图论：倍增求解最近公共祖先LCA

说明：CSDN和公众号文章同步发布，需要第一时间收到最新内容，请关注公众号【比特正传】。

最近公共祖先LCA是NOI大纲中指定的提高组的图论部分的知识点，难度系数为6，提高组考察难度为5~8。

引入

树是一种特殊的图，有没有想过一个问题，给你一棵多叉树，随机给出两个节点，求解两个节点的最近公共祖先？

模板题目链接：

https://www.luogu.com.cn/problem/P3379

基本概念

树的深度：给节点分层，根节点为第一层，即深度为1，依次类推，如图：

节点深度通过depth数组记录，如上图的depth数组如下:

朴素算法

Step1：先从根节点深搜整棵树，搜索过程中，填充深度数组depth和父节点数组fa，代码很简单，如下：

// u表示当前节点，father表示u的父节点
void dfs(int u, int father) {
    depth[u] = depth[father]+1;  // 当前节点深度等于父节点深度+1
    fa[u] = father;   // 记录u父节点
    for(int ne : g[u])  {  // 遍历所有孩子节点，并递归填充depth和fa数组
        if(ne != father) dfs(ne, u); // 除了自己的父节点，其他节点都递归搜索
    }
}

Step2：需要查询两个节点的最近公共祖先，最朴素的想法是，找出两个节点中，深度最大的那个节点，让其向上移动，直到两个节点的深度一样（即在同一层），此时停止，然后两个节点一起向上移动，直到两个节点的父节点为同一个节点即可得到最近公共祖先，代码如下：

// 寻找u和v的LCA
int lcaBaoli(int u, int v) {
    if(depth[u] < depth[v]) swap(u, v);  // 让u永远指向最深的节点
    while(depth[u] > depth[v]) u = fa[u];  // 只要u的深度大于v，那就让u一直往上爬，直到两者在同一层停止就行
    if(u == v) return u;  // 在同一层了，先判断是不是同一个节点，如果是直接返回
    while(fa[u] != fa[v]) {  // u和v的父节点不是同一节点时
        u = fa[u], v = fa[v]; // 让u和v一起向上爬，此时u和v一定处于同一层中
    }
    return fa[u];  // 此时u的父节点和v的父节点是同一个节点，因此直接返回即可
}

完整代码如下：

#include "bits/stdc++.h"
using namespace std;
const int N = 500000+9;
int n, m, s, x, y;
vector<int> g[N];
int depth[N];  // depth[u] 表示节点u的深度
int fa[N];  
// 寻找u和v的LCA
int lcaBaoli(int u, int v) {
    if(depth[u] < depth[v]) swap(u, v);  // 让u永远指向最深的节点
    while(depth[u] > depth[v]) u = fa[u];  // 只要u的深度大于v，那就让u一直往上爬，直到两者在同一层停止就行
    if(u == v) return u;  // 在同一层了，先判断是不是同一个节点，如果是直接返回
    while(fa[u] != fa[v]) {  // u和v的父节点不是同一节点时
        u = fa[u], v = fa[v]; // 让u和v一起向上爬，此时u和v一定处于同一层中
    }
    return fa[u];  // 此时u的父节点和v的父节点是同一个节点，因此直接返回即可
}
// u表示当前节点，father表示u的父节点
void dfs(int u, int father) {
    depth[u] = depth[father]+1;  // 当前节点深度等于父节点深度+1
    fa[u] = father;   // 记录u父节点为father
    for(int ne : g[u])  {  // 遍历所有孩子节点，并递归填充depth和fa数组
        if(ne != father) dfs(ne, u); // 除了自己的父节点，其他节点都递归搜索
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &s);
    for(int i=1; i<n; i++) {
        scanf("%d%d", &x, &y);
        g[x].push_back(y); // 建成无向图
        g[y].push_back(x);
    }
    dfs(s, 0); // 通过深搜填充depth数组和p数组
    while(m--) {
        scanf("%d%d", &x, &y);
        printf("%d\n", lcaBaoli(x, y));
    }
    return 0;
}

结果如下：

以上思想有什么问题吗？哪里还可以优化呢？

还记得ST表吗？还记得并查集路径压缩吗？能不能把这些思想揉一揉，结合到一起呢？

RMQ问题之ST表_st表预处理时间复杂度-CSDN博客

算法思想

倍增思想

上面的代码问题是：向上找父亲，一层一层走太慢了，并查集如果不做路径压缩，也是一层一层找父亲，层数过大会导致效率贼低，因此并查集做了路径压缩。ST呢？f[i][j]表示起点为i，区间长度为2^j的区间，也就是区间[i, i+2^j -1] 的最值，那么递推式为：

f[i][j] = max(f[i][j-1], f[i+2^(j-1)][j-1])

是否可以借助该倍增思想求祖先，而不是一个一个往上跳。

