题解 | 【模板】最近公共祖先（LCA）

#include <iostream>
#include <ratio>
#include<unordered_map>
#include <utility>
#include <vector>
using namespace std;
// 方法1：DFS递归计算深度
void calculateDepthDFS(int node,int father, int currentDepth, 
                      vector<vector<int>>& up,vector<int>& depth,vector<vector<int>>& adj) {
    // 记录当前节点的深度
    up[0][node] =father;
    //求直接父节点
    depth[node]=currentDepth;
    if (adj[node].empty()) return;
    // 递归处理所有子节点
    for (int child : adj[node]) {
        calculateDepthDFS(child,node, currentDepth + 1, up,depth,adj);
    }
}
void DoubleCreationtable(int n,vector<vector<int>>& up,vector<int>& depth){
    for(int p=1;p<=19;p++){
        for(int u=1;u<=n;u++){
            if((2^p)<=depth[u]){
                up[p][u]=up[p-1][up[p-1][u]];
            }
        }
    }
}
//向上提升深度到同一深度
pair<int, int> liftDeepth(int u,int v,vector<vector<int>>& up,vector<int>& depth){
    pair<int,int> temp;
    if(depth[u]<depth[v]){
        int k=depth[v]-depth[u];
        int curpos=v;
        for(int i=0;i<=19;i++){
            bool bit=(k>>i)&1;
            if(bit){
                curpos=up[i][curpos];
            }
        }
        temp={u,curpos};
    }else if(depth[v]<depth[u]){
        int k=depth[u]-depth[v];
        int curpos=u;
        for(int i=0;i<=19;i++){
            bool bit=(k>>i)&1;
            if(bit){
                curpos=up[i][curpos];
            }
        }
        temp={curpos,v};
    }else{
        temp={u,v};
    }
    return temp;
}
//同步向上跳跃，找到最大的不相同
int findfather(int u,int v,vector<int>& depth,vector<vector<int>>& up){
    int i=19;
    for(;i>=0;i--){
        int tmp=1<<i;
        if((tmp>depth[u]-1)) continue;
        if(up[i][u]!=up[i][v]){
            u=up[i][u];
            v=up[i][v];
        }
    }
    return u;
}
int main() {
    int n,m,r;
    cin>>n>>m>>r;
    vector<vector<int>> adj(n+1);
    for(int i=0;i<n-1;i++){
        int x,y;
        cin>>x>>y;
        adj[x].push_back(y);
    }
    //预处理
    vector<int> depth(n+1);
    vector<vector<int>> up(20,vector<int>(n+1,0));
    calculateDepthDFS(r, r, 1, up, depth, adj);
    DoubleCreationtable(n, up, depth);
    while (m--) {
        int a,b;
        cin>>a>>b;
        pair<int, int> cur;
        if(depth[a] != depth[b]){
            cur=liftDeepth(a, b, up, depth);
        }else{
            cur={a,b};
        }
        if(cur.first==cur.second){
            cout<<cur.first<<endl;
        }else{
            int u=findfather(cur.first, cur.second, depth, up);
            cout<<up[0][u]<<endl;
        }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")