最近公共祖先(LCA)

1. 最近公共祖先原理

原理

• LCA问题：在一棵有根树中，一个节点的祖先节点是指它本身或者它父节点的祖先。给定两个节点，两个点共同的祖先中距离两者最近的节点就是这两个节点的最近公共祖先。需要注意的是最近公共祖先可能是这两个节点中的某一个。
• LCA问题的解法有很多种，下面介绍四种，其中第二种、第三种最常用

---

1. 向上标记法

• 做法：求两个节点p、q的最近公共祖先原理，可以任选一个点，比如点p，沿着点p向上走，将走过的节点标记为true，代表已经走过，走到根节点后停止；然后让q向上走，当q遇到某个节点的标记为true时，这个点就是q、q的最近公共祖先。这个做法最坏情况下时间复杂度是O(n)的（当树是一条链时）。

2. 倍增法

• 在这种做法中，我们需要先预处理两个数组，分别是$fa[i,j]$ 和 $depth[i]$，其表示的含义如下：

  $fa[i,j]$ 表示从节点i开始，向上走$2^j$步所能走到的节点的编号，其中$0\le j\le \lfloor log(n)\rfloor$。

  $depth[i]$ 表示每个点的深度，规定根节点的深度为1。

• 如何求解这两个数组呢？

  • $fa[i,j]$ 可以采用递推的方式求解（BFS和DFS都可以求解）：

    当 j == 0 时，$fa[i,j]=i$的父节点；

    当 j > 0 时，我们可以分成两步走，第一次跳$2^{j-1}$步，然后再跳$2^{j-1}$步，因此有：$fa[i,j]=fa[fa[i,j-1],j-1]$。

  • $depth[i]$ 可以采用BFS或者DFS求解

• 有了这两个数组之后，我们就可以根据这两个数组求解LCA了，分为两步：

【1】先将两个点跳到同一层，假设求a、b的LCA，$depth[a]>depth[b]$，则a需要向上跳 $step=depth[a]-depth[b]$ 步，我们可以基于二进制拼凑的思想进行跳跃，从高位向低位看（从大到小枚举k，枚举到0），如果 step 某一高位是1，则应该跳跃对应的步数，直到跳到同一层。

【2】如果两个点是同一个点了，则找到LCA了，可以直接退出了。否则让两个点同时向上跳，一直跳到他们的最近公共祖先的下一层。（为什么不让他们跳到相等呢？因为这样得到的结果可能不是最近公共祖先），具体做法和第一步是类似的，从大到小枚举k，枚举到0，如果$fa[a,k]!=fa[b,k]$，则还可以向上跳。因为是二进制枚举，所以一定可以枚举到任何数据，因此最终一定可以跳到他们的最近公共祖先的下一层。

• 预处理：O(n*log(n))；查询：O(log(n))
• 为了方便处理，这里设置哨兵：如果从i开始跳$2^j$步会跳过根节点，那么规定$f[i,j]=0$。同时规定$depth[0]=0$。

3. tarjan算法（离线求LCA）

• 所谓的在线做法和离线做法是针对有询问的题目的。在线做法，即读取一个询问，处理一个询问。离线做法，即将所有询问读取完毕，一起进行处理。
• 另外注意 tarjan 这个人发明了很多算法，特别是在图论领域，因此很多算法都被称为 tarjan 算法，需要注意区分，这里的 tarjan 算法是指离线求LCA的做法。
• 这个做法求解LCA问题，可以做到O(n + m)的时间复杂度
• 这个做法本质上是对向上标记法的优化，在深度优先遍历时，将所有点分为三大类：

（1）已经遍历过且回溯过的点，记为2；

（2）正在搜索的分支上的点，记为1；

（3）还未搜索到的点，记为0；

• 如果当前正在搜索上图中的点x，则找一下所有和这个点x的所有相关的询问，假设询问x和y的最近公共祖先，如果点y在绿色圈中，则可以得到x和y的LCA是图中对应的红色实心点；如果y还没被搜索到，则直接忽略即可，后面的遍历过程中遍历到点y时，就会处理这个询问。
• 因此我们可以使用并查集将所有标记为2的点合并到他们对应的红色实心节点中，当我们需要查看x和某个绿色圈中的点y的LCA时，只需要查看一下点y合并到了哪个点中即可，如下图（表示DFS到点x时，当前并查集的情况）：

