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

· · 题解

最近刚学了最近公共祖先，趁此机会来写一篇倍增法题解。

算法介绍

定义

在一棵有根树中，有 u 和 v 两个结点。我们需要找到一个点 x，满足 x 既是 u 的祖先又是 v 的祖先。这个结点 x，就是 u 和 v 的最近公共祖先。

最近公共祖先的倍增法可以很好地解决这一问题。

实现

容易想到，我们可以先将深度大的结点跳到和深度小的结点的深度一样，然后在一层层地往上寻找，直到两个结点相同，此时所在结点就是最近公共祖先。

但是，这样的写法会超时。该怎么办呢？

我们可以参考倍增的做法，每次不跳一格，而是跳多格，这样子就可以达到节省时间的效果。

流程

先搜索得出每个结点深度。

定义 lg_i 表示一个非负整数 x，使得 2^x 不大于 i，满足条件的 x 的最大值即为 lg_i。

定义 f[i][j] 表示结点 i 往上跳 2^j 格会到哪里。

预处理部分就很简单了，如果不会的请移至此题。

不一样的是，i 往上跳 2^j 格，可以分解成 i 往上跳 2^{j-1} 格，再往上跳 2^{j-1} 格。这样就可以预处理好 f 数组了。

当他们在同一深度了，要继续往上跳时，如果跳到的这个结点是 u 和 v 的公共祖先，由于我们无法确定这个结点是不是最近公共祖先。所以是不可行的，只有当跳到的结点不是 u 和 v 的最近公共祖先才能继续往上跳。

最后，可以神奇的发现，这个点的父亲结点就是最近公共祖先了。

正确性证明

时间复杂度

预处理 f 数组，时间复杂度为 O(n \log n)。
单此查询，时间复杂度为 O(\log n)。

总体来说，倍增法可以通过此题。

递推式

因为要知道某个点跳 2^j 格到哪，就要知道某个点跳 2^{j-1} 格，而在上次循环中已经求出了每个点跳 2^{j-1} 格会到哪里。所以递推式正确。

查询

一开始需要将两个不同深度的结点跳到同一深度，设 u 为深度大的结点，v 为深度小的结点，c 为 u 的深度与 v 的深度的差值，那么每次都要跳 2^c 格，这样循环，最后两个结点深度一定相同。

需要同时往上跳时，只要跳到的结点不是公共祖先就可以往上跳，那么最后一定是在最近公共祖先的下一层。

因此，查询的部分也是正确的。

综上所述，该算法是正确的。

代码实现

朴素方法的部分代码（会超时）：

if(dep[x] < dep[y]){
    swap(x, y);
}
int t = x, p = y;
while(dep[t] != dep[p]){
    t = f[t];//先让深度大的结点往上跳
}
while(t != p){
    t = f[t], p = f[p];//再让两个结点同时往上跳
}

倍增法代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 500005, M = N;
int n, m, s, lg2[N], f[N][22], head[N], ct, dep[N], maxd = -1;
//lg2[i]:log2(i)向下取整后的值 
//dep[i]:结点i的深度 
struct edge{
    int to, nxt;//简单的链式前向星 
} a[N << 1];
void add(int u, int v){
    a[++ct].to = v, a[ct].nxt = head[u], head[u] = ct; 
    //简单的链式前向星
}
void dfs(int x, int fa){
    f[x][0] = fa;//点x的父亲就是fa 
    dep[x] = dep[fa] + 1;//计算出结点x的深度 
    if(dep[x] > maxd) maxd = dep[x];//计算最大深度 
    for(int i = head[x];i > 0;i = a[i].nxt){
        int tod = a[i].to;
        if(tod != fa){//防止遍历自己的父亲 
            dfs(tod, x);//继续搜索 
        }
    }
}
int lca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    while(dep[u] > dep[v]){
        u = f[u][lg2[dep[u] - dep[v]]];
        //先让两个结点跳到同一深度 
    }
    if(u == v) return u;
    for(int i = lg2[dep[u] - 1];i >= 0;i--){
        if(f[u][i] != f[v][i]){
            u = f[u][i], v = f[v][i];
            //两个结点同时往上跳 
        }
    }
    return f[u][0];//最后的父亲结点就是最近公共祖先 
}
int main(){
    scanf("%d%d%d", &n, &m, &s);
    for(int i = 2;i <= n;i++) lg2[i] = lg2[i / 2] + 1;
    //预处理lg2数组 
    for(int i = 1;i < n;i++){
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    dfs(s, 0);
    for(int j = 1;j <= lg2[maxd];j++){
        for(int i = 1;i <= n;i++){
            f[i][j] = f[f[i][j - 1]][j - 1];
        }//预处理f数组 
    }
    for(int i = 1;i <= m;i++){
        int u, v;
        scanf("%d%d", &u, &v);
        printf("%d\n", lca(u, v));//计算lca 
    }
    return 0;
}