自动搬运

查看原文

来自洛谷，原作者为

	Rui_R El Psy Congroo

搬运于2025-08-24 21:48:44，当前版本为作者最后更新于2021-02-22 15:11:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题意：给定一棵树，结点数为 $n$，一个人从起点 $s$ 出发，在上面等概率选当前能走的边走，直到走到终点 $t$ 。$s,t$ 未知。求他所经过边数的期望。

原题

令 $d_u$ 表示结点 $u$ 的度数，$f_u$ 表示 $u \to fa(u)$ 的期望步数，其中 $u \ne \text{root}$，$f_{\text{root}}$ 没有定义

$$f_u = \frac{1}{d_u} [1+\sum_{fa(v)=u} (f_v+f_u+1)] $$

解方程得到

$$f_u = d_u + \sum_{fa(v) = u} f_v$$

令 $g_u$ 表示 $fa(u)\to u$ 的期望步数，定义 $g_{\text{root}}=0$

当 $fa(u) \ne \text{root}$ ：

$$g_u = \frac{1}{d_{fa(u)}}[1+(1+g_{fa(u)}+g_u)+\sum_{fa(v)=fa(u),v\ne u}(1+f_v+g_u)] $$

解方程得到

$$g_u=d_{fa(u)}+g_{fa(u)}+\sum_{fa(v)=fa(u),v\ne u} f_v=f_{fa(u)}-f_u+g_{fa(u)} $$

当 $fa(u) = \text{root}$：

$$g_u=\frac{1}{d_{fa(u)}}[1+\sum_{fa(v)=fa(u),v\ne u}(1+f_v+g_u)] $$

解得

$$g_u = d_u+\sum_{fa(v)=fa(u),v\ne u} f_v=f_{fa(u)}-f_u $$

由于 $g_{\text{root}}=0$ ，两者可以合并：

$$g_u = f_{fa(u)}-f_u+g_{fa(u)}$$

令 $F(u,v)$ 表示 $u,v$ 这条链上所有点的 $f$ 的和，不含 $v$。

令 $G(u,v)$ 表示 $u,v$ 这条链上所有点的 $g$ 的和，不含 $u$。

$f,g$ 可以线性求出。这样，如果已知 $s,t$ ，就可以通过 $F(s,\text{lca}(s,t)) + G(\text{lca}(s,t),t)$ 求出期望。

考虑求答案：枚举 $\text{lca}(s,t)=u$

令 $u \in v$ 表示 $u$ 在 $v$ 的子树中，$u \notin v$ 表示 $u$ 不在 $v$ 的子树中。

那么此时所有情况的期望和就是

$$\sum_{x \in u} G(u,x)+\sum_{fa(v)=u} ([size(u)-size(v)] \sum_{x \in v} F(x,u)+size(v)\sum_{x \notin v,x \in u} G(u,x) ) $$

意思是，分别计算 $s=x$ 时，$s \in v$ 时的期望和。

预处理 $v=1$ 时的 $F$ 和 $u=1$ 时的 $G$ ，并统计子树内这两个值的和。

那么答案可以 $O(n)$ 计算得到。最后除掉 $n^2$ 就好了。