如题

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll M=500005;
inline ll read()
{
	ll s=0,w=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') w=-1;c=getchar();}
	while(c>='0'&&c<='9') s=s*10+(c-'0'),c=getchar();
	return s*w;
}
inline void out(ll x)
{
	if(x==0){putchar('0');return;}
	ll k=x,len=0,c[10005];
	if(k<0) putchar('-'),k=-k;
	while(k) c[len++]=k%10+'0',k/=10;
	while(len--) putchar(c[len]);
}
ll n,m,s,f[M][25],dep[M],Log[M];
ll head[M],cnt;
struct wide
{
    int v,next;
} a[M<<1];
void dfs(int u,int fa)
{
    f[u][0]=fa;
    dep[u]=dep[fa]+1;
    for(int i=1; i<=Log[dep[u]]; i++)
    {
        ll pos=f[u][i-1];
        f[u][i]=f[pos][i-1];
    }
    for(int i=head[u]; i>0; i=a[i].next)
    {
        ll x=a[i].v;
        if(x!=fa)
        {
            dfs(x,u);
        }
    }
}
void init()
{
    for(int i=1; i<=n; i++)
    {
        Log[i]=Log[i-1]+(1<<Log[i]==i);
    }
    dfs(s,0);
}
ll LCA(int x,int y)
{
    if(dep[x]<dep[y])
    {
        swap(x,y);
    }
    while(dep[x]>dep[y])
    {
        int pos=Log[dep[x]-dep[y]]-1;
        x=f[x][pos];
    }
    if(x==y) return x;
    for(int k=Log[dep[x]]-1; k>=0; k--)
    {
        if(f[x][k]!=f[y][k])
        {
            x=f[x][k],y=f[y][k];
        }
    }
    return f[x][0];
}
void add(int x,int y)
{
    cnt++;
    a[cnt].v=y,a[cnt].next=head[x];
    head[x]=cnt;
}
int main()
{
    n=read(),m=read(),s=read();
    for(int i=1; i<n; i++)
    {
        ll x,y;
        x=read(),y=read();
        add(x,y);
        add(y,x);
    }
    init();
    while(m--)
    {
        ll x,y;
        x=read(),y=read();
        out(LCA(x,y));
        puts("");
    }
    return 0;
}