注意：大于0的任何一个正整数，都可以用2的次幂求和表示出来（二进制），这句话非常重要

记录和保存下来每个节点的不同层级的祖先，按照距离进行划分，距离为1，表示上一级祖先（爸爸）；距离为2，表示上两级祖先（即爷爷）；距离为4，表示上四级祖先（即爷爷的爷爷）。

上面的想法可以通过fa数组进行保存，fa[u][i]表示u的【上2^i 级祖先】，上面的图对应的fa数组如下：

首先通过dfs深搜这棵树，搜索过程中填充depth和fa数组，代码如下，结合代码理解：

// u表示当前节点，father表示u的父节点
void dfs(int u, int father) {
    depth[u] = depth[father]+1;  // 当前节点深度等于父节点深度+1
    fa[u][0] = father;   // 当前节点向上2^0=1个祖先为当前的父节点
    for(int i=1; i<=19; i++) {  //向上找到1,2,4,8,....,2^19长度的祖先并填充
        fa[u][i] = fa[fa[u][i-1]][i-1];  // 该递推式是核心
    }
    for(int ne : g[u])  {  // 遍历所有孩子节点，并递归填充depth和p数组
        if(ne != father) dfs(ne, u); // 除了自己的父节点，其他节点都递归搜索
    }
}

上面的代码结合注释理解应该没什么问题。

下面看找最近公共祖先的核心代码，倍增算法:

// lcaMultiply 函数返回u和v的父节点
int lcaMultiply(int u, int v) {  // 倍增
    if(depth[u] < depth[v]) swap(u, v);  // 让u指向深度最大的节点
    for(int i=19; i>=0; i--) { // 向上找u的祖先，通过数学可以推出来，最终u和v的深度一定会相等，因为两者深度差为一个大于等于0的数，如果等于0什么都不做，对于大于0的数，一定可以通过1，2，4，8，16，32，...，凑出来
        if(depth[fa[u][i]] >= depth[v]) {  
            u = fa[u][i];
        }
    }
    if(u == v) return u;  // 如果此时u和v刚好相等，那一定是最近的公共祖先，直接返回即可，
    for(int i=19; i>=0; i--) {  // 两个一起往上找祖先，
        if(fa[u][i] != fa[v][i]) {    // 如果两个祖先不一样，就继续往上走
            u = fa[u][i];  // 向上走到祖先
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

完整代码如下：

#include "bits/stdc++.h"
using namespace std;
const int N = 500000+9;
int n, m, s, x, y;
vector<int> g[N];
int depth[N];  // depth[u] 表示节点u的深度
int fa[N][20];  // fa[u][i]表示节点u向上的2^i个父节点，比如000->111->222->333->444,则fa[444][0]为333，fa[444][1]为222, fa[444][2]为000
// lcaMultiply 函数返回u和v的父节点
int lcaMultiply(int u, int v) {  // 倍增
    if(depth[u] < depth[v]) swap(u, v);  // 让u指向深度最大的节点
    for(int i=19; i>=0; i--) { // 向上找u的祖先，通过数学可以推出来，最终u和v的深度一定会相等，因为两者深度差为一个大于等于0的数，如果等于0什么都不做，对于大于0的数，一定可以通过1，2，4，8，16，32，...，凑出来
        if(depth[fa[u][i]] >= depth[v]) {  
            u = fa[u][i];
        }
    }
    if(u == v) return u;  // 如果此时u和v刚好相等，那一定是最近的公共祖先，直接返回即可，
    for(int i=19; i>=0; i--) {  // 两个一起往上找祖先，
        if(fa[u][i] != fa[v][i]) {    // 如果两个祖先不一样，就继续往上走
            u = fa[u][i];  // 向上走到祖先
            v = fa[v][i];
        }
    }
    return fa[u][0];
}
// u表示当前节点，father表示u的父节点
void dfs(int u, int father) {
    depth[u] = depth[father]+1;  // 当前节点深度等于父节点深度+1
    fa[u][0] = father;   // 当前节点向上2^0=1个祖先为当前的父节点
    for(int i=1; i<=19; i++) {  //向上找到1,2,4,8,....,2^19长度的祖先并填充
        fa[u][i] = fa[fa[u][i-1]][i-1];  // 该递推式是核心
    }
    for(int ne : g[u])  {  // 遍历所有孩子节点，并递归填充depth和p数组
        if(ne != father) dfs(ne, u); // 除了自己的父节点，其他节点都递归搜索
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &s);
    for(int i=1; i<n; i++) {
        scanf("%d%d", &x, &y);
        g[x].push_back(y); // 建成无向图
        g[y].push_back(x);
    }
    dfs(s, 0); // 通过深搜填充depth数组和p数组
    while(m--) {
        scanf("%d%d", &x, &y);
        printf("%d\n", lca(x, y));
    }
    return 0;
}