P3830:[SHOI2012]随机树题解

解法

第一问

第一问比较好求,设状态\(f[i]\)为有\(i\)个叶子节点时的期望深度。考虑从上一个状态分裂会多对总深度做\(f[i-1]+2\)的贡献,可以知道:

\[ f[i] = \frac{f[i-1] * (i-1) + f[i-1] + 2}{i} = f[i-1] + \frac{2}{i} \]

第二问

第二问难了很多,重点设状态\(f[i][j]\):有\(i\)个叶子节点深度大于等于\(j\)的期望树高。考虑枚举一个\(k\)为左子树叶子结点的个数,计算:

\[ f[i][j] = \sum_{k = 1}^{i – 1} f[k][j – 1] + f[i – k][j – 1] – f[k][j – 1] * f[i – k][j – 1] \]

后面删掉重复计算的部分。答案是\(\sum_{i = 1}^{n – 1} f[n][i] \)。

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注