#include<bits/stdc++.h>
using namespace std;

int n,m,s,cnt,seq[500010],pos[500010],dep[500010],f[5000010][50],lg[500010];
bool vis[500010];
vector<int>son[500010];

inline void add(int x,int y){
	son[x].push_back(y);//建树 
}

inline void dfs(int now,int d){
	vis[now]=1;//判断是否已走过 
	pos[now]=++cnt;//now节点在欧拉序中第一次出现的位置 
	seq[cnt]=now;//建欧拉序 
	dep[cnt]=d;//节点深度 
	for(int i=0;i<son[now].size();i++){
		if(vis[son[now][i]]){
			continue;
		}
		dfs(son[now][i],d+1);
		seq[++cnt]=now;//建欧拉序 
		dep[cnt]=d;//节点深度 
	}
}

inline void ST(){
	lg[1]=0;
	for(int i=2;i<=cnt;i++){
		lg[i]=lg[i>>1]+1;//预处理 
	}
	for(int i=1;i<=cnt;i++){
		f[i][0]=i;//存节点下标 
	}
	for(int j=1;j<=lg[cnt];j++){
		for(int i=1;i<=cnt-(1<<j)+1;i++){
			if(dep[f[i][j-1]]<dep[f[i+(1<<(j-1))][j-1]]){
				f[i][j]=f[i][j-1];
			}
			else{
				f[i][j]=f[i+(1<<(j-1))][j-1];
			}
		}
	}
}

inline int RMQ(int l,int r){//查找最近公共祖先在欧拉序中的下标 
	int k=lg[r-l+1];
	if(dep[f[l][k]]<dep[f[r-(1<<k)+1][k]]){
		return f[l][k];
	}
	else{
		return f[r-(1<<k)+1][k];
	}
}

inline int LCA(int x,int y){
	int l=pos[x],r=pos[y];//x，y节点在欧拉序中第一次出现的位置 
	if(l>r){
		swap(l,r);
	}
	return seq[RMQ(l,r)];
}

int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m>>s;
	for(int i=1,x,y;i<n;i++){
		cin>>x>>y;
		add(x,y);add(y,x);
	}
	dfs(s,1);
	ST();
	for(int i=1,x,y;i<=m;i++){
		cin>>x>>y;
		cout<<LCA(x,y)<<endl;
	}
	return 0;
}

代码如上