rt，采用st表优化欧拉 代码部分

//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=500005;
int head[MAXN],oula[MAXN*4],numc,num[MAXN*2],fath[MAXN*2],re[MAXN*2],fir_oula[MAXN*2];
int lg[MAXN*2],maxn[MAXN][50];
struct stu{
	int next,to;
}sd[MAXN*2];
int cnt;
void dfs_mk(int x,int fa)
{
	num[x]=++numc;
	re[num[x]]=x;
	fath[x]=fa;
	for(int i=head[x];i;i=sd[i].next)
		if(sd[i].to-fa)
			dfs_mk(sd[i].to,x);
	return;
}
void dfs_bk(int x)
{
	if(fath[x])
		oula[++numc]=num[fath[x]];
	return;
}
void dfs_fr(int x)
{
	oula[++numc]=num[x];
	for(int i=head[x];i;i=sd[i].next)
		if(sd[i].to-fath[x])
		{
			dfs_fr(sd[i].to);
			dfs_bk(sd[i].to);
		}
	return;
}
void get_fir_oula()
{
	for(int i=1;i<=numc;i++)
		if(!fir_oula[oula[i]])
			fir_oula[oula[i]]=i;
	return;
}
signed main()
{
	//freopen("P3379_8.in","r",stdin);
	int n,m,s;
	cin>>n>>m>>s;
	int tmpx,tmpy;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&tmpx,&tmpy);
		for(int j=0;j<2;j++)
		{
			sd[++cnt].next=head[tmpx];
			sd[cnt].to=tmpy;
			head[tmpx]=cnt;
			swap(tmpx,tmpy);
		}
	}
	dfs_mk(s,0);
	numc=0;
	dfs_fr(s);
	lg[0]--;
	for(int i=1;i<=numc;i++)
		lg[i]=lg[i>>1]+1;
	for(int i=1;i<=numc;i++)
		maxn[i][0]=oula[i];
	for(int i=1;i<=lg[numc];i++)
        for(int j=1;j+(1<<i)-1<=numc;j++)
            maxn[j][i]=min(maxn[j][i-1],maxn[j+(1<<i-1)][i-1]);
    get_fir_oula();
	for(int i=0;i<m;i++)
	{
		scanf("%d%d",&tmpx,&tmpy);
		int ntmpx=fir_oula[num[tmpx]],ntmpy=fir_oula[num[tmpy]];
		if(ntmpx>ntmpy)
			swap(ntmpx,ntmpy);
		int mid=lg[ntmpy-ntmpx+1];
		printf("%d\n",re[min(maxn[ntmpx][mid],maxn[ntmpy-(1<<(mid))+1][mid])]);
	}
	return 0;
}