梦中漫步

GitHub跳转原题关系图返回列表

树上随机游走的期望步数可沿路径相加:向上 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

形式化题目

给定一棵 NN 个点的树 T=(V,E)T=(V,E)。你在树上做随机游走:身处点 xx 时, 等概率地(概率 1deg⁡(x)\frac{1}{\deg(x)})选择 xx 的一条出边走一步。 给出 QQ 次询问,每次给出起点 uu 与终点 vv,求从 uu 出发首次到达 vv 时 所走的期望步数,答案对 109+710^9+7 取模后输出。

N,Q⩽105N, Q \leqslant 10^5,N=1N=1 时无输入边(此时唯一的询问只能是 1 11\ 1,答案为 00)。

正解

思路

朴素做法。 随机游走的期望步数一般要列全局线性方程组高斯消元,单次 O(N3)O(N^3); 即便利用树的结构,对每个询问从起点单独列方程,单次也要 O(N)O(N),总复杂度 O(NQ)O(NQ), N=Q=105N=Q=10^5 时约 101010^{10},远超 1 s 的时限。瓶颈在于"每次询问都重新解一遍方程"。

关键观察一:路径可加。 树上 u→vu \to v 的简单路径唯一,记作 p1(=u),p2,…,pk(=v)p_1(=u), p_2, \dots, p_k(=v)。因为树上无环,从 pip_i 走到 vv 之前必须先首次到达 pi+1p_{i+1};而一旦到达 pi+1p_{i+1},之后的过程与"在 pip_i 侧枝里绕了多久"完全无关 (马尔可夫无后效性)。所以

E(u→v)=∑i=1k−1E(pi→pi+1),E(u \to v) = \sum_{i=1}^{k-1} E(p_i \to p_{i+1}),

即整条路径的期望步数等于逐条边期望步数之和。

关键观察二:方向解耦。 树上每条边只有两个方向,于是只需两类量:

  • f(x)f(x):从 xx 出发向上首次走到父亲 fa[x]\mathrm{fa}[x] 的期望步数;
  • g(x)g(x):从父亲 fa[x]\mathrm{fa}[x] 出发向下首次走到 xx 的期望步数。

任意询问 (u,v)(u,v) 取 z=LCA(u,v)z=\mathrm{LCA}(u,v),就把路径拆成了"uu 向上走到 zz"与 "zz 向下走到 vv"两段,只需分别累加 ff 与 gg。

关键观察三:两条递推式都极简。 设 xx 的度数为 d(x)d(x),儿子集合为 son(x)\mathrm{son}(x)。在 xx 处有 1d(x)\frac{1}{d(x)} 的概率一步到父亲;有 1d(x)\frac{1}{d(x)} 的概率到某个儿子 cc,之后要先花 f(c)f(c) 步回到 xx,再花 f(x)f(x) 步到父亲:

f(x)=1+1d(x)∑c∈son(x)(f(c)+f(x)).f(x) = 1 + \frac{1}{d(x)}\sum_{c \in \mathrm{son}(x)} \bigl(f(c) + f(x)\bigr).

两边乘 d(x)d(x) 移项,f(x)f(x) 的系数只剩 11,直接解出

f(x)=d(x)+∑c∈son(x)f(c).\boxed{f(x) = d(x) + \sum_{c \in \mathrm{son}(x)} f(c)}.

它的直观含义是:从子树内部首次跳出到父亲,期望步数恰好等于该子树内所有点的度数之和。

向下走同理,在父亲 xx 处展开一步并消去其他儿子与祖先方向的影响后得到

g(c)=g(x)+f(x)−f(c)(c∈son(x), g(根)=0).\boxed{g(c) = g(x) + f(x) - f(c)} \qquad (c \in \mathrm{son}(x),\ g(\text{根}) = 0).

它的直观含义是:向上走的"开销"满足一个望远镜式的关系,向下走可以由父节点的 gg 直接推出, 不必重新遍历子树。

