登录
← 返回首页 | 代码片段 › 4 树上问题 › 4.1 最近公共祖先LCA › 最近公共祖先LCA / 搜索
JSON MD

4.1 最近公共祖先LCA

最近公共祖先 lca
73 行
CPP JSON
【最近公共祖先(LCA)——倍增法(Binary Lifting)】 ▪ dfs(u, p) — 预处理 DFS:计算 depth[u](深度),parent[u][0]=p(父节点),递推 parent[u][k] = parent[parent[u][k-1]][k-1](2^k 级祖先),并建立子节点列表 ch[u] ▪ lca(u, v) — 查询 LCA: ① 将较深的 u 上提到与 v 同深度(从高到低枚举 k,若 depth[u]-(1<<k)≥depth[v] 则跳) ② 若 u==v 返回;否则从高到低同时上跳(parent[u][k]!=parent[v][k] 时跳) ③ 最终 parent[u][0] 即为 LCA 预处理 O(N log N),单次查询 O(log N)。适用于树上距离、路径信息查询、树上差分。
C++ 73 行 CPP
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 1e5 + 5;
const int LOG = 20;  // 2^20 > 1e5

vector<int> adj[MAXN];
vector<int> ch[MAXN];
int depth[MAXN];
int parent[MAXN][LOG];
int n, m, root;

// 预处理:计算每个节点的深度和2^k级祖先
void dfs(int u, int p) {
    depth[u] = depth[p] + 1;
    parent[u][0] = p;
    for (int k = 1; k < LOG; ++k) {
        parent[u][k] = parent[parent[u][k-1]][k-1];
    }
    for (int v : adj[u]) {
        if (v != p) {
            ch[u].push_back(v);
            dfs(v, u);
        }
    }
}

// 查找u和v的最近公共祖先
int lca(int u, int v) {
    if (depth[u] < depth[v]) {
        swap(u, v);
    }
    // 将u提到与v同一深度
    for (int k = LOG - 1; k >= 0; --k) {
        if (depth[u] - (1 << k) >= depth[v]) {
            u = parent[u][k];
        }
    }
    if (u == v) {
        return u;
    }
    // 同时向上跳
    for (int k = LOG - 1; k >= 0; --k) {
        if (parent[u][k] != parent[v][k]) {
            u = parent[u][k];
            v = parent[v][k];
        }
    }
    return parent[u][0];
}

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

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

    // 预处理
    dfs(root, 0);

    // lca查询
    // cout << lca(u, v);
    return 0;
}
已复制