GESP 8级 · 最近公共祖先LCA

📖概念讲解

最近公共祖先（Lowest Common Ancestor, LCA）是树上两个节点的最近的公共祖先节点——即从根出发，同时是两个节点祖先、且深度最大的那个。

⚡ 核心思想：对于节点 u 和 v，它们的 LCA 就是从 u 到根的路径和从 v 到根的路径最后交汇的那个节点。两个节点一定在其 LCA 的不同子树中（或有一个就是 LCA 本身）。

常用的 LCA 算法有三种：

暴力法：先把深的节点往上跳到同一深度，再一起往上跳直到相遇。O(n) 每次查询。
倍增法（倍增+预处理）：预处理每个节点的 2^k 级祖先，查询时 O(log n)。最常考！
Tarjan 离线法：DFS + 并查集，一次遍历处理所有查询。O(n + q)。

GESP 8级主要掌握倍增法，理解 f[i][j] 表示"节点 i 的第 2^j 级祖先"这个关键定义。

💻代码示例

倍增法求 LCA（最常考写法）：

#include<bits/stdc++.h>
using namespace std;
const int N = 500010, LOG = 20;
vector<int> g[N];  // 邻接表存树
int dep[N], f[N][LOG]; // dep=深度, f[i][j]=节点i的第2^j级祖先
// DFS预处理：求深度 + 倍增表
void dfs(int u, int fa) {
    f[u][0] = fa;                // 第 2^0=1 级祖先就是直接父亲
    for (int j = 1; j < LOG; j++)
        f[u][j] = f[f[u][j-1]][j-1]; // 倍增核心：2^j = 2^(j-1) + 2^(j-1)
    for (int v : g[u])
        if (v != fa) {
            dep[v] = dep[u] + 1;    // 子节点深度 = 父+1
            dfs(v, u);
        }
}
// 把节点 x 向上跳 k 步
int lift(int x, int k) {
    for (int j = 0; j < LOG; j++)
        if (k >> j & 1)        // k的二进制第j位为1时跳2^j步
            x = f[x][j];
    return x;
}
// 求 u 和 v 的最近公共祖先
int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);  // 保证u更深
    u = lift(u, dep[u] - dep[v]);   // 第一步：把u跳到和v同一深度
    if (u == v) return u;           // 巧合就是LCA
    for (int j = LOG-1; j >= 0; j--) // 从大到小尝试跳
        if (f[u][j] != f[v][j]) {   // 还没相遇就跳
            u = f[u][j];
            v = f[v][j];
        }
    return f[u][0];               // 最后跳一步到LCA
}
int main() {
    int n = 7, m = 5, root = 1;
    // 建树：1-2, 1-3, 2-4, 2-5, 3-6, 3-7
    int edges[][2]={{1,2},{1,3},{2,4},{2,5},{3,6},{3,7}};
    for (auto& e : edges) {       // 无向边，双向加
        g[e[0]].push_back(e[1]);
        g[e[1]].push_back(e[0]);
    }
    dfs(root, 0);                 // 从根开始预处理
    printf("LCA(4,5) = %d\n", lca(4,5)); // 输出 2
    printf("LCA(4,6) = %d\n", lca(4,6)); // 输出 1
    printf("LCA(6,7) = %d\n", lca(6,7)); // 输出 3
    return 0;
}
# 输出: LCA(4,5)=2, LCA(4,6)=1, LCA(6,7)=3

🧩互动小测

❓ 倍增表 f[i][j] 的含义是？

❓ 在 lca 函数中，为什么要从大到小遍历 j（从 LOG-1 到 0）？

❓ 倍增法求 LCA 的预处理时间复杂度是？

🏋️动手练一练

📝 编程练习

给定一棵 n 个节点的树（1 为根），以及 q 次查询，每次查询两个节点 u 和 v，求它们的最近公共祖先。

输入格式：第一行 n, q；接下来 n-1 行每行两个整数表示边；再 q 行每行两个整数 u, v。
输出格式：q 行，每行一个整数表示 LCA。
提示：用倍增法预处理，然后对每个查询 O(log n) 求解。注意根节点的祖先设为 0，dfs 时判断 v != 0。

参考答案：

// 直接用上面的倍增模板即可
// 注意读入时 n-1 条边建无向图
// 每次查询调用 lca(u, v) 输出结果
int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dep[1] = 0;
    dfs(1, 0);  // 预处理
    while (q--) {
        int u, v; cin >> u >> v;
        cout << lca(u, v) << "\n";
    }
    return 0;
}

要点：预处理 O(n log n)，每次查询 O(log n)，总复杂度 O((n+q) log n)，足以处理 5×10^5 规模。

📝易错点提醒

根节点的父亲设为 0，不是 -1。dfs 时入口传 dfs(root, 0)，f[0][j] 自然为 0，不会越界。
倍增转移公式：f[u][j] = f[ f[u][j-1] ][j-1]，注意是"祖先的祖先"，别写成 f[u][j-1][j-1]。
lca 函数里先调平深度，再从大到小跳。如果先跳再调平，结果会错。
LOG 值要够大：n ≤ 5×10^5 时，LOG = 20 足够（2^19 = 524288）。太小会漏跳。
无向图建边要双向加，漏加一条边会导致树不连通。

📘最近公共祖先 LCA

📖概念讲解

💻代码示例

🧩互动小测

❓ 倍增表 f[i][j] 的含义是？

❓ 在 lca 函数中，为什么要从大到小遍历 j（从 LOG-1 到 0）？

❓ 倍增法求 LCA 的预处理时间复杂度是？

🏋️动手练一练

📝 编程练习

📝易错点提醒