lca求调

#include<bits/stdc++.h>
#define N 500005
using namespace std;
int n,m,s;
struct data{
	int to,next;
}e[2*N];int head[N];
int dp[N][22],cnt,deep[N];
void read(int &x){
	char c=getchar(); 
	while(!(c<='9'&&c>='0'))c=getchar();
	while(c<='9'&&c>='0')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}
void add(int x,int y){
	e[++cnt]=(data){y,head[x]};head[x]=cnt;
}
void dfs(int x,int fa){
	deep[x]=deep[fa]+1;
	dp[x][0]=fa;
	for(int i=1;i<=19;i++){
		dp[x][i]=dp[dp[x][i-1]][i-1];
	}
	for(int i=head[x];i;i=e[i].next){
		if(e[i].to!=fa)dfs(e[i].to,x);
	}
}
int lca(int x,int y){
	if(deep[x]<deep[y])swap(x,y);
	for(int i=20;i;i--){
		if(deep[dp[x][i]]>=deep[y])x=dp[x][i];
	}
	if(x==y)return x;
	for(int i=20;i;i--){
		if(dp[x][i]!=dp[y][i]){
			x=dp[x][i];y=dp[y][i];
		}
	}
	return dp[x][0];
}
int main(){
	read(n);read(m);read(s);
	for(int i=1;i<=n-1;i++){
		int x=0,y=0;
		read(x);read(y);
		add(x,y);
		add(y,x);
	}
	dfs(s,0);
	for(int i=1;i<=m;i++){
		int a=0,b=0;
		read(a);read(b);
		printf("%d\n",lca(a,b));
	}
	return 0;
}