4. RMQ

• 根据层次遍历的顺序给每个节点一个编号，在dfs遍历的过程中记录遍历节点的顺序，重复的节点也要记录，原理如下图：

2. AcWing上的LCA题目

AcWing 1172. 祖孙询问

问题描述

• 问题链接：AcWing 1172. 祖孙询问

  

分析

• 使用倍增法解决即可。
• 因为树中最多有四万个点，树的高度最多为四万，$\lfloor log(40000)\rfloor =15,(2^{15}=32768)$，因此fa的第二维有0-15一共16个数，第二维需要设置为16。
• 这一题的处理方式是在线方式，即读取一个询问，处理一个询问。与此对应的是离线方式，即将所有询问读取完毕，一起进行处理，可以使用tarjan算法，对应题目是：AcWing 1171. 距离。

代码

• C++

#include <iostream>
#include <cstring>

using namespace std;

const int N = 40010, M = N * 2;

int n, m;  // 节点数，询问数
int h[N], e[M], ne[M], idx;
int fa[N][16];
int depth[N];  // 节点深度，根节点深度规定为1, depth[0]规定为0
int q[N];  // bfs使用的队列

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// 负责预处理，求解fa和depth
void bfs(int root) {
    
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0;  // 设置哨兵
    depth[root] = 1;
    int hh = 0, tt = -1;
    q[++tt] = root;
    
    while (hh <= tt) {
        
        int t = q[hh++];
        
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (depth[j] > depth[t] + 1) {
                depth[j] = depth[t] + 1;
                q[++tt] = j;
                
                fa[j][0] = t;
                for (int k = 1; k <= 15; k++)
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b) {
    
    if (depth[a] < depth[b]) swap(a, b);
    // 步骤1: a, b跳到同一层
    for (int k = 15; k >= 0; k--) 
        if (depth[fa[a][k]] >= depth[b])  // 哨兵起作用位置1
            a = fa[a][k];
    if (a == b) return a;
    // 步骤2: a, b跳到他们的最近公共祖先的下一层
    for (int k = 15; k >= 0; k--)
        if (fa[a][k] != fa[b][k]) {  // 哨兵起作用位置2
            a = fa[a][k];
            b = fa[b][k];
        }
    return fa[a][0];
}

int main() {
    
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    int root = 0;
    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (b == -1) root = a;
        else add(a, b), add(b, a);
    }
    
    bfs(root);
    
    scanf("%d", &m);
    
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        
        int p = lca(a, b);
        if (p == a) puts("1");
        else if (p == b) puts("2");
        else puts("0");
    }
    
    return 0;
}

AcWing 1171. 距离

问题描述

• 问题链接：AcWing 1171. 距离

  

分析

• 使用tarjan算法解决即可。
• 注意到本题中是一棵树，那么任意两点之间的路径是唯一的，因为最短路径就是这条路径的距离；如何在树上求解任意两个点的距离（经过的边的权值和）呢？我们可以求出每个点到根节点的距离，记在数组dist中，则任意两点x，y之间的距离是：$dist[x]+dist[y]-2\times dist[lca(x,y)]$。如下图

• 代码中tarjan函数中如下两句话不能调换顺序：

            tarjan(j);
            p[j] = u;

原因如下（参考网址）：

代码

• C++

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;

const int N = 10010, M = N * 2;

int n, m;  // n: 节点数, m: 询问数
int h[N], e[M], w[M], ne[M], idx;
int dist[N];  // 某个点到根节点经过的边的权值和
int p[N];  // 并查集
int res[M];  // 存储询问的结果
int st[N];  // 存储当前节点的状态，可以为2,1,0
vector<PII> query[N];  // 存储查询，first存查询的另外一个点，second存查询编号

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void dfs(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dist[j] = dist[u] + w[i];
        dfs(j, u);
    }
}

