WA在#13

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,L=19;
int n,m,s,x,y;
struct node{
	int to,next;
}a[N*2];
int pre[N*2],k;
int dep[N];
int f[N][L];
int lg[N];
void add(int u,int v){
	k++;a[k].to=v;a[k].next=pre[u];pre[u]=k;
}
void dfs(int x,int d){
	dep[x]=d;
	for (int i=pre[x];i;i=a[i].next) if (a[i].to!=f[x][0]) f[a[i].to][0]=x,dfs(a[i].to,d+1);
}
int main(){
	scanf("%d%d%d",&n,&m,&s);
	for (int i=2;i<=n;i++) lg[i]=lg[i/2]+1;
	for (int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	dfs(s,0);
	for (int j=1;j<=lg[n];j++) for (int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];
	while (m--){
		scanf("%d%d",&x,&y);
		if (x==y){printf("%d\n",x);continue;}
		if (dep[x]<dep[y]) swap(x,y);
		while (dep[x]>dep[y]) x=f[x][lg[dep[x]-dep[y]]];
		if (x==y){printf("%d\n",x);continue;}
		for (int i=lg[dep[x]]+1;i>=0;i--) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
		printf("%d\n",f[x][0]);
	}
	return 0;
}