Game on Tree 题解

这题感觉其他的题解写的都不是很清楚（也可能是因为我太弱），导致我并没有看懂。我于是请教了 THU 学长 Mr_Wu，然后他用了 ${10}^{-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}$.

代码是个人都会写，就不放了。