非常详细的题解见洛谷，个人见解见代码

#include<bits/stdc++.h>
using namespace std;
#define N 500005

vector<int> G[N];//链树，以链上的元素为根节点的树
void add(int x,int y)
{
    G[x].push_back(y);
    G[y].push_back(x);
}

int fa[N][21]={0};
int depth[N]={0};
int n,m,s;

void proc()//预处理
{
    for(int k=1;k<=18;k++)//直接以最大常数算，反正也快不了多少
        for(int i=1;i<=n;i++)
            fa[i][k]=fa[fa[i][k-1]][k-1];//如果超过了，父节点就为零，即代表没有父节点
}

void build(int now,int fath)
{
    fa[now][0]=fath;
    for(int i=0;i<G[now].size();i++)
    {
        int next=G[now][i];
        if(next!=fath)//边不通来路
        {
            depth[next]=depth[now]+1;
            build(next,now);
        }
    }
}

int lca(int x,int y)
{
    if(depth[x]<depth[y])swap(x,y);

    for(int i=18;i>=0;i--)
        if(depth[fa[x][i]]>=depth[y])//最终得到的一定是相等的
            x=fa[x][i];//如果depth为零，代表该节点不存在

    //printf("%d,%d\n",x,y);
    if(x==y)return x;//如果不加这个就会返回他们的父节点，就不是最近祖先了
    //任意两个节点的父节点至少是s，所以fa[s]可以不用管
    for(int i=18;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
        {
            x=fa[x][i];
            y=fa[y][i];
        }//上浮到离lca最近的点

    return fa[x][0];
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);

    for(int i=1;i<=n-1;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }

    depth[s]=1;//要与不存在的节点分开来
    build(s,0);
    proc();

    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
    return 0;
}
526互联

P3379 【模板】最近公共祖先（LCA）

非常详细的题解见洛谷，个人见解见代码
