两种LCA

LCA

LCA两种方法

1. 在线：倍增
2. 离线：Tarjan

倍增

#include<cstdio>
#include<cmath>
#define MAXN 700000+900
#define MAXM 1200000+900
using namespace std;
int anc[MAXN][33];
int n,m,root;
struct E{
    int next,to;
}edge[MAXM];
int head[MAXN],edge_num;
int depth[MAXN];
int logn;
void SWAP(int &x,int &y){
    int t=x;x=y;y=t;
}
void addedge(int x,int y){
    edge[++edge_num].next=head[x];
    edge[edge_num].to=y;
    head[x]=edge_num;
}
void DFS(const int &x,const int &y){
    int i;
    for(i=head[x];i;i=edge[i].next){
        if(edge[i].to!=y){
            anc[edge[i].to][0]=x;
            depth[edge[i].to]=depth[x]+1;
            DFS(edge[i].to,x);
        }
    }
}
void PRE(){
    int i,j;
    for(i=1;(1<<i)<=n;i++){
        for(j=1;j<=n;j++){
            if(anc[j][i-1]){
                anc[j][i]=anc[anc[j][i-1]][i-1];
            }
        }
    }
}
int LCA(int x,int y){
    if(depth[x]<depth[y])
        SWAP(x,y);
    int i,j;
    for(i=logn;i>=0;i--){
        if(depth[y]+(1<<i)<=depth[x])
            x=anc[x][i];
    }
    if(x==y) return x;
    for(i=logn;i>=0;i--){
        if(anc[x][i] && anc[x][i]!=anc[y][i]){
            x=anc[x][i];y=anc[y][i];
        }
    }
    return anc[x][0];
}
int main(){
    scanf("%d%d%d",&n,&m,&root);
    int i;int a,b;
    for(i=1;i<n;i++){
        scanf("%d%d",&a,&b);
        addedge(a,b);addedge(b,a);
    }
    DFS(root,0);
    PRE();
    logn=floor(log(n)/log(2));
    for(i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        printf("%d\n",LCA(a,b));
    }
    return 0;
}

Tarjan

方法：DFS，从最下层把节点加入并查集，如果询问的两个端点都出现在并查集中(首次)，就可以记录答案啦，就是并查集中的fa

#include<cstdio>
#include<algorithm>
#define MAXN 600000
using namespace std;
struct E{
    int next,to,id;
}edge[2*MAXN],ask[2*MAXN];
int head[MAXN],edge_num,h1[MAXN],a_num;
int root;
bool vis[MAXN];
int fa[MAXN];
int ans[MAXN];
int n,m;
void addedge(int x,int y){
    edge[++edge_num].next=head[x];
    edge[edge_num].to=y;
    head[x]=edge_num;
}
void addask(int x,int y,int z){
    ask[++a_num].next=h1[x];
    ask[a_num].to=y;
    ask[a_num].id=z;
    h1[x]=a_num;
}
int Find(int x){
    if(fa[x]!=x) fa[x]=Find(fa[x]);
    return fa[x];
}
void LCA(int x){
    int i;
    vis[x]=1;
    for(i=head[x];i;i=edge[i].next){
        if(!vis[edge[i].to])
            LCA(edge[i].to),fa[edge[i].to]=x;
    }
    for(i=h1[x];i;i=ask[i].next){
        if(vis[ask[i].to])
            ans[ask[i].id]=Find(ask[i].to);
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&root);
    int i;int a,b;
    for(i=1;i<=n-1;i++){
        scanf("%d%d",&a,&b);
        addedge(a,b);
        addedge(b,a);
    }
    for(i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        addask(a,b,i);addask(b,a,i);
    }
    for(i=1;i<=n;i++)
        fa[i]=i;
    LCA(root);
    for(i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}