题解 CF280C 【Game on Tree】

**[题目链接](https://www.luogu.com.cn/problem/CF280C)** 这题感觉其他的题解写的都不是很清楚（也可能是因为我太弱），导致我并没有看懂。我于是请教了 THU 学长 [Mr_Wu](https://www.luogu.com.cn/user/62308)，然后他用了 $1^{-10}$ 秒就切了这道题，并且教会了我。 ### 简单题意 给出一棵树，每次随机等概率选择一未染黑的点，将它及其子树染黑。问期望多少次操作可以将树全部染黑。 ### 题解 设 $f_i$ 表示 $i$ 号点表示点 $i$ 被选中的次数（显然只可能是 0 或 1）。 则要求的答案就是 $E[\sum f_i]$，即 $f_i$ 的和的期望， 由期望的可加性，有 $E[\sum f_i]=\sum E[f_i]$。 由于 $f_i$ 的取值只能是 0 或 1，则 $f_i$ 的期望就等于 $f_i$ 等于 1 的概率，设为 $p_i$. 则答案为 $\sum p_i$，即每个球被选中的概率的和。 考虑随机生成一个操作序列，找到序列中第一个未被染色的节点，并染色这个节点和它的子树中的所有节点，重复这个操作，直到序列中所有节点都被染色。 那么 $i$ 号节点被选中的前提就是在序列中，$i$ 号节点的祖先都在 $i$ 号节点的后面。否则，就会在选择 $i$ 号节点之前选择它的祖先，并且 $i$ 节点就会被染色，而不会被选中。 由于 $i$ 号节点共有 $dep_i-1$ 个祖先，故 $i$ 号节点在这个随机序列中排在所有祖先前面的概率是 $\dfrac 1 {dep[i]}$，故 $i$ 号球被选中的概率是 $\dfrac 1 {dep[i]}$. 故答案为 $\sum\dfrac 1 {dep[i]}$. 代码是个人都会写，就不放了。