#include<bits/stdc++.h>
using namespace std;
int n,m,s,tot,bug;
int nxt[600000],first[600000],go[600000],Dep[600000],f[1200000][20];
void add(int u,int v)
{
	nxt[++tot]=first[u],first[u]=tot,go[tot]=v;
	nxt[++tot]=first[v],first[v]=tot,go[tot]=u;
}
void Deal_first(int u,int father)
{
	Dep[u]=Dep[father]+1;
	for(int i=0;i<=19;i++)
		f[u][i+1]=f[f[u][i]][i];
	for(int e=first[u];e;e=nxt[e])
	{
		int v=go[e];
		if(v==father)continue;
		f[v][0]=u;
		Deal_first(v,u);
	}
}
int lca(int x,int y)
{
	if(Dep[x]<Dep[y])swap(x,y);
	//cout<<"x="<<x<<" y="<<y<<endl;
	for(int i=20;i>=0;i--)
	{
		if(Dep[f[x][i]]>=Dep[y])x=f[x][i];
		if(x==y)return x;
	}
	//cout<<"2@ x="<<x<<" y="<<y<<endl;
	for(int i=20;i>=0;i--)
	{
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i],y=f[y][i];
			//cout<<"x="<<x<<" y="<<y<<endl;
		}
	}
	return f[x][0];
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y);
	}
	Deal_first(s,0);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		cout<<lca(a,b)<<endl;
	}
	return 0;
}

举下为例

| x | y | | :----------- | :----------- | :----------- | | 10 | 9 | | 3 | 1 | | 8 | 2 | | 3 | 8 | | 7 | 3 | | 5 | 9 | | 8 | 5 | | 8 | 6 | | 4 | 6 |

BUG：当跳到a=6，b=1时 会跳到x=0或y=0