【模板】最近公共祖先（LCA）

形式化题目

给定一棵以 $s$ 为根的有根树，共 $n$ 个结点。给出 $m$ 个询问，每个询问给出两个结点 $u, v$ ，求它们的最近公共祖先 $\text{LCA}(u, v)$ ：既是 $u$ 的祖先又是 $v$ 的祖先、且深度最大的那个结点。不保证 $u \neq v$ 。

思路

先看一个可以直接验证想法的朴素解：

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/**
 * 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-08-12 22:28
 * update_at: 2026-08-12 22:28
 */
#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据暴力解，每次询问把 x 到根的路径整条标记出来，
// 再从 y 向上爬父亲，遇到的第一个已标记点就是最近公共祖先。
// 单次询问 O(n)，只适合小数据对拍和帮助理解题意。

const int MAXN = 105;

int n, m, root;
vector<int> g[MAXN];  // 邻接表
int fa[MAXN];         // fa[u] 表示 u 的父亲，根的父亲为 0
int vis[MAXN];        // 本次询问标记 x 的祖先路径

// BFS 求每个点的父亲（根的父亲为 0）。
void build_fa() {
    queue<int> que;
    que.push(root);
    fa[root] = 0;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (v == fa[u]) {
                continue;
            }
            fa[v] = u;
            que.push(v);
        }
    }
}

// 暴力求 x, y 的最近公共祖先。
int lca_brute(int x, int y) {
    // 从 x 一路向上走到根，沿途全部标记。
    while (x != 0) {
        vis[x] = 1;
        x = fa[x];
    }
    // 从 y 向上爬，第一个已被标记的点就是最近公共祖先。
    while (vis[y] == 0) {
        y = fa[y];
    }
    return y;
}

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

    cin >> n >> m >> root;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    build_fa();

    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        memset(vis, 0, sizeof(vis));
        cout << lca_brute(x, y) << '\n';
    }

    return 0;
}

brute.cpp 对每个询问把 x 到根的整条路径标记出来，再从 y 向上爬父亲，遇到的第一个被标记结点就是 LCA：公共祖先就是两条到根路径的交点。单次询问 $O(n)$ ，链形树上 $m$ 次询问 $O(nm)$ ，无法通过 $5\times10^5$ 的数据。

关键观察有两点：

LCA 一定是两个点的祖先：问题等价于「两条到根路径的交点里深度最大的点」，只要能快速向上跳，就能快速找 LCA；
任意上跳距离可拆成二进制位： $13 = 8 + 4 + 1$ ，只要会跳 $2^j$ 步，就能一次跳任意步。

于是预处理倍增祖先表： $up[u][j]$ 表示 $u$ 向上跳 $2^j$ 步到达的祖先，转移式

up[u][j] = up[up[u][j-1]][j-1]

先跳 $2^{j-1}$ 步、再从那跳 $2^{j-1}$ 步，合起来就是 $2^j$ 步。查询分两步走：先把较深点按深度差的二进制位向上跳，和另一个点同深；若此时两点相同，浅点本身就是 LCA；否则从高位到低位枚举 $j$ ，只有 $up[u][j] \neq up[v][j]$ 才一起跳（说明两点仍在 LCA 下方不同分支，安全），最后两点停在 LCA 的两个不同儿子上，父亲就是答案。

这张图是样例树（根为 4，2 与 1 是它的孩子，3 和 5 是 1 的孩子）：

观察要点： $\text{LCA}(3,5) = 1$ ，因为 3、5 同在 1 的子树； $\text{LCA}(2,4) = 4$ ，因为 2 的父亲就是 4。样例五个询问 $(2,4),(3,2),(3,5),(1,2),(4,5)$ 的答案分别是 $4,4,1,4,4$ ，读者可以对照树图逐条验证「先同深、再同步跳」两步。

代码

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/**
 * 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-08-12 22:28
 * update_at: 2026-08-20 10:38
 */
#include <bits/stdc++.h>
using namespace std;

// main.cpp：P3379 最近公共祖先（LCA）正式解，直接使用 rbook 模板 lca-binary-lifting。
// 与模板的唯一差别：模板用递归 dfs 预处理，本题 n 最大 5e5，递归可能爆栈，
// 预处理改用 BFS 迭代，depth / up / kth_ancestor / lca 接口与模板保持一致。

const int MAXN = 500005;
const int LOG = 20; // 2^20 > 5e5，覆盖最大深度差

