倍增70ptsWA

#include<bits/stdc++.h>
using namespace std;
int n;
int deep[1000005],head[1000005],fa[1000005][26],cnt=0,dis[100005],maxk;
struct tree{
	int to,w,next;
}edge[1000005];
void add(int x,int y,int z){
	edge[++cnt].to=y;
	edge[cnt].w=z;
	edge[cnt].next=head[x];
	head[x]=cnt;
}
void dfs(int u){
	for(int i=head[u]; i!=-1; i=edge[i].next){
		int v=edge[i].to;
		if(deep[v]==0){
			dis[v]=dis[u]+edge[i].w;
			deep[v]=deep[u]+1;
			fa[v][0]=u;
			dfs(v);
		}
	}
	return;
} 
void prelca(int root){
	deep[root]=1;
	dfs(root);
	for(int k=1; k<=maxk; k++){
		for(int i=1; i<=n; i++){
			fa[i][k]=fa[fa[i][k-1]][k-1];
		}
	}
	return;
}
int lca(int x,int y){
	if(deep[x]<deep[y]) swap(x,y); 
	int dd=deep[x]-deep[y];
	for(int k=0;k<=maxk; k++){
		if(1<<k&dd){
			x=fa[x][k];
		}
	}
	if(x==y) return x;
	for(int k=maxk; k>=0; k--){
		if(fa[x][k]!=fa[y][k]){
			x=fa[x][k];
			y=fa[y][k];
		}
	} 
	return fa[x][0];
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
	memset(head,-1,sizeof head);
	int m,s;
	cin>>n>>m>>s;
	maxk=log2(n+1);
	for(int i=1; i<n; i++){
		int x,y;
		cin>>x>>y;
		add(x,y,0);
		add(y,x,0);
	}
	prelca(s);
	while(m--){
		int x,y;
		cin>>x>>y;
		cout<<lca(x,y)<<"\n";
	}
	return 0;
}