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

最近公共祖先 $(LCA)$ :在有根树的结构中，对于任意两个节点 $u$ 和 $v$ ,它们的最近公共祖先是指满足下面两个条件的节点 $p$ :

$p$ 同时是 $u$ 和 $v$ 的公共祖先(即 $p$ 在 $u$ 到根节点的路径上，也在 $v$ 到根节点的路径上)、
$p$ 是所有公共祖先中深度最大的节点("最近"的本质是距离u 和 v距离最近)

关键性质：

$LCA(u,v)$ 是 $u$ 到根节点的路径与 $v$ 到根节点的路径中第一个交点
这棵树里面 $u$ 到 $v$ 的的最短路径一定经过 $LCA(u,v)$ 并且 $LCA(u,v)$ 是这条最短路径中深度最小的节点
多个节点的最近公共祖先： $LCA(u,v,w)=LCA(LCA(u,v),w)$
如果 $u$ 是 $v$ 的祖先，则 $LCA(u,v) =u$ ；反之同理

$LCA$ 的常见使用场景：

计算树上两点间的距离： $dist(u,v)=depth[u]+depth[v]-2\times depth[LCA(u,v)]$ ，很好理解： $depth[u]$ 表示根节点到 $u$ 的距离， $dist[v]$ 表示根节点到 $v$ 的距离，两者重叠部分是根节点到 $LCA(u,v)$ 的距离，并且重复计算了两次，因此需要减去 $2\times depth[LCA(u,v)]$
可以判断树中 $u$ 和 $v$ 的关系，判断节点 $u$ 是否在 $v$ 的子树中，如果 $LCA(u,v)= v$ ,则 $u$ 在 $v$ 的子树中
很多树上问题需要对任意两点 $u$ ， $v$ 之间的路径经行操作，（如查询路径的最大值，最小值，求和等），而LCA是将路径拆分为两段的关键 $u\rightarrow v\Leftrightarrow u\rightarrow LCA(u,v)\rightarrow v$
辅助树形DP：在树形DP中，经常需要统计跨字数的路径信息，LCA可以帮助确定路径的公共祖先，从而划分状态转移范围

LCA模板：

定义 $st[i][j]$ 表示节点 $i$ 的 $2^{j}$ 级祖先（节点 $i$ 的1级祖先就是它的父节点，2级祖先就是父节点的父节点.......）

所以 $st[i][j]=st[st[i][j-1]][j-1]$

初始化每一个 $st[i][0]$ 就是节点 $i$ 的直接父节点，可以通过对整棵树的DFS求出每个节点的深度以及直接父节点：

void dfs(int u, int fa, int dep){
    depth[u] = dep;
    st[u][0] = fa;
    for(int v : adj[u]){
        if(v != fa) dfs(v, u, dep + 1);
    }
}

然后就是如何求任意两个节点 $u$ 和 $v$ 的最近公共最先 $LCA(u,v)$ 了：

首先节点 $u$ 和 $v$ 的深度可能不一样，为了方便处理，将深度大的设置为节点 $u$

if(depth[u] < depth[v]) swap(u, v);

然后需要将节点 $u$ 的深度慢慢减小深度至和 $v$ 相同：

int dif = depth[u] - depth[v];
for(int i = M - 1; i >= 0; i --){
    if((dif >> i) & 1) u = st[u][i];
}

现在 $u$ 和 $v$ 的深度变为相同了，如果此时 $u$ 和 $v$ 的值相同，那么直接返回节点 $v$ ，表示一开始的节点 $u$ 是在节点 $v$ 的子树里面(但是现在的 $u$ 和 $v$ 的值相同，所以返回节点 $u$ 和 $v$ 都可以)

如果 $u$ 和 $v$ 的值不相同，那么现在就是在同一深度，我们就可以慢慢的同时减少深度，如果某个 $i$ 时满足 $st[u][i]=st[v][i]$ ，说明 $u$ 和 $v$ 的第 $2^{j}$ 级祖先相同，即找到了一个公共祖先，但不一定是升读最大的，如果 $st[u][i]\ne st[v][i]$ ，那么我继续减少深度，最终的局面是 $st[u][0]=st[v][0]$ ,即 $u$ 和 $v$ 的直接父亲相同，那么这个 $st[u][0]$ 就是 $LCA(u,v)$

总代码：

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 5e5 + 10;
const int M = 20;

int n, m, s;
int st[N][M];
int depth[N];
vector<int> adj[N];

void dfs(int u, int fa, int dep){
    depth[u] = dep;
    st[u][0] = fa;
    for(int v : adj[u]){
        if(v != fa) dfs(v, u, dep + 1);
    }
}

int lca(int u, int v){
    if(depth[u] < depth[v]) swap(u, v);
    int dif = depth[u] - depth[v];
    for(int i = M - 1; i >= 0; i --){
        if((dif >> i) & 1) u = st[u][i];
    }
    if(u == v) return u;
    for(int i = M - 1; i >= 0; i --){
        if(st[u][i] != st[v][i]){
            u = st[u][i];
            v = st[v][i];
        }
    }
    return st[u][0];
}
signed main(){
    HelloWorld;
    
    cin >> n >> m >> s;
    for(int i = 1; i <= n - 1; i ++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }    
    dfs(s, s, 1);
    for(int j = 1; j < M; j ++){
        for(int i = 1; i <= n; i ++) st[i][j] = st[st[i][j - 1]][j - 1];
    }
    while(m --){
        int u, v; cin >> u >> v;
        cout << lca(u, v) << endl;
    }
    return 0;
}