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

封癫 · 2017-05-21 06:47:18 · 题解

Tarjan的lca题解

blog

Tarjan采用离线的方式回答问题，用深搜和并查集实现

因为树其实可以看成是图，所以就用链式前向星来存储

对它的子树遍历，如果已经访问过则得到最近公共祖先

如果未访问过则不变

最后在并查集里合并子树

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cctype>

long long read(){
    long long num=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')    f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        num=num\*10+ch-'0';
        ch=getchar();
    }
    return num\*f;
}

using namespace std;
int father[500010];
int head  [500010];
int qhead [500010];
int que   [500010];

struct Edge{
    int next,to;
}edge[1000010];

struct qEdge{
    int next,to,ans;
    qEdge(){ans=0;}
}q[1000010];

int cnt;
void add(int x,int y){
    cnt++;
    edge[cnt].to=y;
    edge[cnt].next=head[x];
    head[x]=cnt;
}

void qadd(int x,int y,int k){
    q[k].to=y;
    q[k].next=qhead[x];
    qhead[x]=k;
}

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

void unionn(int x,int y){
    x=find(x);y=find(y);
    father[y]=x;
}

void tarjan(int x){
    que[x]=1;
    for(int i=head[x];i;i=edge[i].next){
        int to=edge[i].to;
        if(!que[to]){
            tarjan(to);
            unionn(x,to);
        }
    }
    for(int i=qhead[x];i;i=q[i].next){
        int to=q[i].to;
        if(que[to]==2){
            q[i].ans=find(to);
            if(i%2)    q[i+1].ans=q[i].ans;
            else     q[i-1].ans=q[i].ans;
        }
    }
    que[x]=2;
}

int main(){
    int n=read(),m=read(),s=read();
    for(int i=1;i<n;++i){
        int x=read(),y=read();
        add(x,y);
        add(y,x);
        father[i]=i;
    }
    father[n]=n;
    for(int i=1;i<=m;++i){
        int x=read(),y=read();
        qadd(x,y,i\*2-1);
        qadd(y,x,i\*2);
    }
    tarjan(s);
    for(int i=1;i<=n;++i){
        printf("%d\n",q[i\*2].ans);
    }
    return 0;
}