自动搬运

查看原文

来自洛谷，原作者为

	Elegia irony

搬运于2025-08-24 22:28:02，当前版本为作者最后更新于2021-01-02 23:59:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

我们不难确认如下事实：

任何时刻，将所在位置归类为在根节点或不在根节点，若不在根节点，那么有等概率（即$\bf \frac 1{n-1}$）出现在任何一个非根节点。

我们不妨设 $f_{i,j}$ 表示当前还剩 $i$ 个节点没有被占领，$j=0$ 表示现在在根节点，$j=1$ 表示在 $\bf n-1-i$ 个已经被占领的非根节点中随机选取一个节点作为所在位置，接下来的期望所需代价。

那么我们就不难设计转移了，首先预处理三个量：

• $x$：从根节点随机走到另外一个节点的期望代价。
• $y$：从随机一个非根节点走到根节点的期望代价。
• $z$：从一个随机非根节点走到另一个随机非根节点的期望代价。

这三者只要预处理出每个节点到其他所有节点的距离之和就可以 $\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)$ 解方程方法解决了本题。