题面以图片显示，请点击“阅读全文”查看。
链接
题解
这题有两问。
第一问
如果令 $dp[x]$ 为有 $x$ 个叶节点的时候叶节点的平均深度，那么有如下方程：
$$
\begin{aligned}{}
dp[x] &= \frac{(x-1)dp[x-1] - dp[x-1] + 2 \times (dp[x-1]+1)}{x}\
&=dp[x-1] + \frac{2}{x}
\end{aligned}
$$
初始 $dp[1] = 0$ ， $O(n)$ 递推或者搞一搞通项即可qwq。
第二问
树的深度不太好搞。
定理：
$$
E(x) = \sum _ {i=1}^{+\infty} P(i \leq x)
$$
感性理解：大小为 $x$ 的可能性就会被从 $i = 1$ 到 $i = x$ 一直累积，累积正好就是 $x$ 次，就是这种可能性的值，所以这个式子的值就是期望。
所以我们只要求出在树的叶节点有 $x$ 个的时候，求出树的深度 $i$ 大于 $1$ ，大于 $2$ ，…，一直到大于 $n-1$ 的概率，然后求和之后就是树的期望深度了。
令 $dp[x][j]$ 为有 $x$ 个叶节点时树的深度大于 $j$ 的概率，因为展开在两侧时完全等概率的，所以我们有如下方程：
$$
dp[x][j] = \frac{1}{x-1}(\sum _ {i=1}^{x-1} dp[i][j-1] + dp[x-i][j-1] - dp[i][j-1] \times dp[x-i][j-1])
$$
很简单的容斥。转移即可。注意一下边界，和根结点深度为0即可。
代码
| |
