未超时，但每个点耗时出奇的久。求调 https://www.luogu.com.cn/record/124414051

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n,m,s,tot,xi,yi,ai,bi,
	nex[maxn],to[maxn],head[maxn],f[maxn],ans[maxn];
bool vis[maxn];
vector<pair<int,int> >ask[maxn];//first存另一个，second存询问编号 
void add1(int u,int v){
	nex[++tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}
void add2(int u,int v,int i){
	ask[u].push_back({v,i});
	ask[v].push_back({u,i});
}
int find(int x){
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
void merge(int x,int y){
	f[find(x)]=find(y);
}
void dfs(int x){
	for(int i=head[x];i;i=nex[i]){
		int y=to[i];
		if(vis[y]) continue;
		vis[y]=1;
		dfs(y);
		merge(y,x);
	}
	for(int i=0;i<ask[x].size();i++)	
		if(vis[ask[x][i].first]) 
			ans[ask[x][i].second]=find(ask[x][i].first); 
}
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int main(){
	n=read();m=read();s=read();
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<n;i++){
		xi=read();yi=read();
		add1(xi,yi);add1(yi,xi);
	}
	for(int i=1;i<=m;i++){
		ai=read();bi=read();
		add2(ai,bi,i);
	}
	vis[s]=1;
	dfs(s);
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
}