最近公共祖先笔记

请输入文本.

2026-07-12 21:38:59

发布于：上海

18阅读

0回复

0点赞

倍增法找 LCA

预处理：用 f[x][t] 表示结点 $x$ 向上走 $2^t$ 步的祖先结点编号

f[x][0] 为结点 $x$ 的父结点
当 $t≥1$ 时，利用 f[x][t]=f[f[x][t-1]][t-1]; 进行更新

for(int t=1;(1<<t)<=d[x];t++){
    f[x][t]=f[f[x][t-1]][t-1];
    if(t>maxt)maxt=t;
}

计算 LCA ：调整深度较大的结点和另一个结点相同深度

将深度差转为二进制形式
利用二进制形式中 1 的位置更新结点

if(d[x]>d[y]){
    int p=d[x]-d[y];
    for(int j=0;(1<<j)<=p;j++){
        if(p&(1<<j)){
            x=f[x][j];
        }
    }
}else{
    int p=d[y]-d[x];
    for(int j=0;(1<<j)<=p;j++){
        if(p&(1<<j)){
            y=f[y][j];
        }
    }
}

计算 LCA ：不断更新两个结点直到找到最近公共祖先

由于只能往根的方向走，不能往叶子方向走
所以当祖先结点不相同时才可以进行更新
因为相同祖先结点时不确定是否为最近的
相当于最后找到了最远的非公共祖先
再往上一步即可得到最近公共祖先

往上走的过程仍利用二进制实现，由于此时不知道具体要往上走几步，按照从大到小的顺序枚举每一位

if(x==y){
    return x;
}for(int j=maxt;j>=0;j--){
    if(f[x][j]!=f[y][j]){
        x=f[x][j];
        y=f[y][j];
    }
}
return f[x][0];

看题

P3379 一眼 __ __（（（

namespace HQ{
    #define int long long
    void init(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    int n,m,s,t=18;
    int d[550000];
    int f[550000][25];
    vector<int>l[550000];
    void find(int x){
        for(int t=1;(1<<t)<=d[x];t++){
            f[x][t]=f[f[x][t-1]][t-1];
        }for(int i=0;i<l[x].size();i++){
            int y=l[x][i];
            if(y==f[x][0]){
                continue;
            }f[y][0]=x;
            d[y]=d[x]+1;
            find(y);
        }
    }
    void Main(){
        init();
        cin>>n>>m>>s;
        for(int i=1;i<n;i++){
            int x,y;
            cin>>x>>y;
            l[x].push_back(y);
            l[y].push_back(x);
        }d[s]=1;
        find(s);
        for(int i=1;i<=m;i++){
            int x,y;
            cin>>x>>y;
            if(d[x]>d[y]){
                int p=d[x]-d[y];
                for(int j=0;(1<<j)<=p;j++){
                    if(p&(1<<j)){
                        x=f[x][j];
                    }
                }
            }else{
                int p=d[y]-d[x];
                for(int j=0;(1<<j)<=p;j++){
                    if(p&(1<<j)){
                        y=f[y][j];
                    }
                }
            }if(x==y){
                cout<<x<<'\n';
                continue;
            }for(int j=t;j>=0;j--){
                if(f[x][j]!=f[y][j]){
                    x=f[x][j];
                    y=f[y][j];
                }
            }cout<<f[x][0]<<'\n';
        }
        return;
    }
}