「一本通 4.4 例 1」点的距离

形式化题目

给定一棵包含 $n$ 个节点的无权无向连通树 $T=(V, E)$ ，边权均为 $1$ 。给出 $Q$ 次查询，每次查询给定节点对 $(u, v)$ ，求 $u$ 与 $v$ 在树上的简单路径长度（即两点之间的最短边数 $\text{dist}(u, v)$ ）。

正解

思路

在一棵以节点 $1$ 为根的有根树中，任意两节点 $u$ 与 $v$ 之间的简单路径必定唯一通过它们的最近公共祖先 $\text{LCA}(u, v)$ 。

设 $\text{depth}[u]$ 为节点 $u$ 的深度（定义根节点的深度 $\text{depth}[1] = 1$ ），则节点 $u$ 到根节点的边数恰为 $\text{depth}[u] - 1$ 。从 $u$ 到 $v$ 的路径可以拆分为先由 $u$ 向上走到 $\text{LCA}(u, v)$ ，再从 $\text{LCA}(u, v)$ 向下走到 $v$ 两段：

$u$ 到 $\text{LCA}(u, v)$ 的边数为 $\text{depth}[u] - \text{depth}[\text{lca}]$ ；
$v$ 到 $\text{LCA}(u, v)$ 的边数为 $\text{depth}[v] - \text{depth}[\text{lca}]$ 。

因此，两点在树上的距离公式为：

\text{dist}(u, v) = \text{depth}[u] + \text{depth}[v] - 2 \cdot \text{depth}[\text{LCA}(u, v)]

计算距离的核心即转化为高效求解 $\text{LCA}(u, v)$ 。对于 $Q \leqslant 10^5$ 的在线询问，单次 $O(n)$ 暴力爬树会超时（ $O(Q \cdot n)$ ），采用二进制倍增法（Binary Lifting）：

倍增状态与转移：定义 $\text{up}[k][u]$ 表示节点 $u$ 沿父节点方向向上跳 $2^k$ 步所到达的祖先节点。
- 基础状态： $\text{up}[0][u] = \text{father}[u]$ ；
- 状态转移： $\text{up}[k][u] = \text{up}[k-1][\text{up}[k-1][u]]$ 。由于 $n \leqslant 10^5 < 2^{18}$ ，取步长上限 $k < 18$ 即可覆盖全树高度。
建树与预处理：使用广度优先搜索（BFS）自根节点 $1$ 层次遍历整棵树，确定每个节点的深度 depth 和直接父节点 $\text{up}[0][u]$ 。采用迭代 BFS 可避免在极限链状数据下递归调用爆栈。随后按 $k = 1, 2, \dots, 17$ 双重循环递推填充倍增表。
倍增查询 LCA：
- 设 $u$ 的深度不小于 $v$ （若 $\text{depth}[u] < \text{depth}[v]$ 则交换）；
- 计算深度差 $\Delta = \text{depth}[u] - \text{depth}[v]$ ，将其按二进制拆分，把 $u$ 提升到与 $v$ 相同的深度；
- 若此时 $u == v$ ，说明原先的 $v$ 即为 $u$ 的祖先，直接返回 $u$ ；
- 否则， $k$ 从 $17$ 逆序递减到 $0$ ：若 $\text{up}[k][u] \neq \text{up}[k][v]$ ，则两点同步向上跳跃至对应祖先。循环结束后，两点恰好停留在 LCA 的直接子节点处，最终答案即为 $\text{up}[0][u]$ 。

代码

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
87
88
89
90
91
92#!/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-05-22 19:17
# update_at: 2026-05-22 19:17

import sys

# 题目数据 n <= 10^5，树高最大为 10^5，二进制倍增步长取 18 即可满足 2^17 <= 10^5 < 2^18
MAX_LOG = 18