void tarjan(int u) {
    
    st[u] = 1;  // 表示该点正在搜索分支上
    
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            // 这两句话不能调换顺序，细节可以参考上面的解释
            // 简言之，调换顺序后之后的find函数会做路径压缩，导致结果错误
            tarjan(j);
            p[j] = u;
        }
    }
    
    for (auto item : query[u]) {
        int y = item.first, id = item.second;
        if (st[y] == 2) {
            int anc = find(y);  // anc是点u和y的LCA
            res[id] = dist[u] + dist[y] - 2 * dist[anc];
        }
    }
    
    st[u] = 2;  // 已经遍历过且回溯过的点
}

int main() {
    
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a != b) {
            query[a].push_back({b, i});
            query[b].push_back({a, i});
        }
    }
    
    for (int i = 1; i <= n; i++) p[i] = i;
    
    // 将1号点当做根节点
    dfs(1, -1);
    tarjan(1);
    
    for (int i = 0; i < m; i++) printf("%d\n", res[i]);
    
    return 0;
}

AcWing 356. 次小生成树

问题描述

• 问题链接：AcWing 356. 次小生成树

  

分析

• 这一题和 AcWing 1148. 秘密的牛奶运输 一样，都是求解次小生成树，关于次小生成树的分析如下：

• 这一题对求解MST中任意两点之间的距离进行了优化处理，即上图中的暴力枚举，将$O(n^2)$的时间复杂度优化为$O(n\times log(n))$的时间复杂度，具体优化过程如下：
• 我们使用 $d1[i,j]$ 表示在节点i向上跳 $2^j$ 步路径上的边权最大值， $d2[i,j]$ 表示在节点i向上跳 $2^j$ 步路径上的边权严格次大值。在lca向上跳的过程中记录每次跳跃时的最大值和次大值，那么最终整个路径中的最大值和次大值一定在这些记录的值中，从中求出即可。
• 那么如何求解 $d1、d2$ 呢？和求 $fa$ 类似，在BFS的过程中递推求解即可，如下图：

• 总结：求解这个题分为三步：

（1）使用kruskal算法求解最小生成树；

（2）求解 $fa、d1、d2$ 数组；

（3）依次枚举每条非树边，将其加入树中，一定会形成环，去掉环中树边的最大值或者次大值得到另一棵树，这些树中权值最小的就是次小生成树。

• 注意点：对于数组 $fa、d1、d2$ ，其第二维的大小应该为17，因为树中最多十万个点，$\lfloor log(100000)\rfloor =16,(2^{16}=65536)$，因此 $fa、d1、d2$ 的第二维有0-16一共17个数，第二维需要设置为17。另外邻接表中我们建立的是MST，双向边，最多二十万条边。边的存储使用结构体。

代码

• C++

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010, M = 300010, INF = 0x3f3f3f3f;

int n, m;  // 点数、边数
int h[N], e[M], w[M], ne[M], idx;  // 存储MST
struct Edge {
    int a, b, w;
    int used;  // 该边是否在MST中
    bool operator< (const Edge &e) const {
        return w < e.w;
    }
} edges[M];
int p[N];  // kruskal算法使用到的并查集
int depth[N];  // 节点深度，根节点深度规定为1, depth[0]规定为0
int fa[N][17], d1[N][17], d2[N][17];
int q[N];  // bfs使用到的队列

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

LL kruskal() {
    
    for (int i = 1; i <= n; i++) p[i] = i;
    sort(edges, edges + m);
    LL res = 0;
    for (int i = 0; i< m; i++) {
        int a = find(edges[i].a), b = find(edges[i].b), w = edges[i].w;
        if (a != b) {
            p[a] = b;
            edges[i].used = true;
            res += w;
        }
    }
    
    return res;
}

void build() {
    
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i++) 
        if (edges[i].used) {
            int a = edges[i].a, b = edges[i].b, w = edges[i].w;
            add(a, b, w), add(b, a, w);
        }
}

