给定一棵有根树，初始所有点都是白色。定义一个结点是好的，当且仅当它到根的路径上（包含端点）都是黑点，否则它是坏的。定义一次操作为，在坏点中均匀随机一个点并令其为黑点。
求使得所有点都是好点的期望操作次数。$2\leq n\leq 2\times 10^5$。
考虑一个问题：有 $n$ 个小球，每次操作均匀随机一个选择，直到所有小球都被选过至少一次，求期望操作次数。设 $f_i$ 表示已经有 $i$ 个被选过的小球时，再选到一个没被选过的小球的期望次数。则有 $f_i=1+\frac{i}{n}+(\frac{i}{n})^2+(\frac{i}{n})^3+\cdots=\frac{n}{n-i}$，则总次数的期望等于 $\sum_{i=0}^{n-1}f_i=n\sum_{i=1}^n \frac{1}{i}$。由于每颗小球等价，所以每颗小球被操作的期望次数就是 $\sum_{i=1}^n \frac{1}{i}$。
在本题中，把每个点到根的路径看成上面的问题，则每个点被操作的期望次数就是 $\sum_{i=1}^{dep} \frac 1i$。由期望的线性性，直接对每个点的期望次数求和。
2 条评论
%%%
尊敬的独立博客作者您好，您的博客已经被收录在博客乌托邦，博客乌托邦是一个中文独立博客文章聚合搜索平台，如有疑问可前往https://utopiablog.cn 留言，祝您新春愉快！