def build_tree(n: int, edges: list[tuple[int, int]]) -> tuple[list[int], list[list[int]]]:
    """通过 BFS 遍历树，返回每个节点的深度深度表与倍增祖先表 up[k][u]。"""
    adj: list[list[int]] = [[] for _ in range(n + 1)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    depth = [0] * (n + 1)
    up = [[0] * (n + 1) for _ in range(MAX_LOG)]

    # BFS 层次遍历定父子关系与深度，避免深递归爆栈
    depth[1] = 1
    queue = [1]
    order: list[int] = []
    for u in queue:
        order.append(u)
        for v in adj[u]:
            if v != up[0][u]:
                depth[v] = depth[u] + 1
                up[0][v] = u
                queue.append(v)

    # 倍增预处理 2^k 级祖先表
    for k in range(1, MAX_LOG):
        prev = up[k - 1]
        curr = up[k]
        for u in range(1, n + 1):
            curr[u] = prev[prev[u]]

    return depth, up


def get_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

    # 1. 提升较深节点至同一深度
    diff = depth[u] - depth[v]
    for k in range(MAX_LOG):
        if diff >> k & 1:
            u = up[k][u]

    if u == v:
        return u

    # 2. 同步向上倍增跳跃，直到两者的父节点相同
    for k in reversed(range(MAX_LOG)):
        if up[k][u] != up[k][v]:
            u, v = up[k][u], up[k][v]

    return up[0][u]


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    try:
        first = next(data)
    except StopIteration:
        return
    n = int(first)
    edges = [(int(next(data)), int(next(data))) for _ in range(n - 1)]

    depth, up = build_tree(n, edges)

    q = int(next(data))
    out: list[str] = []
    for _ in range(q):
        u, v = int(next(data)), int(next(data))
        lca = get_lca(u, v, depth, up)
        # 树上两点距离公式：dist(u, v) = depth[u] + depth[v] - 2 * depth[lca]
        dist = depth[u] + depth[v] - 2 * depth[lca]
        out.append(str(dist))

    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
116
117
118
119
120
121
122
123
124
125
126
127
128/**
 * 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 07:44
 * update_at: 2026-10-05 07:44
 */

// main.cpp：树上两点距离询问。
// 做法：BFS 求深度与父节点，倍增预处理 2^k 级祖先，单次询问 O(log n) 求 LCA，
// 再用公式 dist(u, v) = depth[u] + depth[v] - 2 * depth[lca] 得到距离。

#include <cstdio>
#include <queue>
using namespace std;

typedef long long ll;

const int MAXN = 100005; // n <= 10^5
const int MAXLOG = 18;   // 2^17 > 10^5，步长 18 层足够覆盖全树高度

// 链式前向星存树
struct Edge {
    int to;
    int next_edge;
};

Edge e[MAXN * 2]; // 无向边，正反各存一条
int head[MAXN];
int cnt_edge = 0;

int depth[MAXN];  // depth[u]：节点 u 的深度，根节点深度为 1
int up[MAXLOG][MAXN]; // up[k][u]：节点 u 沿父节点方向向上跳 2^k 步到达的祖先
bool vis[MAXN];   // BFS 时防止走回父节点
int n, q;

// 加一条无向边
void add_edge(int x, int y) {
    cnt_edge++;
    e[cnt_edge].to = y;
    e[cnt_edge].next_edge = head[x];
    head[x] = cnt_edge;
}

// BFS 建树：求每个点的深度和父节点 up[0][u]，迭代写法避免链状树递归爆栈
void bfs_build(int root) {
    queue<int> qu;
    qu.push(root);
    vis[root] = 1;
    depth[root] = 1;
    up[0][root] = 0; // 根节点没有父节点，跳 1 步出界记为 0

    while (!qu.empty()) {
        int u = qu.front();
        qu.pop();
        for (int i = head[u]; i != 0; i = e[i].next_edge) {
            int v = e[i].to;
            if (vis[v])
                continue;
            vis[v] = 1;
            depth[v] = depth[u] + 1;
            up[0][v] = u;
            qu.push(v);
        }
    }
}

// 倍增预处理：up[k][u] = up[k-1][ up[k-1][u] ]，即先跳 2^(k-1) 步再跳 2^(k-1) 步
void build_up_table() {
    for (int k = 1; k < MAXLOG; k++) {
        for (int u = 1; u <= n; u++) {
            up[k][u] = up[k - 1][up[k - 1][u]];
        }
    }
}

// 倍增求 u, v 的最近公共祖先（LCA）
int get_lca(int u, int v) {
    // 保证 u 是较深的那个点
    if (depth[u] < depth[v])
        swap(u, v);

    // 1. 把 u 按二进制拆分向上跳，提升到与 v 相同深度
    int diff = depth[u] - depth[v];
    for (int k = 0; k < MAXLOG; k++) {
        if ((diff >> k) & 1)
            u = up[k][u];
    }

    // 此时 u, v 同深度；u == v 说明 v 本来就是 u 的祖先
    if (u == v)
        return u;

    // 2. 从高位往低位试跳：只有当跳完 2^k 步后两点不同才跳，
    //    循环结束后 u, v 恰好停在 LCA 的两个不同子节点上
    for (int k = MAXLOG - 1; k >= 0; k--) {
        if (up[k][u] != up[k][v]) {
            u = up[k][u];
            v = up[k][v];
        }
    }
    return up[0][u]; // 再往上一格就是 LCA
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n - 1; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        add_edge(x, y);
        add_edge(y, x);
    }

    bfs_build(1);
    build_up_table();

    scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        int lca = get_lca(x, y);
        // 树上两点距离公式：u 到 LCA 的边数 + v 到 LCA 的边数
        // 深度最大 10^5，两深度之和约 2*10^5，int 不会溢出
        int dist = depth[x] + depth[y] - 2 * depth[lca];
        printf("%d\n", dist);
    }
    return 0;
}