void bfs() {
    
    // 这里默认1号点为根节点，其实任意一个点都可以作为根节点
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[1] = 0;
    int hh = 0, tt = 0;
    q[0] = 1;
    
    while (hh <= tt) {
        
        int t = q[hh++];
        
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (depth[j] > depth[t] + 1) {
                depth[j] = depth[t] + 1;
                q[++tt] = j;
                
                fa[j][0] = t;
                d1[j][0] = w[i], d2[j][0] = -INF;
                for (int k = 1; k <= 16; k++) {
                    int anc = fa[j][k - 1];
                    fa[j][k] = fa[anc][k - 1];
                    int distance[4] = {d1[j][k - 1], d2[j][k - 1], d1[anc][k - 1], d2[anc][k - 1]};
                    d1[j][k] = d2[j][k] = -INF;
                    for (int u = 0; u < 4; u++) {
                        int d = distance[u];
                        if (d > d1[j][k]) d2[j][k] = d1[j][k], d1[j][k] = d;
                        else if (d != d1[j][k] && d > d2[j][k]) d2[j][k] = d;
                    }
                }
            }
        }
    }
}

LL lca(int a, int b, int w) {
    
    static int distance[N * 2];  // 记录上跳过程中每段的最大值和次大值
    int cnt = 0;  // 记录跳跃的次数，每跳一次，会记录两个数据
    
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 16; k >= 0; k--)
        if (depth[fa[a][k]] >= depth[b]) {
            distance[cnt++] = d1[a][k];
            distance[cnt++] = d2[a][k];
            a = fa[a][k];
        }
    
    if (a != b) {
        for (int k = 16; k >= 0; k--) 
            if (fa[a][k] != fa[b][k]) {
                distance[cnt++] = d1[a][k];
                distance[cnt++] = d2[a][k];
                distance[cnt++] = d1[b][k];
                distance[cnt++] = d2[b][k];
                a = fa[a][k], b = fa[b][k];
            }
        // 此时a,b到其LCA距离都为1，只存在最大值
        distance[cnt++] = d1[a][0];
        distance[cnt++] = d1[b][0];
    }
    
    int dist1 = -INF, dist2 = -INF;
    for (int i = 0; i < cnt; i++) {
        int d = distance[i];
        if (d > dist1) dist2 = dist1, dist1 = d;
        else if (d != dist1 && d > dist2) dist2 = d;
    }
    
    if (w > dist1) return w - dist1;
    return w - dist2;
}

int main() {
    
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = {a, b, c};
    }
    
    LL sum = kruskal();  // 返回MST权值和
    build();  // 创建MST
    bfs();  // 求解fa、d1、d2
    
    LL res = 1e20;
    for (int i = 0; i < m; i++)
        if (!edges[i].used) {
            int a = edges[i].a, b = edges[i].b, w = edges[i].w;
            res = min(res, sum + lca(a, b, w));
        }
    
    printf("%lld\n", res);
    
    return 0;
}

AcWing 352. 闇の連鎖

问题描述

• 问题链接：AcWing 352. 闇の連鎖

  

分析

• 根据题意，我们需要在图上去掉两条边，第一条是树边，第二条是非树边，然后使得图不连通，问这样的做法有多少种？

• 现在问题就变成了如何快速的给连续的树边上增加一个相同的值，并且快速的得到每个边上对应的值？这可以使用类似于差分的思想求解。做法如下：

• 注意点：对于数组 $fa$ ，其第二维的大小应该为17，因为树中最多十万个点，$\lfloor log(100000)\rfloor =16,(2^{16}=65536)$，因此 $fa$ 的第二维有0-16一共17个数，第二维需要设置为17。

代码

• C++

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = N * 2;  // 附加边不需要存储

