【模板】最近公共祖先

题目链接:https://www.luogu.org/problemnew/show/P3379

$Tarjan$:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN=500005;

int n,m,x,y,np,root;
int f[MAXN],ans[MAXN];
int h1[MAXN],h2[MAXN];
bool vis[MAXN];
struct rpg{
    int li,nx,id;
}a1[MAXN<<1],a2[MAXN<<1];

void add1(int ls,int nx){
    a1[++np]=(rpg){h1[ls],nx};
    h1[ls]=np;
}void add2(int ls,int nx,int id){
    a2[++np]=(rpg){h2[ls],nx,id};
    h2[ls]=np;
}

void init(){
    scanf("%d%d%d",&n,&m,&root);
    for(int i=1;i<=n;++i) f[i]=i;
    for(int i=1;i<n;++i){
        scanf("%d%d",&x,&y);
        add1(x,y);add1(y,x);
    }np=0;
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        add2(x,y,i);add2(y,x,i);
    }return;
}

int find(int x){
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}

void un(int a,int b){
    int fa=find(a),fb=find(b);
    if(fa!=fb) f[fa]=fb;
}

void tarjan(int x){
    vis[x]=1;
    for(int i=h1[x];i;i=a1[i].li){
        if(!vis[a1[i].nx]){
            tarjan(a1[i].nx);
            un(a1[i].nx,x);
        }
    }for(int i=h2[x];i;i=a2[i].li){
        if(vis[a2[i].nx]){
            ans[a2[i].id]=find(a2[i].nx);
        }
    }return;
}

void write(){
    for(int i=1;i<=m;++i){
        printf("%d\n",ans[i]);
    }return;
}

int main(){
    init();
    tarjan(root);
    write();
    return 0;
}

倍增:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN=500005;

int n,m,root,np,x,y;
int fa[MAXN][19],lg[MAXN],tp[MAXN];
int h[MAXN];
struct rpg{
    int li,nx;
}a[MAXN<<1];

void add(int ls,int nx){
    a[++np]=(rpg){h[ls],nx};
    h[ls]=np;
}

void init(){
    scanf("%d%d%d",&n,&m,&root);
    for(int i=1;i<n;++i){
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    }lg[n]=lg[n-1]+(1<<lg[n-1]==n);
    return;
}

void dfs(int x,int f,int deep){
    tp[x]=deep;
    fa[x][0]=f;
    for(int i=1;(1<<i)<=tp[x];++i){
        fa[x][i]=fa[fa[x][i-1]][i-1];
    }for(int i=h[x];i;i=a[i].li){
        if(a[i].nx!=f){
            dfs(a[i].nx,x,deep+1);
        }
    }return;
}

int getLCA(int x,int y){
    if(tp[x]<tp[y]) swap(x,y);
    while(tp[x]>tp[y]){
        x=fa[x][lg[tp[x]-tp[y]]-1];
    }if(x==y) return x;
    for(int i=lg[tp[x]];i>=0;--i){
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i];y=fa[y][i];
        }
    }return fa[x][0];
}

void solve(){
    while(m--){
        scanf("%d%d",&x,&y);
        printf("%d\n",getLCA(x,y));
    }return;
}

int main(){
    init();
    dfs(root,0,1);
    solve();
    return 0;
}

树链剖分:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN=500005;

int n,m,root,np,cnt,x,y;
int siz[MAXN],top[MAXN],tp[MAXN],id[MAXN];
int h[MAXN],sn[MAXN],fa[MAXN];
struct rpg{
    int li,nx;
}a[MAXN<<1];

void add(int ls,int nx){
    a[++np]=(rpg){h[ls],nx};
    h[ls]=np;
}

void init(){
    scanf("%d%d%d",&n,&m,&root);
    for(int i=1;i<n;++i){
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }return;
}

void dfs1(int x,int f,int deep){
    tp[x]=deep;
    siz[x]=1;
    fa[x]=f;
    int hwy=0;
    for(int i=h[x];i;i=a[i].li){
        if(a[i].nx!=f){
            dfs1(a[i].nx,x,deep+1);
            siz[x]+=siz[a[i].nx];
            if(siz[a[i].nx]>hwy){
                hwy=siz[a[i].nx];
                sn[x]=a[i].nx;
            }
        }
    }return;
}

void dfs2(int x,int tpx){
    top[x]=tpx;
    id[x]=++cnt;
    if(!sn[x]) return;
    dfs2(sn[x],tpx);
    for(int i=h[x];i;i=a[i].li){
        if(a[i].nx!=fa[x]&&a[i].nx!=sn[x]){
            dfs2(a[i].nx,a[i].nx);
        }
    }return;
}

int getLCA(int x,int y){
    while(top[x]!=top[y]){
        if(tp[top[x]]<tp[top[y]]) swap(x,y);
        x=fa[top[x]];
    }if(tp[x]>tp[y]) swap(x,y);
    return x;
}

void solve(){
    while(m--){
        scanf("%d%d",&x,&y);
        printf("%d\n",getLCA(x,y));
    }return;
}

int main(){
    init();
    dfs1(root,0,1);
    dfs2(root,root);
    solve();
    return 0;
}