「一本通 4.4 练习 1」Dis

形式化题目

给定一棵包含 $n$ 个节点和 $n-1$ 条带权无向边的树。给定 $m$ 次询问，每次询问给出两个节点 $u, v$ ，要求计算树上两点 $u$ 和 $v$ 之间的唯一简单路径上的边权和（即两点间最短距离）。

graph TD
    R((1)) --- |10| A((2))
    R --- |15| B((3))
    classDef default fill:#f9f9f9,stroke:#333,stroke-width:1.5px;
    classDef lca fill:#d4edda,stroke:#28a745,stroke-width:2px;
    class R lca;

以样例 2 为例，树上节点 1 连接节点 2（边权 10）和节点 3（边权 15）。询问节点 3 到 2 的距离，其简单路径为 $3 \to 1 \to 2$ ，距离为 $15 + 10 = 25$ 。

正解

思路

树上任意两点 $u$ 和 $v$ 之间有且仅有一条简单路径。若任意钦定一个根节点（例如节点 1），这条简单路径一定由两段构成：从 $u$ 向上走到它们的最深公共分叉点——即最近公共祖先 $\operatorname{LCA}(u, v)$ ，再向下走到 $v$ 。

graph TD
    Root((Root)) --> |...| LCA((LCA u,v))
    LCA --> |...| U((u))
    LCA --> |...| V((v))
    classDef lca fill:#e1f5fe,stroke:#0288d1,stroke-width:2px;
    class LCA lca;

记 $\operatorname{dist}(x)$ 为节点 $x$ 到根节点的路径权值和。根据树上路径的可减性，从根节点到 $u$ 的路径与到 $v$ 的路径重叠部分恰好是根节点到 $\operatorname{LCA}(u, v)$ 的路径。因此，两点间的距离公式为：

\operatorname{dist}(u, v) = \operatorname{dist}(u) + \operatorname{dist}(v) - 2 \cdot \operatorname{dist}(\operatorname{LCA}(u, v))

借助该性质，问题拆解为两步：

预处理深度与距离：从根节点出发进行一次广度优先搜索（BFS），计算出每个节点的深度 $\operatorname{depth}[u]$ 以及到根节点的累积权值 $\operatorname{dist}[u]$ 。同时构建倍增祖先数组 $up[u][k]$ ，表示节点 $u$ 的第 $2^k$ 级祖先。
- 转移方程： $up[u][k] = up[up[u][k-1]][k-1]$ 。
快速回答询问：对于每次询问 $(u, v)$ ：
- 首先利用倍增把较深的节点跳升到与较浅节点相同的深度；
- 若两点重合，则该节点即为 LCA；
- 否则两者同步按 $2^k$ 从大到小向上跳，直到两点的父节点相同，此时父节点即为 LCA；
- 代入上述距离公式即可在 $O(1)$ 计算出答案。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86#!/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-07-05 21:47
# update_at: 2026-07-05 21:47

import sys

LOGN = 16  # 2^15 = 32768 > 10000


def build_lca_table(n: int, adj: list[list[tuple[int, int]]], root: int = 1) -> tuple[list[int], list[int], list[list[int]]]:
    """BFS 遍历树，返回每个节点的深度、到根距离以及倍增祖先表。"""
    depth = [0] * (n + 1)
    dist = [0] * (n + 1)
    up = [[0] * LOGN for _ in range(n + 1)]
    visited = [False] * (n + 1)

    queue = [root]
    visited[root] = True
    head = 0
    while head < len(queue):
        u = queue[head]
        head += 1
        for v, w in adj[u]:
            if not visited[v]:
                visited[v] = True
                depth[v] = depth[u] + 1
                dist[v] = dist[u] + w
                up[v][0] = u
                for k in range(1, LOGN):
                    up[v][k] = up[up[v][k - 1]][k - 1]
                queue.append(v)

    return depth, dist, up


