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

小橘子🍊

2026-07-31 19:42:14

发布于：福建

15阅读

0回复

0点赞

一、什么是LCA

最近公共祖先（Lowest Common Ancestor）：对于有根树上的两个节点 u 和 v，它们的 LCA 是深度最大的公共祖先节点。

例如：

根节点为 1

u = 4，v = 5，它们的 LCA 是 2

u = 4，v = 6，它们的 LCA 是 1

LCA 是树论中最基础也是最重要的算法之一，广泛应用于树上路径查询、树上差分等问题。
二、倍增法核心思想

倍增法是一种高效的在线查询算法，核心思路是预处理每个节点向上跳 2^k 步到达的祖先节点。
关键定义

设 fa[i][j] 表示节点 i 向上跳 2^j 步到达的祖先节点。

fa[i][0] = i 的父节点

fa[i][j] = fa[fa[i][j-1]][j-1]

即：向上跳 2^j 步 = 先向上跳 2^(j-1) 步，再跳 2^(j-1) 步。
预处理（BFS 版本）

void maketree() {
    fa[s][0] = s;
    queue<int> q;
    q.push(s);
    dep[s] = 1;
    while(q.size()) {
        int r = q.front();
        q.pop();
        for(int j : v[r]) {
            if(!fa[j][0]) {
                fa[j][0] = r;
                dep[j] = dep[r] + 1;
                q.push(j);
            }
        }
    }
}

倍增表初始化

void init() {
    for(int j = 1; j < 20; j++) {
        for(int i = 1; i <= n; i++) {
            fa[i][j] = fa[fa[i][j-1]][j-1];
        }
    }
}

LCA 查询

int lca(int u, int v) {
    if(u == v) return u;
    if(dep[u] < dep[v]) swap(u, v);
    
    // 将 u 提升到与 v 同一深度
    int d = dep[u] - dep[v], cnt = 0;
    while(d) {
        if(d & 1) u = fa[u][cnt];
        cnt++;
        d /= 2;
    }
    
    if(u == v) return u;
    
    // 一起向上跳
    for(int i = 19; i >= 0; i--) {
        if(fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    
    return fa[u][0];
}

三、完整模板代码

#include<bits/stdc++.h>
using namespace std;

int n, m, s, x, y, a, b;
int fa[500005][20], dep[500005];
vector<int> v[500005];

void maketree() {
    fa[s][0] = s;
    queue<int> q;
    q.push(s);
    dep[s] = 1;
    while(q.size()) {
        int r = q.front();
        q.pop();
        for(int j : v[r]) {
            if(!fa[j][0]) {
                fa[j][0] = r;
                dep[j] = dep[r] + 1;
                q.push(j);
            }
        }
    }
}

void init() {
    for(int j = 1; j < 20; j++) {
        for(int i = 1; i <= n; i++) {
            fa[i][j] = fa[fa[i][j-1]][j-1];
        }
    }
}

int lca(int u, int v) {
    if(u == v) return u;
    if(dep[u] < dep[v]) swap(u, v);
    
    int d = dep[u] - dep[v], cnt = 0;
    while(d) {
        if(d & 1) u = fa[u][cnt];
        cnt++;
        d /= 2;
    }
    
    if(u == v) return u;
    
    for(int i = 19; i >= 0; i--) {
        if(fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    
    return fa[u][0];
}

int main() {
    cin >> n >> m >> s;
    for(int i = 1; i < n; i++) {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    maketree();
    init();
    while(m--) {
        cin >> x >> y;
        cout << lca(x, y) << endl;
    }
    return 0;
}

四、时间复杂度

操作	时间复杂度	说明
预处理 BFS	O(n)	遍历每个节点一次
倍增表初始化	O(n log n)	每个节点递推 log n 个祖先
单次 LCA 查询	O(log n)	最多跳 log n 次

五、常见变形

求两点距离

int dist(int u, int v) {
    int l = lca(u, v);
    return dep[u] + dep[v] - 2 * dep[l];
}

判断一个点是否在另一个点的子树中

bool is_ancestor(int u, int v) {
    // 判断 u 是否是 v 的祖先
    return dfn[u] <= dfn[v] && dfn[v] <= dfn[u] + sz[u] - 1;
}

求两点路径上的第 k 个节点

int kth_node(int u, int v, int k) {
    int l = lca(u, v);
    int dist = dep[u] + dep[v] - 2 * dep[l] + 1;
    if(k <= dep[u] - dep[l] + 1) {
        // 从 u 往上跳 k-1 步
        return jump(u, k - 1);
    } else {
        // 从 v 往上跳 dist - k 步
        int step = dist - k;
        return jump(v, step);
    }
}

六、注意事项

LOG 取值：通常取 20（n <= 5e5）或 25（n <= 1e6），保证 2^LOG > n

数组大小：fa[MAXN][LOG+5]，第二维要 +5 防止越界

根节点的父节点设为自身：fa[s][0] = s，避免跳出树

dep 数组：dep[0] 通常设为 0，根节点 dep 设为 1

vector 存图：n 较大时建议用链式前向星优化

倍增从大到小：从 LOG 到 0 枚举，保证不会跳过头

七、练习题推荐

题目	难度	知识点
【模板】最近公共祖先（LCA）	普及/提高-	倍增 LCA
[GESP202506 六级] 最大因数	普及/提高-	数学,最近公共祖先
村庄问路	普及/提高-	求两点距离