题解：AT_arc150_d [ARC150D] Removing Gacha

首先有个很经典的做法是设 $E(u)$ 为 $u$ 期望被选中多少次，答案为 $\sum_{i=1}^{n} E_i$。

树上问题还是太难了，不难发现操作后对 $u$ 被选中的次数产生影响的的只会是其祖先结点，于是可以把树上问题变成链上问题。

接着观察性质。发现做了 $E(u)$ 这个转化次数之后我们在计算 $E(u)$ 的时候不需要考虑哪些好顶点会不会选中，因为在考虑 $E(u)$ 时只要选中的点不是 $u$ 都不会产生代价。

枚举 $u$ 在其和其祖先节点中选中的时候在那几次被选中，假设这个链的长度为 $x$。那么如果已经选中过了 $i$ 个点，选中下一个没有选择过的点的期望操作次数为 $\frac{x}{x-i}$，而这一次操作选择这个点的概率为 $\frac{1}{x-i}$，所以 $E(u)=\sum_{i=0}^{x-1}\frac{1}{x-i}=\sum_{i=1}^{x}\frac{1}{i}$，预处理一下即可。

时间复杂度 $\operatorname{O}(n)$。