用的倍增，scanf/printf，大部分思想都写在注释里面了

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

    const int maxn=500010;
    vector <int> e[maxn];//邻接表 
    int n;//结点个数
    int m;//询问的个数
    int s;//树根结点的序号
    int x,y;
    int dep[maxn];//记录每个节点深度 
    int fa[maxn][20];//记录i节点的2^j级祖先

    //预处理
    void dfs(int x,int father){//x为当前节点，father为它的父节点
        int size=e[x].size();//当前节点的相邻边数
        dep[x]=dep[father]+1; //x的深度是它父节点的深度+1
        fa[x][0]=father;
        for(int i=1;(1<<i)<=dep[x];++i){//1<<i==2^i，当2^i小于x的深度时，枚举他的祖先
            fa[x][i]=fa[fa[x][i-1]][i-1]; //fa数组的更新 
        }
        for(int i=0;i<size;++i){//枚举与他相邻的边
            if(e[x][i]!=father) {//如果不是他父节点
                dfs(e[x][i],x); //说明是子节点 继续dfs
            }
        } 
        return;
    }//处理完后根节点深度为0

    int LCA(int u,int v){
        int temp; //temp是两个点的深度度差
        if(dep[u]<dep[v]){ //默认u的深度大一些，否则将u与v交换
            swap(u,v);
        }
        temp=dep[u]-dep[v]; //计算深度差
        for(int i=0;(1<<i)<=temp;++i){//将u的深度变得与v相同，还是使用倍增的思想
            if((1<<i)&temp){//将深度差视为几个2^n的和，判断2^i是不是其中一个 (二进制数的性质 非常巧妙)
                u=fa[u][i]; //将u跳到他祖先的位置
                //这里由于二进制的性质 不需要重新计算temp 不会重复的
            }
        }//完成后u与v同深
        if(u==v){//如果u刚好等于v,即他们已经变成了同一个点               
            return u; //返回这个点的值,就是LCA
        }
        for(int i=dep[u];i>=0;--i){//假如n、v同深但是不重合，则一起往上跳
            if(fa[u][i]!=fa[v][i]){//不等于是为了防止跳过头 (同样是二进制数的巧妙性质,保证了不会卡住或者漏值)
                u=fa[u][i];
                v=fa[v][i];//往上跳
            }
        }//结束的时候会卡在他们LCA下面一层
        return fa[u][0];
    }

    int main(){
        memset(dep,-1,sizeof(dep));
        scanf("%d",&n);scanf("%d",&m);scanf("%d",&s);
        for(int i=1;i<n;++i){
            scanf("%d",&x); scanf("%d",&y);
            e[x].push_back(y);e[y].push_back(x);
        }//构建邻接表

        dfs(s,0);
        int ans;//结果
        for(int i=0;i<m;++i){
            scanf("%d",&x); scanf("%d",&y);
            ans=LCA(x,y);
            printf("%d\n",ans);
        }
        system("pause");
        return 0;
    }