欧拉序

#include<bits/stdc++.h>
using namespace std;
int n,m,s,cnt,vis[500005],o[500005],dep[500005];
vector <int> G[500005];
struct stu
{
	int sx,deeep;
}h[1000010],st[1000010][20];
void dfs(int u,int fa)
{
	vis[u]=1;
	dep[u]=dep[fa]+1;
	h[++cnt].deeep=dep[u];
	h[cnt].sx=u;
	o[u]=cnt;
	for(auto v : G[u])
	{
		if(v!=fa&&!vis[v])dfs(v,u);
		h[++cnt].deeep=dep[u];
		h[cnt].sx=u;
		o[u]=cnt;
	}
}
void p()
{
	for(int i=1;i<=cnt;i++)st[i][0].deeep=h[i].deeep,st[i][0].sx=h[i].sx;
	int l=log2(cnt);
	for(int j=1;j<=l;j++)
	{
		for(int i=1;i+(1<<(j))-1<=cnt;i++)
		{
			if(st[i][j-1].deeep<st[i+(1<<(j-1))][j-1].deeep)
			st[i][j]=st[i][j-1];
			else st[i][j]=st[i+(1<<(j-1))][j-1];
		}
	}
}
//void print()
//{
//	cout<<'\n';
//	for(int i=1;i<=cnt;i++)
//	{
//		cout<<h[i].sx<<' ';
//	}
//	cout<<'\n';
//	for(int i=1;i<=cnt;i++)
//	{
//		cout<<h[i].deeep<<' ';
//	}
//	cout<<'\n';
//	for(int i=1;i<=cnt;i++)
//	{
//		int l=log2(cnt-i);
//		for(int j=0;j<=l;j++)
//		{
//			cout<<i<<' '<<i+(1<<j)<<' '<<st[i][j].deeep<<' '<<st[i][j].sx<<'\n';
//		}
//	}
//}
int main()
{
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(s,0);
	p();
	for(int i=1;i<=m;i++)
	{
		int a,b,d;
		scanf("%d%d",&a,&b);
		if(o[a]>o[b])swap(a,b);
		d=log2(o[b]-o[a]+1);
		if(st[o[a]][d].deeep<st[o[b]-(1<<d)][d].deeep)
		printf("%d\n",st[o[a]][d].sx);
		else printf("%d\n",st[o[b]-(1<<d)][d].sx);
	}
//	print();
 	return 0;
}