RT.罕见的40分：

#include<bits/stdc++.h>
using namespace std;
struct node{
	int to,next;
}a[1000010];
int head[500010],dp[500010][20],dep[500010],Log[500010];
int cnt=0;
void add(int x,int y){
	a[++cnt].to=y;
	a[cnt].next=head[x];
	head[x]=cnt;
}
void dfs(int x,int fa){
	dp[x][0]=fa;
	dep[x]=dep[fa]+1;
	for(int i=1;i<=Log[dep[x]];i++){
		dp[x][i]=dp[dp[x][i-1]][i-1];
	}
	for(int i=head[x];i;i=a[i].next){
		int y=a[i].to;
		if(y!=dp[x][0]){
			dfs(y,x);
		}
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y]){
		swap(x,y);
	}
	while(dep[x]>dep[y]){
		x=dp[x][Log[dep[x]-dep[y]]];
	}
	if(x==y){
		return x;
	}
	for(int i=Log[dep[x]]-1;i>=0;i--){
		if(dp[x][i]!=dp[y][i]){
			x=dp[x][i],y=dp[y][i];
		}
	}
	return dp[x][0];
}
int main(){
	int n,q,s;
	cin>>n>>q>>s;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		if(u==v){
			continue;
		}
		add(u,v);
		add(v,u);
	}
	Log[0]=-1;
	for(int i=1;i<=n;i++){
		Log[i]=Log[i/2]+1;
	}
	dfs(s,0);
	while(q--){
		int a,b;
		cin>>a>>b;
		cout<<lca(a,b)<<endl;
	}
	return 0;
}