ARC150D Removing Gacha

题意：给定 $n$ 个点的树，定义一个点是好的当且仅当它和它的所有祖先都是黑色的，从所有点都是白点开始，任选一个不好的点染成黑色，问期望染多少次使得所有都是黑色。$n\leq 2\times 10 ^ 5$，对 998244353 取模。

非常 nb 的期望题，做了一整场 /cy

和题解角度不同，我们考虑每个点的时候，需要考虑它没被祖先覆盖的概率，然后再在它的子树内部任意选，直到选到这个点为止。容易发现我们如果没选在子树内部的话，根据期望的线性性，我们可以把不同子树之间的答案直接加就好了。

首先考虑在它的子树内部任意选的期望。因为子树的根是没有被选中的，所以所有点都是不好的点，那么期望就是 $sz(x)$ 能选中子树的根。

然后考虑它没被祖先覆盖的概率。我们不管其他节点，我们现在只关心我们选到了 $x$ 以及所有祖先的情况。这个相当于是我们把所有祖先都染成黑色了，但是 $x$ 没被碰到。

有一个好点的限制比较烦，但是注意到我们选择好点对概率是没有影响的。所以我们相当于是不管好不好，所有点都是随机一个选择。这样的话，所有点是等价的，那么 $x$ 没被碰到相当于是 $x$ 被最后选到，概率就是 $\dfrac 1{dep(x)}$。

于是我们可以得到答案为 $\displaystyle \sum_{i = 1} ^ n \dfrac {sz(x)}{dep(x)}$。直接计算即可，时间复杂度 $O(n)$ 或者 $O(n\log a)$。

void dfs(int x)
{
	if (x ^ 1) dep[x] = dep[fa[x]] + 1;
	sz[x] = 1;
	for (int v : g[x]) dfs(v), sz[x] += sz[v];
	// std::cout << dep[x] << ' ' << sz[x] << '\n';
	res = (res + (LL) qpow(dep[x] + 1) * sz[x]) % Mod;
}