tle球跳（悬6关）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5*1e5;
int n,m,s;
//int a[N+5];
int fa[N+5],dep[N+5],siz[N+5],zson[N+5],tp[N+5],dfn[N+5],seg[N+5],dfncnt;
vector<int>to[N+5];
void dfs1(int anc,int root)
{
	fa[root]=anc;
	dep[root]=dep[anc]+1; 
	int maxx=-1;
	for(auto v:to[root])
	{
		if(v==anc) continue;
		dfs1(root,v);
		if(siz[v]>maxx)
		{
			maxx=siz[v];
			zson[root]=v;
		}
		siz[root]+=siz[v];
	}
} 
void dfs2(int root,int topp) 
{
	tp[root]=topp;
	dfn[root]=++dfncnt;
//	seg[dfncnt]=root;
	if(zson[root]==0) return ;
    dfs2(zson[root],topp);
    for(int v:to[root])
    {
    	if(v==zson[root] || v==fa[root]) continue;
        dfs2(v,v);
	}
}
int ask_path(int x,int y)
{
    while(tp[x]!=tp[y])
	{
        if(dep[tp[x]]<dep[tp[y]])
			swap(x,y); //x更下面 
        x=fa[tp[x]];
    }
    if(dep[x]>dep[y])
		swap(x,y); //x更上面 
	return x;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=n-1;i++)
	{
		int u,v;
		cin>>u>>v;
		to[u].push_back(v);
		to[v].push_back(u);
	}
	dfs1(-1,s);
	dfs2(s,s);
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		cout<<ask_path(u,v)<<'\n';
	}
	return 0;
}