倍增LCA

LCA(最近公共祖先)

倍增ＬＣＡ

倍增的思路就是利用二进制的性质存储状态

引入一个数组pre[i][j]表示ｉ节点的第$2^j$个祖先

如

pre[4][0]=3

pre[6][1]=2

pre[7][0]=2

pre[7][1]=1

我们可以发现一个很美妙的式子

pre[i][j]=pre[pre[i][j-1]][j-1]]

也就是

6的爷爷　＝　6的父亲的父亲

6的曾祖父　＝　6　的爷爷的爷爷

我们只要直到每个的父亲是谁，就可以处理出整个pre数组

如下图

然后要怎么找ＬＣＡ呢？ｘ，ｙ，默认d[x]>d[y]，这里指的是深度

那么肯定让x进行跳跃

for(int i=20;i>=0;i--){
    if(d[pre[x][i]]>=d[y]){
        x=pre[x][i];
    }
}

然后如果x==y了，那么ｘ就是公共祖先，否则就x,y一起跳

for(int i=20;i>=0;i--){
    if(pre[x][i]!=pre[y][i]){
        x=pre[x][i];
        y=pre[y][i];
    }
}

此处最后得到的x,y的父亲就是他们的公共祖先

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6+10;
struct Node{
    int to,next,val;
}edge[N];
int pre[N][25];
int d[N];
int head[N],cnt;
void add(int u,int v){
    cnt++;
    edge[cnt].next=head[u];
    edge[cnt].to=v;
    edge[cnt].val=0;
    head[u]=cnt;
}
void dfs(int u){
    for(int i=head[u];~i;i=edge[i].next){
        int v = edge[i].to;
        if(d[v]==0) {
            d[v] = d[u] + 1;
            pre[v][0] = u;
            dfs(v);
        }
    }
}
int lca(int x,int y){
    if(d[x]<d[y])swap(x,y);
    for(int i=20;i>=0;i--){
        if(d[pre[x][i]]>=d[y]){
            x=pre[x][i];
        }
    }
    if(x==y)return x;
    for(int i=20;i>=0;i--){
        if(pre[x][i]!=pre[y][i]){
            x=pre[x][i];
            y=pre[y][i];
        }
    }
    return pre[x][0];
}
int main(){
    int n,m,s;
    scanf("%d%d%d",&n,&m,&s);
    memset(head,-1,sizeof(head));
    for(int i=0;i<n-1;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        add(u,v);
        add(v,u);
    }
    pre[s][0]=0;
    d[s]=1;
    dfs(s);
    for(int i=1;i<=20;i++){
        for(int x=1;x<=n;x++){
            pre[x][i]=pre[pre[x][i-1]][i-1];
        }
    }
    for(int i=0;i<m;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        printf("%d\n",lca(u,v));
    }
}