备战csp-s求调

#include<bits/stdc++.h>
using namespace std;
int n,m,s,dep[500005],lg[500005],f[500005][35];
vector<int> v[500005];
int lowbit(int i)
{
	return i & -i;
}
void dfs(int x,int fa)
{
//	cout<<x<<" "<<fa<<endl;
	for(register int i=0;i<v[x].size();++i)
	{
		int to=v[x][i];
		if(to==fa) continue;
		dep[to]=dep[x]+1,dfs(to,x);
	}
}
void find_fa(int x,int fa)
{
	f[x][0]=fa;
	for(register int i=1;i<=lg[dep[x]];++i)
		f[x][i]=f[f[x][i-1]][i-1];
	for(register int i=0;i<v[x].size();++i)
		if(fa!=v[x][i]) find_fa(v[x][i],x);
}
int serve(int x,int y)
{
//	cout<<11111<<endl;
	if(dep[x]<dep[y]) swap(x,y);
	while(dep[x]!=dep[y]) x=f[x][lg[dep[x]-dep[y]-1]];
//	cout<<x<<" "<<y<<endl;
	if(x==y) return x;
	for(register int i=lg[dep[x]];i>=0;--i)
		if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
//	cout<<f[x][0]<<endl;
	return f[x][0];
}
int main()
{
//	freopen("P3379_1.in","r",stdin);
//	freopen("a.out","w",stdout);
	scanf("%d%d%d",&n,&m,&s);
	for(register int i=1;i<n;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		v[x].push_back(y),v[y].push_back(x);
		lg[i]=lg[i-1]+(lowbit(i)==i);
	}
//	for(register int i=0;i<=100;++i)
//		cout<<lg[i]<<" ";
	dep[s]=1,dfs(s,0);find_fa(s,0);
	for(register int i=1;i<=m;++i)
	{
		int x,y;
		cin>>x>>y;
		cout<<serve(x,y)<<endl;
	}
	return 0;
}