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。完整实现如下vectorint 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），仅供参考