最近公共祖先 LCA（倍增法）

原理介绍

最近公共祖先 问题：在一棵有根树中，求两个节点 u 和 v 的公共祖先中深度最深的那个节点。

倍增法 是解决 LCA 问题的高效在线算法，时间复杂度 O(n log n) 预处理，O(log n) 单次查询。

核心思想

  1. 预处理深度：DFS 计算每个节点的深度 dep[u] 和直接父节点 p[0][u]。
  2. 倍增祖先：令 p[k][u] 表示节点 u 向上走 2^k 步到达的祖先。
    状态转移：p[k][u] = p[k-1][ p[k-1][u] ]
    （先向上走 2^(k-1) 步到 pp，再从 pp 向上走 2^(k-1) 步）
  3. 查询 LCA：
    • 先将较深的节点上提到与另一节点同深度，使用二进制拆分。
    • 若此时两节点相同，直接返回。
    • 否则从大到小尝试同时向上跳，保持两者不相遇，最终它们的父节点就是 LCA。

算法复杂度

  • 预处理：O(n log n)
  • 单次查询：O(log n)
  • 空间：O(n log n)（存储 p[k][u] 数组）

以下附上代码:

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
#include<bits/stdc++.h>
using namespace std;

int n, m, s, u, v, pp;
const int maxn = 100001, lg = 20;
int dep[maxn], p[lg][maxn];

//DFS 预处理 dep 与直接父节点 p[0][u]
void dfs(int u, int fa, const vector<vector<int>> &graph) {
    p[0][u] = fa;
    for (int i = 0; i < graph[u].size(); i++) {
        int v = graph[u][i];
        if (v != fa) {
            dep[v] = dep[u] + 1;
            dfs(v, u, graph);
        }
    }
}

//倍增LCA
int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v); // 保证 u 是较深节点
    // 将 u 上提到与 v 同深度
    for (int k = lg - 1; k >= 0; k--) {
        if (dep[u] - dep[v] >= (1 << k)) {
            u = p[k][u];
        }
    }
    if (u == v) return u;
    // 同时向上跳，直到 u 和 v 的父节点相同
    for (int k = lg - 1; k >= 0; k--) {
        if (p[k][u] != p[k][v]) {
            u = p[k][u];
            v = p[k][v];
        }
    }
    return p[0][u];
}

int main() {
    cin >> n >> m >> s;
    vector<vector<int>> graph(n + 1);
    for (int i = 0; i < n - 1; i++) {
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dep[s] = 1; // 设置根节点深度为1，避免dep[s]=-1导致的负数
    dfs(s, 0, graph);

    // 预处理p[k][u]
    for (int k = 1; k < lg; k++) {
        for (int i = 1; i <= n; i++) {
            pp = p[k - 1][i];
            if (pp != 0) p[k][i] = p[k - 1][pp];
            else p[k][i] = 0;
        }
    }
    // 查询
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        cout << lca(u, v) << '\n';
    }
    return 0;
}