树剖RE求调

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define endll " "
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define lowbit(x) x&(-x)
#define fi first
#define se second
#define iv inline void
#define it inline int 
#define ib inline bool
#define fre(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
#ifndef ONLINE_JUDGE
#pragma GCC optimize(0)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#endif
using namespace std;
const int MAXN=500050;
const int INF=0x3f3f3f3f;
const int mod=998244353;
it gcd(int x,int y){return y==0?x:gcd(y,x%y);}
it lcm(int x,int y){return x/gcd(x,y)*y;}
it max(int x,int y){return x>y?x:y;}
it min(int x,int y){return x<y?x:y;}
it ksm(int x,int m,int mod) 
{
    int res=1,bas=x%mod;
    while(m)
    {
        if(m&1) res=(res*bas)%mod;
        bas=(bas*bas)%mod,m>>=1;
    }
    return res%mod;
}
int n,m,cnt,tot,ans,sum,l,r,x,y,z,head[MAXN],u,v,w,dep[MAXN],siz[MAXN],son[MAXN];
int top[MAXN],tim,fa[MAXN],root,dfn[MAXN];
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
struct edge
{
	int to,nxt;
}e[MAXN*2];
void add_edge(int u,int v)
{
	e[++tot].to=v;
	e[tot].nxt=head[u];
	head[u]=tot;
}
void dfs1(int u,int f)
{
	fa[u]=f;
	siz[u]=1;
	dep[u]=dep[f]+1;
	int ms=-1;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==f)
			continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>ms)
		{
			ms=siz[v];
			son[u]=v;
		}
	}
}
void dfs2(int u,int f)
{
	dfn[u]=++tim;
	top[u]=f;
	if(!son[u])
		return;
	dfs2(son[u],f);
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==f || v==son[u])
			continue;
		dfs2(v,v);
	}
}
int get_lca(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]>dep[top[v]])
			u=fa[top[u]];
		else
			v=fa[top[v]];
	}
	if(dep[u]>dep[v])
		return v;
	else
		return u;
}
signed main()
{
	//fre("");
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> root;
	for(int i=1;i<n;i++)
	{
		cin >> u >> v;
		add_edge(u,v);
		add_edge(v,u);
	}
	dfs1(root,0);
	dfs2(root,root);
	for(int i=1;i<=m;i++)
	{
		cin >> u >> v;
		cout<<get_lca(u,v)<<endl;
	}
	return 0;
}