using Graph = vector<int>;
Graph tree[MAXN]; // 全局邻接表数组：直接向 tree[u] 加无权边

// 倍增算法求最近公共祖先（LCA），接口与 rbook 模板 lca-binary-lifting 一致。
struct BinaryLCA {
    int depth[MAXN];       // depth[u] 表示节点 u 的深度（根深度为 1）
    int up[MAXN][LOG + 1]; // up[u][j] 表示节点 u 的 2^j 级祖先

    // BFS 从根出发，预处理每个节点的深度和 2^j 级祖先表。
    // 模板用递归 dfs，这里换 BFS 避免 5e5 链形树递归爆栈。
    void build(int root) {
        queue<int> que;
        que.push(root);
        depth[root] = 1;
        up[root][0] = 0; // 根的祖先视为 0 号虚点

        while (!que.empty()) {
            int u = que.front();
            que.pop();

            // 倍增转移：先跳 2^(j-1)，再从那里继续跳 2^(j-1)。
            for (int j = 1; j <= LOG; j++) {
                up[u][j] = up[up[u][j - 1]][j - 1];
            }

            for (int v : tree[u]) {
                if (v == up[u][0]) {
                    continue; // v 是父亲，跳过
                }
                up[v][0] = u;
                depth[v] = depth[u] + 1;
                que.push(v);
            }
        }
    }

    // 查询节点 u 的第 k 级祖先（向上跳 k 步），k 拆成二进制位逐层跳。
    int kth_ancestor(int u, int k) {
        for (int j = 0; j <= LOG; j++) {
            if (k & (1 << j)) {
                u = up[u][j];
            }
        }
        return u;
    }

    // 查询节点 a 和节点 b 的最近公共祖先。
    int lca(int a, int b) {
        if (depth[a] < depth[b]) {
            swap(a, b); // 保证 a 是较深节点
        }

        a = kth_ancestor(a, depth[a] - depth[b]);
        if (a == b) {
            return a; // b 本来就是 a 的祖先
        }

        // 从大到小一起跳，跳到 LCA 下面一层。
        for (int j = LOG; j >= 0; j--) {
            if (up[a][j] != up[b][j]) {
                a = up[a][j];
                b = up[b][j];
            }
        }
        return up[a][0];
    }
};

BinaryLCA solver;

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

    int n, m, root;
    cin >> n >> m >> root; // 注意输入顺序：n m root(s)

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    solver.build(root);

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        cout << solver.lca(a, b) << '\n';
    }

    return 0;
}

复杂度

时间：预处理 $O(n \log n)$ ，单次询问 $O(\log n)$ ，总计 $O((n+m)\log n)$ 。
空间：倍增表 $O(n \log n)$ ，邻接表与深度数组 $O(n)$ 。

总结

LCA 倍增的本质是把「一次向上跳一步」升级成「一次跳 $2^j$ 步」：预处理 2 的幂祖先表，查询时先对齐深度、再从高位到低位同步跳，保证跳后两点仍分居 LCA 两侧，最后返回父亲。rbook 的《倍增求 LCA》讲解了同一种 up / depth 模板（lca-binary-lifting）与「同深不丢答案」「从大到小跳正确」的完整证明，本解按该模板的接口实现，仅把递归 DFS 预处理换成 BFS，避免 $5\times10^5$ 规模递归爆栈。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18朴素暴力（brute.cpp）
  每次询问：标记 x 到根的整条路径，y 沿父亲向上爬找第一个标记点
  单次 O(n)，m 次询问 O(n*m)
        |
        | 瓶颈：最坏是链，一次询问要爬 O(n) 次父亲
        v
关键观察
  LCA 一定是两个点的祖先 => 到根的两条路径交点里深度最大的那个
  任意上跳距离可拆成二进制位：13 = 8 + 4 + 1
        |
        v
倍增预处理（main.cpp）
  depth[u] 深度；up[u][j] 表示 u 的 2^j 级祖先
  up[u][j] = up[up[u][j-1]][j-1]
  查询两步走：① 深点先提到同深  ② 从高位到低位同步跳，祖先不同才跳
        |
        v
复杂度 O((n + m) log n)，空间 O(n log n)

图中三条主线对应「暴力慢在哪」「用什么性质加速」「倍增如何兑现这个性质」。整个算法只有两个动作——先把深度对齐，再一起向上跳到 LCA 的下方一层，最后父亲就是答案；把「爬一步」升级成「跳 $2^j$ 步」就是倍增的全部内容。