最近公共祖先模板（未完待续）

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int ret=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        ret=(ret<<1)+(ret<<3)+ch-'0';
        ch=getchar();
    }
    return ret*f;
}
int n,m,s,t,x,y;
int f[500005][20],d[500005];
int num,head[1000005];
queue<int> q;
struct edge
{
    int ver,nxt;
}e[1000005];
inline void adde(int u,int v)
{
    e[++num].ver=v;
    e[num].nxt=head[u];
    head[u]=num;
}
inline void bfs()
{
    d[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(register int i=head[x];i;i=e[i].nxt)
        {
            int y=e[i].ver;
            if(d[y])
                continue;
            d[y]=d[x]+1;
            f[y][0]=x;
            for(register int j=1;j<=t;j++)
                f[y][j]=f[f[y][j-1]][j-1];
            q.push(y);
        }
    }
}
inline int lca(int x,int y)
{
    if(d[x]<d[y])
        swap(x,y);
    for(register int i=t;i>=0;i--)
        if(d[f[x][i]]>=d[y])
            x=f[x][i];
    if(x==y)
        return y;
    for(register int i=t;i>=0;i--)
    {
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    }
    return f[x][0];
}
int main()
{
    n=read();
    m=read();
    s=read();
    t=(int)(log(n)/log(2))+1;
    for(register int i=1;i<n;i++)
    {
        x=read();
        y=read();
        adde(x,y);
        adde(y,x);
    }
    bfs();
    for(register int i=1;i<=m;i++)
    {
        x=read();
        y=read();
        printf("%d\n",lca(x,y));
    }
    return 0;
}