树上随机游走的期望步数可沿路径相加:向上 f[x]=deg[x]+Σf[儿子]、向下 g[c]=g[x]+f[x]-f[c],配树上前缀和与倍增 LCA 做到 O(1) 回答每个询问。
OJ: roj
题目 ID: 1775
难度:提高+/省选-
标签:动态规划数学期望树形DP最近公共祖先python
创建: 2026-10-08 01:49
更新: 2026-10-08 01:49
形式化题目
给定一棵
正解
思路
朴素做法。 随机游走的期望步数一般要列全局线性方程组高斯消元,单次
关键观察一:路径可加。 树上
即整条路径的期望步数等于逐条边期望步数之和。
关键观察二:方向解耦。 树上每条边只有两个方向,于是只需两类量:
:从 出发向上首次走到父亲 的期望步数; :从父亲 出发向下首次走到 的期望步数。
任意询问
关键观察三:两条递推式都极简。 设
两边乘
它的直观含义是:从子树内部首次跳出到父亲,期望步数恰好等于该子树内所有点的度数之和。
向下走同理,在父亲
它的直观含义是:向上走的"开销"满足一个望远镜式的关系,向下走可以由父节点的
步骤。
- 以
为根 BFS,得到每个点的父亲 、深度 和自顶向下的遍历序; - 按逆遍历序自底向上做
; - 按遍历序自顶向下做
,同时递推两条树上前缀和 、 ; - 倍增预处理
; - 每次询问求出
,答案为 。 时 ,两项都是 ,边界自然成立。
为什么不用取模的中间量也不会溢出? 因为 long long 绰绰有余。答案本身是整数,不存在有理数取模的麻烦。
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 01:49
# update_at: 2026-10-08 01:55
import sys
MOD = 1000000007 # 答案取模
LOG = 17 # 倍增层数:2^17 = 131072 > 1e5
type Adj = list[list[int]] # adj[x] = 与 x 相邻的所有点
type Table = list[list[int]] # up[j][x] = x 的 2^j 级祖先,0 表示不存在
def build_tree(n: int, adj: Adj) -> tuple[list[int], list[int], list[int]]:
"""以 1 为根做 BFS,返回 (父亲数组, 深度数组, BFS 序)。
order 边遍历边增长,等价于一个队列;树上除了父亲没有别的已访问邻居。
"""
fa = [0] * (n + 1)
dep = [0] * (n + 1)
order = [1]
for x in order:
for y in adj[x]:
if y != fa[x]:
fa[y] = x
dep[y] = dep[x] + 1
order.append(y)
return fa, dep, order
def prefix_sums(n: int, fa: list[int], order: list[int], adj: Adj) -> tuple[list[int], list[int]]:
"""返回 (pf, pg):根到每个点的路径上「向上期望 f」「向下期望 g」之和。
f[x] = deg[x] + Σ f[儿子]:从 x 出发首次走到父亲的期望步数;
g[x] = g[fa] + f[fa] - f[x]:从父亲出发首次走到 x 的期望步数。
"""
f = [len(adj[x]) for x in range(n + 1)]
for x in reversed(order[1:]): # 逆 BFS 序即自底向上
f[fa[x]] += f[x]
g = [0] * (n + 1)
pf = [0] * (n + 1)
pg = [0] * (n + 1)
for x in order[1:]: # BFS 序即自顶向下
p = fa[x]
g[x] = g[p] + f[p] - f[x]
pf[x] = pf[p] + f[x]
pg[x] = pg[p] + g[x]
return pf, pg
def build_up(fa: list[int], n: int) -> Table:
"""倍增表:up[j][x] 是 x 的 2^j 级祖先(0 表示不存在)。"""
up: Table = [fa] # 第 0 层就是父亲数组本身,只读不改
for _ in range(LOG):
prev = up[-1]
up.append([prev[prev[x]] for x in range(n + 1)])
return up
def lca(u: int, v: int, dep: list[int], up: Table) -> int:
"""求 u、v 的最近公共祖先:先把深的拉到同深度,再一起倍增上跳。"""
if dep[u] < dep[v]:
u, v = v, u
diff = dep[u] - dep[v]
for j in range(LOG):
if diff >> j & 1:
u = up[j][u]
if u == v:
return u
for j in range(LOG, -1, -1):
if up[j][u] != up[j][v]:
u, v = up[j][u], up[j][v]
return up[0][u]
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, q = next(data), next(data)
adj: Adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = next(data), next(data)
adj[u].append(v)
adj[v].append(u)
fa, dep, order = build_tree(n, adj)
pf, pg = prefix_sums(n, fa, order, adj)
up = build_up(fa, n)
# u 向上走到 z=LCA,再向下走到 v:两段期望步数直接相加
out: list[str] = []
for _ in range(q):
u, v = next(data), next(data)
z = lca(u, v, dep, up)
out.append((pf[u] - pf[z] + pg[v] - pg[z]) % MOD)
sys.stdout.write('\n'.join(map(str, out)) + '\n')
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 01:49
* update_at: 2026-10-08 01:49
*/
// 1775《梦中漫步》:树上随机游走的期望步数(树形 DP + 倍增 LCA)
// 以 1 为根,f[x] 表示从 x 出发首次走到父亲的期望步数,
// g[x] 表示从父亲出发首次走到 x 的期望步数。
// 设 d[x] 为 x 的度数,son(x) 为 x 的儿子集合,由马尔可夫方程消元得
// f[x] = d[x] + Σ_{c∈son(x)} f[c] (即子树内所有点的度数之和)
// g[c] = g[x] + f[x] - f[c] (x 是 c 的父亲)
// 两者都是整数,配合树上前缀和 + LCA 即可 O(1) 回答每个询问:
// ans(u, v) = (pf[u] - pf[z]) + (pg[v] - pg[z]), z = LCA(u, v)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007; // 答案取模
const int MAXN = 100005; // 点数上限
const int LOG = 18; // 倍增层数:2^17 = 131072 > 1e5
struct Node {
int fa; // 父亲编号,根节点 1 的父亲记为虚点 0
int dep; // 深度,根的深度为 0
ll deg; // 度数
ll f; // f[x]:从 x 出发首次走到父亲的期望步数
ll g; // g[x]:从父亲出发首次走到 x 的期望步数
ll pf; // 根到 x 路径上所有 f 之和(不含根的 f)
ll pg; // 根到 x 路径上所有 g 之和(不含根的 g)
};
Node nd[MAXN]; // nd[x] 就是节点 x 的全部属性
int head[MAXN], nxt[MAXN << 1], to[MAXN << 1], ecnt; // 链式前向星
int order[MAXN]; // BFS 序,order[1..n];父亲一定排在儿子前面
int up[MAXN][LOG]; // 倍增表:up[x][j] 是 x 的 2^j 级祖先(0 表示不存在)
// 加一条有向边 u -> v
void add_edge(int u, int v) {
to[++ecnt] = v;
nxt[ecnt] = head[u];
head[u] = ecnt;
}
// 以 1 为根做 BFS,求出每个点的父亲、深度,以及自顶向下的遍历序
void build_tree(int n) {
int qh = 1, qt = 1;
order[qt] = 1;
nd[1].fa = 0;
nd[1].dep = 0;
while (qh <= qt) {
int x = order[qh++];
for (int e = head[x]; e; e = nxt[e]) {
int y = to[e];
if (y == nd[x].fa) continue; // 只有父亲是"已访问"的邻居,跳过即可
nd[y].fa = x;
nd[y].dep = nd[x].dep + 1;
order[++qt] = y;
}
}
}
// 自底向上求 f[x] = deg[x] + Σ f[儿子]
void calc_f(int n) {
for (int x = 1; x <= n; x++) nd[x].f = nd[x].deg;
for (int i = n; i >= 2; i--) {
int x = order[i];
nd[nd[x].fa].f += nd[x].f;
}
}
// 自顶向下求 g[x] 与两条前缀和 pf / pg
void calc_g(int n) {
nd[1].g = 0;
nd[1].pf = 0;
nd[1].pg = 0;
for (int i = 2; i <= n; i++) {
int x = order[i], p = nd[x].fa;
nd[x].g = nd[p].g + nd[p].f - nd[x].f;
nd[x].pf = nd[p].pf + nd[x].f;
nd[x].pg = nd[p].pg + nd[x].g;
}
}
// 倍增表预处理
void build_up(int n) {
for (int x = 1; x <= n; x++) up[x][0] = nd[x].fa;
for (int j = 1; j < LOG; j++)
for (int x = 1; x <= n; x++)
up[x][j] = up[up[x][j - 1]][j - 1];
}
// 求 u、v 的最近公共祖先
int lca(int u, int v) {
if (nd[u].dep < nd[v].dep) { int t = u; u = v; v = t; }
int diff = nd[u].dep - nd[v].dep;
for (int j = 0; j < LOG; j++)
if (diff >> j & 1) u = up[u][j];
if (u == v) return u;
for (int j = LOG - 1; j >= 0; j--)
if (up[u][j] != up[v][j]) { u = up[u][j]; v = up[v][j]; }
return up[u][0];
}
int main() {
int n, q;
if (scanf("%d %d", &n, &q) != 2) return 0;
for (int i = 1; i <= n - 1; i++) {
int u, v;
scanf("%d %d", &u, &v);
add_edge(u, v);
add_edge(v, u);
nd[u].deg++;
nd[v].deg++;
}
build_tree(n);
calc_f(n);
calc_g(n);
build_up(n);
while (q--) {
int u, v;
scanf("%d %d", &u, &v);
int z = lca(u, v);
// u 向上走到 z,再向下走到 v;两段期望步数直接相加
ll ans = (nd[u].pf - nd[z].pf + nd[v].pg - nd[z].pg) % MOD;
if (ans < 0) ans += MOD;
printf("%lld\n", ans);
}
return 0;
}复杂度
- 时间:BFS 建树与两次树形 DP 都是
;倍增表预处理 ; 每次询问 求 LCA、 查前缀和。总计 , 时约 次基本操作。实测最大点 0.05 s、峰值 16 MB(限时 1 s / 256 MB)。 - 空间:邻接表、
、倍增表均为 或 , 约 MB,远低于 256 MB。 - 与 C++ 解法的关系:
main.py与main.cpp是同一算法的两个实现, 复杂度同阶。的链/菊花/完全二叉树点上 Python 实测 0.16~0.25 s, 即使常数再放大数倍也仍在 1 s 时限内,本题不存在 Python 特有的 TLE 风险。
总结
- 期望问题先找可加性:树上的随机游走满足马尔可夫无后效性,整条路径的期望可以
拆成逐条边的期望之和,这一步把
的"每次重新解方程"变成全局一次预处理。 - 按方向而不是按点设状态:树上每条边只有上下两个方向,
(向上)与 (向下) 两个状态就覆盖了所有情况; 的递推式 还是望远镜式的, 直接说明 不会比 大一个量级。 - 式子能化简就化简:
是消元后的封闭形式, 一眼看出 就是子树度数和,既给出了溢出上界,也让代码只有一行累加。 - 树上任意两点路径用 LCA + 前缀和:这是把"路径求和"从
压到 的标准套路,本题只是把求和对象换成了期望值。
素材说明:本题素材源(
new_ROJ/problems/1775/)中附带了数据生成脚本data.py, 说明data/的 10 个测试点是自造的(按题面的、 、 链、 随机树/菊花/完全二叉树/毛毛虫分层构造),题面文本也可能来自网络重建, 与官方原题的分层细节未必一致。素材源的 std.cpp与本解法思路一致, 已编译并与全部 10 组.out比对通过。验证:
main.cpp/main.py在 10 组真实数据上均与.out逐字节一致; 另用独立暴力(对每个目标点列的方程并做模意义高斯消元)在 400 组 的随机树上对拍,全部一致。