题意简述

一棵有 n 个节点的树，每次等概率随机选一个点，把这个点及其子树都染色，求把整棵树染色的期望次数。

解题报告

答案是 (sum frac{1}{mathrm{depth}(i)})。但是为什么呢？

在这里引入「随机变量指示器」：

给定样本空间 (S) 和事件 (A)，定义它的随机变量指示器 (I{A}) 满足：

[I{A}=left{egin{array}{l} 0, ext { if A don't happen } \ 1, ext { if A happen } end{array} ight. ]

那么在这道题里，令 (X_{i}) 为事件 (T_i) 的随机变量指示器，其中 (T_i) 表示 (i) 这个节点被选中。

所以本题要求的染色次数即为选中的节点数：

[X = sum X_i ]

对两边取期望，

(E(X) = E(sum X_i) = sum E(X_i))

因为 (X_i) 只有 (0) 和 (1) 两个取值，所以 (E(X_i) = P(T_i) imes 1 + P(overline{T_i}) imes 0 = P(T_i))

所以说 (E(X) = sum P(T_i).)

那么接下来只需要知道每个点选中的概率就好了。

考虑随机一个 (1 sim n) 的排列作为操作序列，从前往后扫，遇到未染色的就染色，那么点 (i) 能被选中当且仅当它和它的祖先这些点里，它排在最前面，这个概率是 (frac{1}{mathrm{dep}(i)})

所以答案即为 (sum frac{1}{mathrm{dep}(i)}.)