• 周六. 7月 2nd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

CodeForces 280C Game on Tree

admin

11月 28, 2021

题意简述

一棵有 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)}.)

发表评论

您的电子邮箱地址不会被公开。