步骤。

  1. 以 11 为根 BFS,得到每个点的父亲 fa\mathrm{fa}、深度 dep\mathrm{dep} 和自顶向下的遍历序;
  2. 按逆遍历序自底向上做 f(x)=d(x)+∑f(c)f(x) = d(x) + \sum f(c);
  3. 按遍历序自顶向下做 g(c)=g(x)+f(x)−f(c)g(c) = g(x) + f(x) - f(c),同时递推两条树上前缀和 pf[x]=pf[fa[x]]+f(x)pf[x] = pf[\mathrm{fa}[x]] + f(x)、pg[x]=pg[fa[x]]+g(x)pg[x] = pg[\mathrm{fa}[x]] + g(x);
  4. 倍增预处理 LCA\mathrm{LCA};
  5. 每次询问求出 z=LCA(u,v)z=\mathrm{LCA}(u,v),答案为 (pf[u]−pf[z])+(pg[v]−pg[z]) mod (109+7)\bigl(pf[u]-pf[z]\bigr) + \bigl(pg[v]-pg[z]\bigr) \bmod (10^9+7)。 u=vu=v 时 z=uz=u,两项都是 00,边界自然成立。

为什么不用取模的中间量也不会溢出? 因为 f(x)f(x) 恰好是子树内度数之和 ⩽2N\leqslant 2N,而 g(c)=f(根)−f(c)g(c)=f(\text{根})-f(c)(沿路径望远镜求和),所以 gg 也不超过 2N2N;前缀和沿深度不超过 NN 个点累加,上界约 2×10102 \times 10^{10}, long long 绰绰有余。答案本身是整数,不存在有理数取模的麻烦。

代码

Python 版:

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++ 版(同一算法):

cpp
/**
 * 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 都是 O(N)O(N);倍增表预处理 O(Nlog⁡N)O(N \log N); 每次询问 O(log⁡N)O(\log N) 求 LCA、O(1)O(1) 查前缀和。总计 O((N+Q)log⁡N)O\bigl((N+Q)\log N\bigr), N=Q=105N=Q=10^5 时约 3×1063 \times 10^6 次基本操作。实测最大点 0.05 s、峰值 16 MB(限时 1 s / 256 MB)。
  • 空间:邻接表、f/g/pf/pgf/g/pf/pg、倍增表均为 O(N)O(N) 或 O(Nlog⁡N)O(N \log N), 约 105×18×4B≈710^5 \times 18 \times 4\text{B} \approx 7 MB,远低于 256 MB。
  • 与 C++ 解法的关系:main.py 与 main.cpp 是同一算法的两个实现, 复杂度同阶。N=Q=105N=Q=10^5 的链/菊花/完全二叉树点上 Python 实测 0.16~0.25 s, 即使常数再放大数倍也仍在 1 s 时限内,本题不存在 Python 特有的 TLE 风险。

总结

  • 期望问题先找可加性:树上的随机游走满足马尔可夫无后效性,整条路径的期望可以 拆成逐条边的期望之和,这一步把 O(NQ)O(NQ) 的"每次重新解方程"变成全局一次预处理。
  • 按方向而不是按点设状态:树上每条边只有上下两个方向,ff(向上)与 gg(向下) 两个状态就覆盖了所有情况;gg 的递推式 g(c)=g(x)+f(x)−f(c)g(c)=g(x)+f(x)-f(c) 还是望远镜式的, 直接说明 gg 不会比 ff 大一个量级。
  • 式子能化简就化简:f(x)=d(x)+∑f(c)f(x)=d(x)+\sum f(c) 是消元后的封闭形式, 一眼看出 ff 就是子树度数和,既给出了溢出上界,也让代码只有一行累加。
  • 树上任意两点路径用 LCA + 前缀和:这是把"路径求和"从 O(路径长)O(\text{路径长}) 压到 O(log⁡N)O(\log N) 的标准套路,本题只是把求和对象换成了期望值。

素材说明:本题素材源(new_ROJ/problems/1775/)中附带了数据生成脚本 data.py, 说明 data/ 的 10 个测试点是自造的(按题面的 N⩽10N \leqslant 10、N⩽1000N \leqslant 1000、 链、N=Q=105N=Q=10^5 随机树/菊花/完全二叉树/毛毛虫分层构造),题面文本也可能来自网络重建, 与官方原题的分层细节未必一致。素材源的 std.cpp 与本解法思路一致, 已编译并与全部 10 组 .out 比对通过。

验证:main.cpp / main.py 在 10 组真实数据上均与 .out 逐字节一致; 另用独立暴力(对每个目标点列 E[x]=1+1d(x)∑y∼xE[y]E[x]=1+\frac{1}{d(x)}\sum_{y\sim x}E[y] 的方程并做模意义高斯消元)在 400 组 N⩽8N \leqslant 8 的随机树上对拍,全部一致。