 实现)
OI-wiki 树上随机游走：向父结点与子结点移动的期望距离完整推导与 O(n) 实现
【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki
导读
本文基于 OI-wiki 图论模块中的「树上随机游走」专题，完整推导有根树上结点随机游走的两类核心期望量：结点 $u$ 走向其父结点的期望距离 $f(u)$，以及父结点走向其子结点 $u$ 的期望距离 $g(u)$。掌握这两组递推式后，读者将能在一棵 $n$ 个结点的树上以 $O(n)$ 的时间复杂度求出任意两个相邻结点之间的期望移动距离，为求解更复杂的树上期望问题（如树上覆盖、首达时间、逃离树根期望步数等）打下坚实的理论基础。
问题背景：硬币在树上的随机游走
给定一棵有根树，树的某个结点上有一枚硬币。在每一个时刻，硬币会等概率地移动到当前结点的任意一个邻接结点上。我们关心的问题是：硬币从某个结点移动到指定邻接结点的期望距离是多少。
这里"期望距离"中的"距离"指硬币移动的步数（或边权之和）。由于树是无环连通图，每个非根结点恰好有一个父结点、若干个子结点，因此"向某个邻接结点移动"天然可以分为两类：
- 从结点 $u$ 移动到其父结点$p_u$；
- 从父结点 $p_u$ 移动到其子结点$u$。
这两种移动在树上并不对称：向父结点走时，硬币可能误入子树再折返；向子结点走时，硬币还可能先跑向父结点的父结点或兄弟结点。这正是推导复杂度所在，也是本文要解决的核心问题。
本文属于 OI-wiki 随机游走系列的一部分，其姊妹篇 docs/graph/graph-random-walk.md 讨论了网格图、稀疏图与一般图上的随机游走（涉及高斯消元、Berlekamp–Massey 算法、稳态分布与矩阵树定理），而本文聚焦于树这一特殊图结构，其关键优势在于：树的无环性使得期望量之间存在不依赖高斯消元的显式递推关系，可以做到线性时间求解。
需要用到的定义
为统一记号，全文沿用以下定义：
| 记号 | 含义 |
|---|---|
| $T=(V,E)$ | 所讨论的树 |
| $d(u)$ | 结点 $u$ 的度数 |
| $w(u,v)$ | 结点 $u$ 与结点 $v$ 之间的边的边权 |
| $p_u$ | 结点 $u$ 的父结点 |
| $\textit{root}$ | 树的根结点 |
| $\textit{son}_u$ | 结点 $u$ 的子结点集合 |
| $\textit{sibling}_u$ | 结点 $u$ 的兄弟结点集合 |
其中"期望"是离散型随机变量的数字特征，其定义为 $E[X]=\sum x_i p_i$（参见 OI-wiki 的 期望与方差 一节）。下文所有推导都建立在期望的线性性之上。
向父结点走的期望距离 $f(u)$
设 $f(u)$ 代表结点 $u$ 走到其父结点 $p_u$ 的期望距离（这里的距离以边权计，边权均为 $1$ 时即期望步数）。按照"从 $u$ 出发的第一步走向哪里"进行分类讨论，可以得到：
$$ f(u) = \cfrac{w(u,p_u) + \sum\limits_{v \in \textit{son}_u}(w(u,v) + f(v) + f(u))}{d(u)} $$
方程的直观含义是：
- 分子中的前半部分$w(u,p_u)$：第一步直接走向父结点，代价即边权；
- 分子中的后半部分：第一步先走向某个子结点 $v$，代价为边权 $w(u,v)$，随后要经历 $f(v)$ 的期望步数从 $v$ 走回 $u$，再经历 $f(u)$ 的期望步数从 $u$ 走到父结点；
- 分母$d(u)$：从 $u$ 出发走向其任意一个邻接点的概率相同，即每个方向出现的概率均为 $\cfrac{1}{d(u)}$。
注意上式右边同时出现了 $f(u)$（自指），因此需要化简消去：
$$ \begin{aligned} f(u) &= \cfrac{w(u,p_u) + \sum\limits_{v \in \textit{son}u}(w(u,v) + f(v) + f(u))}{d(u)} \ &= \cfrac{w(u,p_u) + \sum\limits{v \in \textit{son}u}(w(u,v) + f(v)) + (d(u)-1)f(u)}{d(u)} \ &= w(u,p_u) + \sum\limits{v \in \textit{son}u}(w(u,v) + f(v)) \ &= \sum\limits{(u,t) \in E}w(u,t) + \sum\limits_{v \in \textit{son}_u}f(v) \end{aligned} $$
第三步到第四步利用了 $\sum\limits_{(u,t) \in E}w(u,t) = w(u,p_u)+\sum_{v\in \textit{son}_u} w(u,v)$（所有邻边权之和）。
边界条件：对于叶子结点 $l$（没有子结点），$\sum$ 为空，初始状态为
$$ f(l) = w(p_l, l) $$
即叶子结点走向父结点的期望距离恰为其连边的边权——因为此时从叶子出发只有唯一选择。
无权树的特例：子树度数和
当树上所有边的边权都为 $1$ 时，$f(u)$ 的递推式化为：
$$ f(u) = d(u) + \sum\limits_{v \in \textit{son}_u}f(v) $$
即 $f(u)$ 等于$u$ 子树内所有结点的度数和。这个结论还有一个非常直观的等价刻画：
$f(u)$ 等于 $u$ 子树大小的两倍减 $1$，即 $2 \cdot \textit{size}_u - 1$。
理由：每个结点连向其父亲的边都有且只有一条；除 $u$ 与 $p_u$ 之间的那条边只贡献 $1$ 点度数（$p_u$ 不在子树内）外，子树内的每条边都会为两个端点各贡献 $1$ 点度数，共产生 $2$ 点度数的贡献。
由此可以立刻验证两个边界情形：
- 叶子结点：子树大小为 $1$，$f = 2 \times 1 - 1 = 1$，与 $f(l)=w(p_l,l)=1$ 一致；
- 整棵树的根：$f(\textit{root})$ 无定义（根没有父结点），因此公式仅对非根结点有意义。
向子结点走的期望距离 $g(u)$
设 $g(u)$ 代表 $p_u$ 结点走到其子结点 $u$ 的期望距离。与 $f(u)$ 不同，从 $p_u$ 出发走向 $u$ 时，第一步可能"走错"的方向更多：可能直接走向 $u$，可能先走向 $p_u$ 的父结点再折返，也可能先走向 $u$ 的兄弟结点再折返。按第一步分类可得：
$$ g(u) = \cfrac{w(p_u,u) + \left(w(p_u,p_{p_u})+g(p_u)+g(u)\right) + \sum\limits_{s \in \textit{sibling}_u}(w(p_u,s)+f(s)+g(u))}{d(p_u)} $$
各部分的含义：
- 第一部分$w(p_u,u)$：第一步直接走向子结点 $u$；
- 第二部分$w(p_u,p_{p_u})+g(p_u)+g(u)$：第一步先走向父结点 $p_{p_u}$（注意 $g(p_u)$ 表示 $p_{p_u}$ 走向 $p_u$ 的期望距离，此时走的是反向路径），再由 $p_u$ 走回 $p_u$……更准确地理解：先花费 $w(p_u,p_{p_u})$ 到达 $p_{p_u}$，再以期望 $g(p_u)$ 从 $p_{p_u}$ 回到 $p_u$，最后以期望 $g(u)$ 从 $p_u$ 走到 $u$；
- 第三部分$\sum\limits_{s \in \textit{sibling}_u}(w(p_u,s)+f(s)+g(u))$：第一步先走向兄弟结点 $s$（代价 $w(p_u,s)$），随后以期望 $f(s)$ 从 $s$ 走回 $p_u$（注意 $f(s)$ 正是"子结点走向父结点"的量，方向恰好相反），最后以期望 $g(u)$ 从 $p_u$ 走到 $u$；
- 分母$d(p_u)$：从 $p_u$ 走向其任意邻接点的概率均为 $\cfrac{1}{d(p_u)}$。
与 $f(u)$ 的推导类似，将含 $g(u)$ 的自指项收集后化简：
$$ \begin{aligned} g(u) &= \cfrac{w(p_u,u) + \left(w(p_u,p_{p_u})+g(p_u)+g(u)\right) + \sum\limits_{s \in \textit{sibling}u}(w(p_u,s)+f(s)+g(u))}{d(p_u)} \ &= \cfrac{w(p_u,u) + w(p_u,p{p_u}) + g(p_u) + \sum\limits_{s \in \textit{sibling}u}\left(w(p_u,s)+f(s)\right)+(d(p_u)-1)g(u)}{d(p_u)} \ &= w(p_u,u) + w(p_u,p{p_u}) + g(p_u) + \sum\limits_{s \in \textit{sibling}u}(w(p_u,s)+f(s)) \ &= \sum\limits{(p_u,t) \in E}w(p_u,t) + g(p_u) + \sum\limits_{s \in \textit{sibling}u}f(s) \ &= \sum\limits{(p_u,t) \in E}w(p_u,t) + g(p_u) + \left(f(p_u)-\sum\limits_{(p_u,t) \in E}w(p_u,t)-f(u)\right) \ &= g(p_u) + f(p_u) - f(u) \end{aligned} $$
最后两步使用了 $f(u)$ 的结果：由 $f(p_u) = \sum_{(p_u,t)\in E}w(p_u,t)+\sum_{s\in\textit{sibling}_u}f(s)+f(u)$，移项即可把"兄弟结点的 $f$ 值之和"替换为 $f(p_u)-\sum w - f(u)$，从而得到极其简洁的最终形式：
$$ g(u) = g(p_u) + f(p_u) - f(u) $$
边界条件：根结点没有父结点，取
$$ g(\textit{root}) = 0 $$
这个结果非常优美：$g(u)$ 只需要父结点的 $g$ 值与相邻两个结点的 $f$ 值即可确定，整棵树上所有 $g$ 值可以通过自顶向下的单次遍历线性求出。
代码实现（以无权树为例）
基于上述两组递推式，求解过程分为两次 DFS：
- 自底向上求 $f$：
dfs1从叶子向根回溯，先递归处理所有子结点，再累加 $f$ 值。对于无权树，$f(u)=d(u)+\sum_{v\in son_u} f(v)$，其中 $d(u)$ 在无向图中恰为G[u].size()； - 自顶向下求 $g$：
dfs2从根向叶子递推，利用g[u] = g[p] + f[p] - f[u]，根结点的g[root] = 0。
完整实现如下：
vector<int> G[MAXN]; void dfs1(int u, int p) { f[u] = G[u].size(); for (auto v : G[u]) { if (v == p) continue; dfs1(v, u); f[u] += f[v]; } } void dfs2(int u, int p) { if (u != root) g[u] = g[p] + f[p] - f[u]; for (auto v : G[u]) { if (v == p) continue; dfs2(v, u); } }几点实现细节说明：
- 邻接表
G以无向图方式存储（每条边存两遍），因此G[u].size()即为无向图度数 $d(u)$，与公式中"无权树 $f(u)=d(u)+\sum f(v)$"严格对应； dfs1中先递归再累加，保证子结点的 $f$ 值在父结点使用前已被计算；dfs2中if (u != root)的判定等价于初始条件 $g(\textit{root})=0$：根结点在dfs2入口处不会被赋值，其初始值应预置为 $0$；- 两遍 DFS 的每个结点都只被访问常数次，因此总时间复杂度为 $O(n)$，空间复杂度为 $O(n)$（邻接表与两个 DP 数组），相比一般图上随机游走问题常用的高斯消元 $O(n^3)$（参见 docs/graph/graph-random-walk.md）有着数量级的优势，这也是树结构带来的最大便利。
带权树的扩展
若边带权，只需在dfs1中把初始值由G[u].size()改为 $\sum_{(u,t)\in E}w(u,t)$（即u的所有邻边权值之和），递推式改为
$$ f(u) = \sum_{(u,t)\in E}w(u,t) + \sum_{v\in son_u}f(v) $$
而 $g(u)=g(p_u)+f(p_u)-f(u)$ 的形式保持不变（边权信息已全部吸收进 $f$ 中）。叶子结点的初始条件 $f(l)=w(p_l,l)$ 也在求和式中自然成立。
与概率 DP 的衔接
树上随机游走的期望计算本质上是一类树上概率 DP。OI-wiki 的 概率 DP 专题 指出：解决期望问题通常需要逆序循环递推，而当状态转移存在后效性（环状依赖）时往往要借助高斯消元。本文的巧妙之处在于：
- 树作为无环图，虽然从任意结点出发的下一步方向"看似"构成环（走向子结点又折返），但通过对自指项做代数化简（收集等式两边的 $f(u)$、$g(u)$），后效性被完全消除，得到了无环的显式递推；
- 求解顺序因此完全由树的父子关系确定：$f$ 自底向上（类似树上 DP 的后序 DFS），$g$ 自顶向下（类似前序 DFS）。
这一"化简自指项、消除后效性"的手法可以推广到更复杂的树上随机过程（如带吸收点的随机游走、树上多硬币问题等），是解决树上期望问题的重要范式。
总结
| 量 | 含义 | 递推式 | 求解方向 |
|---|---|---|---|
| $f(u)$ | $u$ 走向父结点 $p_u$ 的期望距离 | $f(u)=\sum_{(u,t)\in E}w(u,t)+\sum_{v\in son_u}f(v)$ | 自底向上（后序 DFS） |
| $g(u)$ | $p_u$ 走向子结点 $u$ 的期望距离 | $g(u)=g(p_u)+f(p_u)-f(u)$ | 自顶向下（前序 DFS） |
核心要点：
- 两组递推式相互配合：$f$ 自下而上独立求解，$g$ 依赖 $f$ 自上而下求解；边界条件分别为 $f(l)=w(p_l,l)$（叶子）与 $g(\textit{root})=0$（根）。
- 无权树有闭式解：$f(u)$ 等于 $u$ 子树所有结点度数之和，也等于 $2\cdot \textit{size}_u-1$，可进一步简化实现。
- 复杂度为 $O(n)$：两遍 DFS 即可求出所有相邻结点对的期望移动距离，无需高斯消元。
文中推导与代码均可在 OI-wiki 仓库的 docs/graph/tree-random-walk.md 找到原始版本；关于有根树、父子、兄弟等基础术语，可参考 树的定义一节。
【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
