倍增

#include<bits/stdc++.h>
using namespace std;
// #define fileio
#define IOS
void ___()
{
#ifdef fileio
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
#ifdef IOS
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #define endl '\n'
#endif
}
#define ll long long
const int _mxn=500000+5;
vector<int> g[_mxn];
void add(int u,int v){g[u].push_back(v);}
int n,rt;
int deep[_mxn],f[_mxn][20],lg;
void dfs(int u,int fa,int dep)
{
    deep[u]=dep;
    f[u][0]=fa;
    for(int i=1;i<=lg;i++)
        f[u][i]=f[f[u][i-1]][i-1];
    for(auto it:g[u])
    {
        if(it==fa)
            continue;
        dfs(it,u,dep+1);
    }
}
int lca(int x,int y)
{
    if(deep[x]<deep[y])
        swap(x,y);
    for(int i=lg;i>=0;i--)
        if(deep[f[x][i]]>=deep[y])
            x=f[x][i];
    if(x==y)
        return x;
    for(int i=lg;i>=0;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
int main()
{
    ___();
    int _;
    cin>>n>>_>>rt;
    lg=log2(n);
    for(int i=2;i<=n;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v),add(v,u);
    }
    dfs(rt,-1,0);
    while(_--)
    {
        int x,y;
        cin>>x>>y;
        cout<<lca(x,y)<<endl;
    }
    return 0;
}

样例输出：

0
4
1
0
0