题目描述
$n\le 10^5$。
思路
首先,考虑每一个点的贡献:每一个点被选择后,如果不终止,一定随机选择下一个点,计算这之间的期望路径长度(树形 DP)。这样,我们只需计算每个点期望被选择的次数。此时该问题只与节点的值有关。
当已有 $i$ 个点为 $1$ 时,选择值为 $0/1$ 的点的期望次数为:
$$
f_{i,0}=\frac{1}{n}+\frac{f_{i+1,1}}{n}+\frac{i\cdot f_{i-1,0}}{n}+\frac{(n-i-1)f_{i+1,0}}{n}
$$
$$
f_{i,1}=\frac{1}{n}+\frac{f_{i-1,0}}{n}+\frac{(i-1)f_{i-1,1}}{n}+\frac{(n-i)f_{i+1,1}}{n}
$$
整理可得,
$$
(n-i-1)f_{i+1,0}+f_{i+1,1}=n\cdot f_{i,0}-1-i\cdot f_{i-1,0}
$$
$$
f_{i+1,1}=\frac{n\cdot f_{i,1}-1-f_{i-1,0}-(i-1)f_{i-1,1}}{n-i}
$$
我们用 $f_{1,0/1}$ 来表示每一个 $f$,用 $f_{n-1,0/1}$ 的转移列出方程。