【算法模板】图论：最近公共祖先(LCA)

【算法模板】图论：最近公共祖先(LCA)

概念

最近公共祖先（Lowest Common Ancestor，简称LCA）问题通常出现在树或图的结构中，特别是在计算机科学和算法领域。这个问题的核心是找到两个节点在树中的共同祖先，且这个祖先的深度（或者说高度）是最小的。

在算法中，我们通常使用以下步骤来找到两个节点的LCA：

1. 树的遍历：首先，我们需要遍历整棵树，记录每个节点的深度和父节点信息。这通常通过深度优先搜索（DFS）实现。
2. 初始化信息：在遍历过程中，我们为每个节点存储它的深度和一系列的父节点。这些父节点可以快速帮助我们跳转到更高级别的祖先。
3. 对齐深度：当我们需要找到两个节点A和B的LCA时，我们首先确保A在B的上面或者B在A的上面。这通常通过比较它们的深度来实现。
4. 二进制提升：利用之前存储的父节点信息，我们可以快速跳转到更高的祖先。这就像是使用二进制来加速我们的搜索过程。
5. 查找LCA：一旦两个节点的深度对齐，我们就可以通过比较它们的父节点来找到共同的祖先。如果父节点相同，我们就继续向上查找；如果不同，我们就沿着树向上跳转，直到找到共同的祖先。
6. 返回结果：最终，我们找到的共同祖先就是LCA。

模板

struct Tree {
    int n;
    vector<vector<int>> ver, val;
    vector<int> lg, dep;
    Tree(int n) {
        this->n = n;
        ver.resize(n + 1);
        val.resize(n + 1, vector<int>(30));
        lg.resize(n + 1);
        dep.resize(n + 1);
        for (int i = 1; i <= n; i++) { //预处理 log
            lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
        }
    }
    void add(int x, int y) { // 建立双向边
        ver[x].push_back(y);
        ver[y].push_back(x);
    }
    void dfs(int x, int fa) {
        val[x][0] = fa; // 储存 x 的父节点
        dep[x] = dep[fa] + 1;
        for (int i = 1; i <= lg[dep[x]]; i++) {
            val[x][i] = val[val[x][i - 1]][i - 1];
        }
        for (auto y : ver[x]) {
            if (y == fa) continue;
            dfs(y, x);
        }
    }
    int lca(int x, int y) {
        if (dep[x] < dep[y]) swap(x, y);
        while (dep[x] > dep[y]) {
            x = val[x][lg[dep[x] - dep[y]] - 1];
        }
        if (x == y) return x;
        for (int k = lg[dep[x]] - 1; k >= 0; k--) {
            if (val[x][k] == val[y][k]) continue;
            x = val[x][k];
            y = val[y][k];
        }
        return val[x][0];
    }
    int clac(int x, int y) { // 倍增查询两点间距离
        return dep[x] + dep[y] - 2 * dep[lca(x, y)];
    }
    void work(int root = 1) { // 在此初始化
        dfs(root, 0);
    }
};

例题

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

P3379 【模板】最近公共祖先

#include 
using namespace std;

const int N=5e5+5;
vector<int> tree[N];
int parent[N][20];
int depth[N];

void dfs(int nowp,int prev){
    depth[nowp]=depth[prev]+1;
    parent[nowp][0]=prev;
    for(int i=1;i<20;i++)
        parent[nowp][i]=parent[parent[nowp][i-1]][i-1];
    for(int next:tree[nowp]){
        if(next==prev)continue;
        dfs(next,nowp);
    }
}

int find(int u,int v){
    if(depth[u]<depth[v])swap(u,v);
    for(int i=19;~i;i--) {
        if (depth[u] - (1 << i) >= depth[v])u = parent[u][i];
    }
    if(u==v)return u;
    for(int i=19;~i;i--){
        if(parent[u][i]==parent[v][i])continue;
        u=parent[u][i],v=parent[v][i];
    }
    return parent[v][0];
}

int main(){
    int n,m,s;cin>>n>>m>>s;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    dfs(s,0);
    while(m--){
        int u,v;cin>>u>>v;
        cout<<find(u,v)<<endl;
    }
}

最近公共祖先LCA查询

最近公共祖先LCA查询 - 蓝桥云课 (lanqiao.cn)

#include 
using namespace std;

int main(){
    //-----存树-----
    int n;cin>>n;
    vector<vector<int>> tree(n+1);
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        tree[u].emplace_back(v);
        tree[v].emplace_back(u);
    }
    //-----初始化-----
    const int t=ceil(log2(n));
    vector<int> depth(n+1);
    vector<vector<int>> fa(n+1,vector<int>(t));
    //-----深度与父节点-----
    function<void(int,int)> dfs=[&](int nowp,int prev){
        depth[nowp]=depth[prev]+1;
        fa[nowp][0]=prev;
        for(int i=1;i<t;i++)fa[nowp][i]=fa[fa[nowp][i-1]][i-1];
        for(int next:tree[nowp]){
            if(next==prev)continue;
            dfs(next,nowp);
        }
    };dfs(1,0);
    //-----lca实现-----
    auto lca=[&](int u,int v){
        if(depth[u]<depth[v])swap(u,v);
        for(int i=t-1;~i;i--)
            if(depth[u]-(1<<i)>=depth[v])u=fa[u][i];
        if(u==v)return u;
        for(int i=t-1;~i;i--){
            if(fa[u][i]==fa[v][i])continue;
            u=fa[u][i],v=fa[v][i];
        }
        return fa[u][0];
    };
    //------查询-----
    int Q;cin>>Q;
    while(Q--){
        int a,b;cin>>a>>b;
        cout<<lca(a,b)<<endl;
    }
    return 0;
}

版本分支

版本分支 - 蓝桥云课 (lanqiao.cn)

#include 
using namespace std;

int main(){
    int N,Q;cin>>N>>Q;
    vector<vector<int>> tree(N+1);
    for(int i=1;i<N;i++){
        int u,v;cin>>u>>v;
        tree[u].emplace_back(v);
    }
    const int t= ceil(log2(N));
    vector<int> depth(N+1);
    vector<vector<int>>fa(N+1,vector<int>(t));
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int nowp=q.front();
        q.pop();
        for(int next:tree[nowp]){
            depth[next]=depth[nowp]+1;
            fa[next][0]=nowp;
            for(int i=1;i<t;i++)fa[next][i]=fa[fa[next][i-1]][i-1];
            q.push(next);
        }
    }
    while(Q--){
        int x,y;cin>>x>>y;
        if(x==y){
            puts("YES");
            continue;
        }
        if(depth[y]<=depth[x]){
            puts("NO");
            continue;
        }
        for(int i=t-1;~i;--i)
            if(depth[y]-(1<<i)>=depth[x])
                y=fa[y][i];
        if(x==y)puts("YES");
        else puts("NO");
    }
    return 0;
}