int n, m;  // 点数、附加边数
int h[N], e[M], w[M], ne[M], idx;
int depth[N], fa[N][17];
int d[N];  // 树上差分，每个点上的权值，可以转化为边上的权值
int q[N];  // bfs使用到的队列
int ans;  // 方案数

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void bfs() {
    
    // 这里默认1号点为根节点，其实任意一个点都可以作为根节点
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[1] = 1;
    
    int hh = 0, tt = 0;
    q[0] = 1;
    
    while (hh <= tt) {
        
        int t = q[hh++];
        
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (depth[j] > depth[t] + 1) {
                depth[j] = depth[t] + 1;
                q[++tt] = j;
                
                fa[j][0] = t;
                for (int k = 1; k <= 16; k++)
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b) {
    
    if (depth[a] < depth[b]) swap(a, b);
    
    for (int k = 16; k >= 0; k--)
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
            
    if (a == b) return a;
    
    for (int k = 16; k >= 0; k--)
        if (fa[a][k] != fa[b][k]) {
            a = fa[a][k];
            b = fa[b][k];
        }
    
    return fa[a][0];
}

// fa: u的父节点，防止遍历出现环
// 返回以u为根的所有点的权值和
int dfs(int u, int fa) {
    
    int res = d[u];
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j != fa) {
            int s = dfs(j, u);
            if (s == 0) ans += m;
            else if (s == 1) ans += 1;
            res += s;
        }
    }
    return res;
}

int main() {
    
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    
    bfs();  // 求解depth、fa
    
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        int p = lca(a, b);
        d[a]++, d[b]++, d[p] -= 2;
    }
    
    dfs(1, -1);
    
    printf("%d\n", ans);
    
    return 0;
}

3. 力扣上的LCA题目

Leetcode 0235 二叉搜索树的最近公共祖先

问题描述

• 问题链接：Leetcode 0235 二叉搜索树的最近公共祖先

  

分析

• 因为是二叉搜索树，所以我们可以根据值的大小递归求解。
• 时间复杂度：$O(h)$，h为树高。

代码

• C++

/**
 * 执行用时：44 ms, 在所有 C++ 提交中击败了21.83%的用户
 * 内存消耗：22.8 MB, 在所有 C++ 提交中击败了33.33%的用户
 */
class Solution {
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {

        if (!root) return NULL;
        if (p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q);
        if (p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right, p, q);
        return root;
    }
};

• Java

/**
 * 执行用时：6 ms, 在所有 Java 提交中击败了99.37%的用户
 * 内存消耗：39.4 MB, 在所有 Java 提交中击败了30.59%的用户
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if (root == null) return null;
        if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
        if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);
        return root;
    }
}

Leetcode 0236 二叉树的最近公共祖先

问题描述

• 问题链接：Leetcode 0236 二叉树的最近公共祖先

  

分析

• 递归遍历两棵子树，第一次发现某棵子树中既有p又有q，则该子树的根节点为p和q的最近公共祖先。

• 递归的返回值是一个二进制的数，最低位是1的话表示该棵子树存在p，从右向左第二位是1的话表示该棵子树存在q。
• 时间复杂度：$O(n)$，n为节点个数。

代码

• C++

/**
 * 执行用时：12 ms, 在所有 C++ 提交中击败了98.30%的用户
 * 内存消耗：13.9 MB, 在所有 C++ 提交中击败了77.14%的用户
 */
class Solution {
public:
    TreeNode* ans = NULL;

    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {

        dfs(root, p, q);
        return ans;
    }

    // 返回值是一个二进制的数，最低位是1的话表示该棵子树存在p，从右向左第二位是1的话表示该棵子树存在q。
    int dfs(TreeNode *root, TreeNode *p, TreeNode *q) {

        if (!root) return 0;

        int state = dfs(root->left, p, q);
        if (root == p) state |= 1;
        else if (root == q) state |= 2;
        state |= dfs(root->right, p, q);

        if (state == 3 && !ans) ans = root;  // 只有第一次找到的才是LCA
        return state;
    }
};

• Java

/**
 * Date: 2020/9/27 9:43
 * Content: 后序遍历
 * 执行用时：7 ms, 在所有 Java 提交中击败了99.90%的用户
 * 内存消耗：40.4 MB, 在所有 Java 提交中击败了84.65%的用户
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if (root == null) return null;
        if (root == p || root == q) return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left != null && right != null) return root;
        if (left != null) return left;
        return right;
    }
}