题解

这里使用tarjan算法完成此题。运用离线思想。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,s,fa[N],ans[N];bool vis[N];
vector<int>g[N];vector<pair<int,int>>Q[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void dfs(int now){
    fa[now]=now;vis[now]=1;
    for(int nx:g[now]){
        if(vis[nx])continue;
        dfs(nx);
        fa[nx]=now;
    }
    for(auto [v,id]:Q[now]){
        if(!vis[v])continue;
        ans[id]=find(v);
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1,x,y;i<n;i++){
        scanf("%d%d",&x,&y);
        g[x].push_back(y);g[y].push_back(x);
    }
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        Q[x].push_back({y,i});Q[y].push_back({x,i});
    }
    dfs(s);
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}