复杂度

时间复杂度：
- BFS 建树与遍历：每条边与节点访问常数次，耗时 $O(n)$ 。
- 倍增数组预处理：遍历 $18 \times n$ 个状态，耗时 $O(n \log n)$ 。
- 单次 LCA 询问：对齐深度与同步上跳均至多执行 $18$ 步，耗时 $O(\log n)$ 。
- 回答 $Q$ 次询问总耗时 $O(Q \log n)$ 。
- 总时间复杂度为 $O((n + Q) \log n)$ 。
空间复杂度：
- 邻接表与深度表占用 $O(n)$ 空间。
- 倍增表占用 $O(n \log n)$ 空间。
- 总空间复杂度为 $O(n \log n)$ 。

总结

树上距离与 LCA 的转化：无权树上两点距离直接由深度表与最近公共祖先深度确定： $\text{dist}(u, v) = \text{depth}[u] + \text{depth}[v] - 2 \cdot \text{depth}[\text{lca}]$ ，将路径长度问题转化为树上祖先定位。
二进制倍增的稳定性：倍增法将单次搜索从 $O(n)$ 降为 $O(\log n)$ ，预处理与查询开销均衡，且逻辑均为数组随机访问，十分适合应对多组在线询问。

图示解析

下图以样例树结构说明询问 $(2, 6)$ 与 $(5, 6)$ 的最近公共祖先及路径：

graph TD
    1((1)) --- 2((2))
    1 --- 3((3))
    2 --- 4((4))
    2 --- 5((5))
    3 --- 6((6))

    classDef lcaNode fill:#ff9999,stroke:#333,stroke-width:2px;
    classDef queryNode fill:#99ccff,stroke:#333,stroke-width:2px;

    class 1 lcaNode;
    class 5,6 queryNode;

根节点为 $1$ （ $\text{depth}[1]=1$ ）。
询问 $(2, 6)$ ： $\text{depth}[2]=2, \text{depth}[6]=3$ 。最近公共祖先为节点 $1$ （ $\text{depth}[1]=1$ ），路径为 $2 \to 1 \to 3 \to 6$ ，边数为 $2 + 3 - 2 \times 1 = 3$ 。
询问 $(5, 6)$ ： $\text{depth}[5]=3, \text{depth}[6]=3$ 。最近公共祖先为节点 $1$ （ $\text{depth}[1]=1$ ），路径为 $5 \to 2 \to 1 \to 3 \to 6$ ，边数为 $3 + 3 - 2 \times 1 = 4$ 。