https://www.luogu.com.cn/record/226091686

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+10;
int head[MAXN];
int to[MAXN],nxt[MAXN],top=1;
vector<pair<int,int> >q[MAXN];
int ans[MAXN];
bool vis[MAXN];
int fat[MAXN];
void add(int u,int v){
	to[top]=v;
	nxt[top]=head[u];
	head[u]=top;
	top++;
}
int fa(int x){
	if(fat[x]==x)return x;
	return fat[x]=fa(fat[x]);
}
void dfs(int u){
	fat[u]=u;
	vis[u]=1;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(!vis[v]){
			dfs(v);
			fat[v]=u;
		}
	}
	for(int i=0;i<q[u].size();i++){
		int v=q[u][i].first,k=q[u][i].second;
		if(vis[v]){
			ans[k]=fa(v);
		}
	}
} 
int main(){
	int n,m,s,x,y,a,b;
	cin>>n>>m>>s;
	for(int i=0;i<n-1;i++){
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	for(int i=0;i<m;i++){
		scanf("%d%d",&a,&b);
		q[a].push_back(make_pair(b,i));
		q[b].push_back(make_pair(a,i));
	}
	dfs(s);
	for(int i=0;i<m;i++){
		printf("%d\n",ans[i]);		
	}
	return 0;
}