给定一棵 \(n\) 个点的基环树，每次随机选择一个节点 \(u\) 执行以下操作：
- 将 \(u\) 的所在连通块大小加到 \(ans\) 里。
- 删除 \(u\) 及其连边。
问 \(ans\) 的期望大小。
\(n \le 3000\)
先考虑一棵树的情况。
为了不记录整棵树的形态，考虑使用期望线性性拆成若干个小部分进行贡献。这个题中考虑有序数对 \((u, v)\) 对答案的贡献（\(u\) 删除时 \(v\) 在其子树内），设 \(u\) 到 \(v\) 的路径上有 \(x\) 个点，只有 \(u\) 是这 \(x\) 个点中最后一个被删的才有贡献。所以答案为：
\[\sum\limits_{i = 1}^n\sum\limits_{j = 1}^n \frac{1}{dis(i, j) + 1}
\]
在考虑基环树，还是考虑 \((u, v)\) 的贡献。
- 如果 \(u, v\) 之间没有那个环，计算方式同上。
- 否则有两条路径 \(l1, l2\)，\(u\) 只要是 \(l1/l2\) 中删的最晚的即可。简单容斥一下，答案为 \(\frac{1}{|l1|} + \frac{1}{|l2|} - \frac{1}{|l1 \cup l2|}\)。
分讨一下即可。
时间复杂度：\(O(n^2)\)
通过”拆贡献“的方式不用记录树的形态就可以计算了。期望题很多都可以拆一拆。