题解 P7247 【教材运送】
Elegia
·
·
题解
我们不难确认如下事实：
任何时刻，将所在位置归类为在根节点或不在根节点，若不在根节点，那么有等概率（即\bf \frac 1{n-1}）出现在任何一个非根节点。
我们不妨设 f_{i,j} 表示当前还剩 i 个节点没有被占领，j=0 表示现在在根节点，j=1 表示在 \bf n-1-i 个已经被占领的非根节点中随机选取一个节点作为所在位置，接下来的期望所需代价。
那么我们就不难设计转移了，首先预处理三个量：
这三者只要预处理出每个节点到其他所有节点的距离之和就可以 \Theta(n) 算出，这只需要 dfs 两遍，不予赘述。
那么对于 1\le i\le n-2，我们根据组合意义直接列出的是一个关于 f_{i,0},f_{i,1} 的方程：
\begin{aligned}
f_{i,0} &= \frac i{n-1}f_{i-1,1}+\frac{n-1-i}{n-1}f_{i,1}&+x\\
f_{i,1} &= \frac i{n-1}f_{i-1,1}+\frac{1}{n-1}f_{i,0}+\frac{n-2-i}{n-1}f_{i,1} & + \frac 1{n-1}y + \frac{n-2}{n-1}z
\end{aligned}
读者不难自行化简上式，会发现化简之后分母关于 i 的部分只有一些形如 i,i+1 等，因此不会发生除以 0 的事情。
综上，我们通过一个简洁的 \Theta(n) 解方程方法解决了本题。