题解 P3412 【仓鼠找sugar II】

· · 题解

题意：给定一棵树，结点数为 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。

考虑求答案：枚举 $\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 就好了。