【模板】LCA树链剖分

#include<bits/stdc++.h>
#define MAX 500002
using namespace std;
int n,m,s,d[MAX],siz[MAX],son[MAX],top[MAX],fa[MAX];
vector<int>G[MAX];
void dfs1(int u)
{
    siz[u]=1;son[u]=0;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v==fa[u])continue;
        fa[v]=u;
        d[v]=d[u]+1;
        dfs1(v);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void dfs2(int u,int tp)
{
    top[u]=tp;
    if(son[u])dfs2(son[u],top[u]);
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v==fa[u]||v==son[u])continue;
        dfs2(v,v);
    }
}
int lca(int x,int y)
{
    for(;top[x]!=top[y];d[top[x]]>d[top[y]]?x=fa[top[x]]:y=fa[top[y]]);
    return d[x]<d[y]?x:y;
}
int main()
{
    int a1,a2;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&a1,&a2);
        G[a1].push_back(a2);
        G[a2].push_back(a1);
    }
    dfs1(s);
    dfs2(s,s);
    while(m--)
    {
        scanf("%d%d",&a1,&a2);
        printf("%d\n",lca(a1,a2));
    }
    return 0;
}