【模板】LCA

#include<bits/stdc++.h>
using namespace std;
int head[2000000],d[500005],lg[500005],fa[500005][25],l,n,m,s,x,y;
struct node {
    int to,next;
} a[2000000];
inline void add(int from,int to) {
    a[++l].to=to;
    a[l].next=head[from];
    head[from]=l;
}
void dfs(int bh,int f)
{
    d[bh]=d[f]+1;
    fa[bh][0]=f;
    for(int i=1;pow(2,i)<=d[bh];i++)
        fa[bh][i]=fa[fa[bh][i-1]][i-1];
    for(int i=head[bh];i;i=a[i].next)
    {
        int y=a[i].to;
        if(y!=f)dfs(y,bh);
    }
}
int lca(int x,int y)
{
    if(d[x]<d[y])swap(x,y);
    while(d[x]>d[y])x=fa[x][lg[d[x]-d[y]]-1];
    if(x==y)return x;
    for(int i=lg[d[x]]-1;i>=0;i--)
        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(s,0);
    for(int i=1;i<=n;i++)
        lg[i]=lg[i>>1]+1;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
    return 0;
}