#include<bits/stdc++.h>
using namespace std;
int head[500020];
struct edge{
	int to;
	int next;
};
int a[500020];
edge point[1000020];
int deep[500020];
int fa[500020][20];
int n,m,s;
int action_(int x,int from){
	for(int i=head[x];i!=0;i=point[i].next){
		if(point[i].to!=from){
			deep[point[i].to]=deep[x]+1;
			fa[point[i].to][0]=x;
			action_(point[i].to,x);
		}
	}
}
int f(int i,int j){
	if(fa[i][j]!=0) return fa[i][j];
	else if(deep[i]-(1<<j)<=0) return fa[i][j]=-1;
	else return fa[i][j]=f(f(i,j-1),j-1);
}
int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=2*(n-1);i++){
		int x,y;
		scanf("%d%d",&x,&y);
		point[i].to=y;
		point[i].next=head[x];
		head[x]=i;
		i++;
		point[i].to=x;
		point[i].next=head[y];
		head[y]=i;
	}
	deep[s]=1;
	action_(s,s);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		if(deep[x]<=deep[y]) swap(x,y);
		for(int i=19;i>=0;i--){
			if(f(x,i)!=-1){
				if(deep[f(x,i)]>=deep[y]){
					x=f(x,i);
				}
			}
		}
		while(deep[x]>deep[y]) x=f(x,0);
		for(int i=19;i>=0;i--){
			if(f(x,i)!=f(y,i)){
				x=f(x,i);
				y=f(y,i);
			}
			if(f(x,0)==f(y,0)) break;
		}
		if(x!=y) printf("%d\n",f(x,0));
		else printf("%d\n",x);
	}
	return 0;
}

样例、第一个点本地过了，在线测12个点全TLE

求解