[？？记录]arc150D Removing Gacha

题意：给定一棵初始所有节点为白色的有根树，定义一个节点是“好的”当且仅当它与它的所有祖先节点都是黑色的，定义一次操作为随机一个不好的点染黑，求期望操作数。

首先根据期望的线性性，总期望操作数等于每个节点上的期望操作数。

接着每个节点上的期望操作数仅与该节点的深度有关。学校里盯着这点看了半天都思考不下去。

把链拎出来，在整条链都是黑色前操作不会停止。

有两个推法。

注意到这个期望之所以难算，是因为选到每个节点的概率在变化。现在允许选好的节点，反复染一个节点显然不影响答案（最右点的操作数），而因为均匀随机，所有坏点的概率是一样的，所以此时的期望操作数与答案等价。

那么问题转化为：每次随便涂，涂满为止。

考虑到已有 \(m\) 数时下一次取到不同数的概率是 \(\dfrac{n-m}{n}\)，所以期望取 \(\dfrac{n}{n-m}\) 次取到新数，所以一共取数 \(\sum_{i=1}^n \dfrac{n}{i}\) 次，因为所有球相同，单个球的期望操作次数就是 \(\sum_{i=1}^n \dfrac{1}{i}\)。

允许选过的数再被选是一个经典的套路。有了这个转化后其实挺平凡。

原文地址：http://www.cnblogs.com/purplevine/p/16879033.html