求调LCA模版 0pt

#include<bits/stdc++.h>
using namespace std;
void add(int x,int y);
int get(int x,int y);
void dfs(int p,int f);
int lca(int x,int y);

const int N=5e5+2;
int n,m,s,cnt,tot,h[N],dfn[N],st[N][20];
struct edge{
    int to,next;
}e[N<<1];

int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    dfs(s,0);
    for(int j=1;j<=log2(n);j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        cout<<lca(a,b)<<"\n";
    }
    return 0;
}
void add(int x,int y)
{
    e[++cnt].to=y;
    e[cnt].next=h[x];
    h[x]=cnt;
}
int get(int x,int y)
{return dfn[x]<dfn[y]?x:y;}
void dfs(int p,int f)
{
    st[dfn[p]=++tot][0]=f;
    for(int i=h[p];i;i=e[i].next)
        if(e[i].to!=f)
            dfs(e[i].to,p);
}
int lca(int x,int y)
{
    if(x==y) // 别忘了特判
        return x;
    if((x=dfn[x])>(y=dfn[y]))
        swap(x,y);
    int t=log2(y-x++);
    return get(st[x][t],st[y-(1<<t)+1][t]);
}