P3379 【模板】最近公共祖先（LCA）[Tarjan算法]

fan20090915 · 2023-04-24 13:48:47 · 个人记录

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
vector<int>e[N];
vector<pair<int,int>>query[N];
int fa[N],vis[N],ans[N],n,m,s;
int findfa(int x){
    return fa[x]=fa[x]==x?x:findfa(fa[x]);
}
void tarjan(int u){
    vis[u]=true;
    for(auto v:e[u]){
        if(!vis[v]){
            tarjan(v);
            fa[v]=u;
        }
    }for(auto ak:query[u]){
        int y=ak.first,i=ak.second;
        if(vis[y])ans[i]=findfa(y);
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n-1;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        e[x].push_back(y);
        e[y].push_back(x);  
    }for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        query[x].push_back({y,i});
        query[y].push_back({x,i});  
    }for(int i=1;i<=N;i++)fa[i]=i;
    tarjan(s);
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}