求调

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
int fa[500010],dep[500010];
int hd[500010],nex[1000010],to[1000010],tot;
void add(int x,int y)
{
	++tot;
	to[tot]=y;
	nex[tot]=hd[x];
	hd[x]=tot;
}
void link(int x,int y){add(x,y);add(y,x);}
int anc[500010][20];
void dfs(int x,int fa)
{
	dep[x]=dep[fa]+1;anc[x][0]=fa;
	for(int i=1;i<19;++i)
		anc[x][i]=anc[anc[x][i-1]][i-1];
	for(int i=hd[x];i;i=nex[i])
		if(to[i]!=fa)
			dfs(to[i],fa);
}
int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=19;i>=0;--i)
		if(dep[anc[x][i]]>=dep[y])
			x=anc[x][i];
	if(x==y) return x;
	for(int i=19;i>=0;--i)
		if(anc[x][i]!=anc[y][i])
			x=anc[x][i],y=anc[y][i];
	return anc[x][0];
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1,a,b;i<=n-1;++i) 
    {
        cin>>a>>b;
        link(a,b);
    }
    dfs(s,0);
    for(int i=1,a,b;i<=m;++i)
    {
    	cin>>a>>b;
    	cout<<lca(a,b)<<endl;
    }
    return 0;
}