def query_lca(u: int, v: int, depth: list[int], up: list[list[int]]) -> int:
    """求节点 u 和 v 的最近公共祖先 (LCA)。"""
    if depth[u] < depth[v]:
        u, v = v, u

    diff = depth[u] - depth[v]
    for k in range(LOGN):
        if (diff >> k) & 1:
            u = up[u][k]

    if u == v:
        return u

    for k in range(LOGN - 1, -1, -1):
        if up[u][k] != up[v][k]:
            u = up[u][k]
            v = up[v][k]

    return up[u][0]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data, None)
    if n is None:
        return
    m = next(data)

    adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v, w = next(data), next(data), next(data)
        adj[u].append((v, w))
        adj[v].append((u, w))

    depth, dist, up = build_lca_table(n, adj, root=1)

    out: list[str] = []
    for _ in range(m):
        u, v = next(data), next(data)
        lca = query_lca(u, v, depth, up)
        ans = dist[u] + dist[v] - 2 * dist[lca]
        out.append(str(ans))

    sys.stdout.write('\n'.join(out) + '\n')


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115/**
 * 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-05 08:03
 * update_at: 2026-10-05 08:03
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 10005;
const int LOGN = 16; // 2^15 = 32768 > 10^4，15 级祖先足够

int n, m;
// 链式前向星存树：边是双向的，所以边数组开两倍
int head[MAXN], nxt[2 * MAXN], to[2 * MAXN], edge_cnt;
ll edge_w[2 * MAXN]; // 每条边的权值

int depth[MAXN]; // depth[u] 表示节点 u 的深度（根为 1，深度 0）
ll dist_root[MAXN]; // dist_root[u] 表示节点 u 到根节点的路径权值和
int up[MAXN][LOGN]; // up[u][k] 表示节点 u 的第 2^k 级祖先
bool visited[MAXN]; // BFS 时防止往父节点方向走回头路

int que[MAXN]; // BFS 用手写队列

// 加一条 u -> v、权值为 w 的无向边。
void add_edge(int u, int v, ll w) {
    edge_cnt++;
    to[edge_cnt] = v;
    edge_w[edge_cnt] = w;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// 从根节点 1 开始 BFS，预处理深度、到根距离和倍增祖先数组。
void bfs_init() {
    int qhead = 1, qtail = 1;
    que[qtail] = 1;
    visited[1] = true;
    depth[1] = 0;
    dist_root[1] = 0;

    while (qhead <= qtail) {
        int u = que[qhead];
        qhead++;
        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            if (visited[v]) continue; // 树上只有父节点被访问过
            visited[v] = true;
            depth[v] = depth[u] + 1;
            dist_root[v] = dist_root[u] + edge_w[i];
            up[v][0] = u; // 第 2^0 = 1 级祖先就是父节点
            // 倍增转移：先跳 2^(k-1) 步，再跳 2^(k-1) 步
            for (int k = 1; k < LOGN; k++) {
                up[v][k] = up[up[v][k - 1]][k - 1];
            }
            qtail++;
            que[qtail] = v;
        }
    }
}

// 求节点 u 和 v 的最近公共祖先 (LCA)。
int query_lca(int u, int v) {
    // 保证 u 是较深的节点
    if (depth[u] < depth[v]) {
        int t = u; u = v; v = t;
    }
    // 第一步：把 u 跳升到与 v 相同的深度
    int diff = depth[u] - depth[v];
    for (int k = 0; k < LOGN; k++) {
        if ((diff >> k) & 1) {
            u = up[u][k];
        }
    }
    if (u == v) return u; // 较浅节点本身就是 LCA
    // 第二步：两点同步从大到小试跳，祖先相同的层不跳
    for (int k = LOGN - 1; k >= 0; k--) {
        if (up[u][k] != up[v][k]) {
            u = up[u][k];
            v = up[v][k];
        }
    }
    // 此时 u、v 的父节点就是 LCA
    return up[u][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    edge_cnt = 0;
    for (int i = 1; i <= n - 1; i++) {
        int x, y;
        ll k;
        cin >> x >> y >> k;
        add_edge(x, y, k);
        add_edge(y, x, k);
    }

    bfs_init();

    // dist[u] + dist[v] - 2 * dist[lca]：两条到根的路径减去重叠部分的两倍
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        int lca = query_lca(x, y);
        cout << dist_root[x] + dist_root[y] - 2 * dist_root[lca] << "\n";
    }

    return 0;
}

复杂度

时间复杂度：
- 建图与 BFS 预处理遍历所有边和点，并填充倍增数组，时间复杂度为 $O(n \log n)$ ；
- 共有 $m$ 次询问，单次倍增查询 LCA 时间复杂度为 $O(\log n)$ ，总查询时间复杂度为 $O(m \log n)$ ；
- 整体时间复杂度为 $O((n + m) \log n)$ 。在本题 $n \leqslant 10^4, m \leqslant 2 \times 10^4$ 的数据规模下，运算量在数十万次级别，执行耗时不足 0.1 秒，轻松通过。
空间复杂度：
- 邻接表占用 $O(n)$ 空间；
- 深度数组、距离数组与倍增数组 $up[n][16]$ 占用 $O(n \log n)$ 空间；
- 整体空间复杂度为 $O(n \log n)$ ，内存开销约为数十兆字节，远低于 128MB 限制。

总结

本题是树上两点距离与最近公共祖先（LCA）的经典结合。利用树上路径的可减性，将求两点距离转化为求点到根距离与 LCA 的差分运算。通过一次遍历预处理加上树上倍增，将单次查询复杂度从朴素遍历的 $O(n)$ 优化至 $O(\log n)$ ，是在线求解树上多点路径相关问题的基础范式。

「一本通 4.4 练习 1」Dis

目录

形式化题目

正解

思路

代码

复杂度

总结