浅析最近公共祖先（LCA）

Nekroz

2018-08-06 16:34:53

算法·理论

1. 定义

LCA（Least Common Ancestors），即最近公共祖先，指对于有根树 T 的两个结点 u 、v ，最近公共祖先 LCA(T, u, v) 表示一个结点 x, 满足 x 是 u、v 的祖先且 x 的深度尽可能大。

下面给出一个自己画的图，用来解释LCA及其算法，顺便举个例子。

图中，LCA(2, 4) = 1 ， LCA(5, 6) = 2 。

平常在信息学竞赛中求LCA一般有四种办法：

用倍增法求解，预处理复杂度是 O(n\log n) ,每次询问的复杂度是 O(\log n), 属于在线解法。
利用欧拉序转化为RMQ问题，用ST表求解RMQ问题，预处理复杂度 O(n + n \log n) ，每次询问的复杂度为 O(1)，也是在线算法。
采用Tarjan算法求解，复杂度 O(\alpha(n) + Q) ，属于离线算法。
利用树链剖分求解，复杂度预处理O(n) ，单次查询 O(\log n) ，属于在线算法。

但是树链剖分求解LCA中的行为（强调是行为，不是思想）与倍增法类似，加之代码量大（当然你有板子的话当我没说过），不易调试，所以仅在讲倍增法的时候有所涉及，不详细展开。

为了能够更加流畅的阅读这篇文章，你需要掌握如下内容：

能用dfs预处理出有根树中的父子关系和其到根的深度和距离（如果需要的话）
了解基础的倍增算法的思想
能够运用ST表求解RMQ问题
会使用带路径压缩的并查集

熟悉前向星存边（我在程序中都是前向星存边），代码在这里给出

struct edgetype {
int to, next, dist;
} edge[MAXN << 1];
int head[MAXN], cnt;
inline void AddEdge(int from, int to, int dist) {
edge[++cnt] = (edgetype){to, head[from], dist};
head[from] = cnt;
}

前置姿势很简单是吧QAQ（因为不用讲树链剖分啊~）

2. LCA问题的3种解法

2.1. 倍增法

最常用，也是最简单的算法，实质就是直接对暴力使用倍增优化将复杂度降低达到需求。

2.1.1. 暴力求解LCA

预处理，先对有根树 T 进行一次 dfs 得到每个结点的父亲和它的深度。

对于每个查询 LCA(T, u, v) ，我们假设 depth(u) > depth(v) （反正反了可以 swap 一下调过来）。于是我们可以先将 u 暴力跳到与 v 相同深度，然后两个结点一起往上走，每次的步长都是 1 （即每次是从结点 u 跳到它的父亲）。直到两个结点相遇位置，相遇的位置就是 LCA(T, u, v) 。

2.1.2. 倍增优化暴力

了解了倍增基本思想的话我就直接来讲做法了。

首先还是要来说明为什么可以用倍增优化暴力，因为找祖先这个操作是满足结合律的，这就是能够使用倍增算法的一个前提，如果看不懂也没关系，毕竟这个和理解程序没什么太大的关系。

我们令 anc(x, y) 表示结点 x 的 2^j 个祖先。倍增的递推式也很简单，就是 anc(x, y) = anc(anc(x, y - 1),y - 1) ,即 x 的 2^j 个祖先是 x 的 2^{j -1} 个祖先的 2^{j-1} 个祖先。

有点绕？画个图就可以让自己清晰了，套回定义式就行。

这个递推的部分我们可以放在dfs内部完成，也可以在dfs结束之后再单独执行，个人比较推荐单独执行。

现在我们面临询问 LCA(T, u, v) 。按照暴力的思想，我们要把相对较深的结点爬到与另外一个结点相同的深度。我们假设 depth(u) > depth(v) ，那么 u 要上爬 h=depth(u) - depth(v) 个祖先到达与 v 相同的深度。

考虑对这个 h 进行二进制拆分，假设 h = (13)_{10} = (1101)_2 ，从低位开始， h 在第 0 （从低位开始由低到高依次排列），第 2 ，第 3 上的数是 1 ，也就意味着我们先 u \leftarrow anc(u, 0) ，再 u \leftarrow anc(u, 2) ，u \leftarrow anc(u, 3) 。最后得到的 u 就与 v 深度相同了，可以看出，这些操作互不影响，调换位置也没有关系（这就是之前说的找祖先这个操作满足结合律的体现）。实现起来也很简单：

    inline void swim(int& x, int h) {
        for (int i = 0; h > 0; i++) {
            if (h & 1) 
                x = anc[x][i];
            h >>= 1;
        }
    }

那么我们让 u ，v 到达了同样的高度之后怎么做呢，分两种情况：

按照暴力的思路，这回我们要让这两个结点一起往上跳，用倍增思想就体现为每次上跳相等的高度。但是这一回我们就不可以从低位开始跳了，因为我们不知道要上跳多少才能与让 u 和 v 相遇，即枚举从高位开始，上跳的条件是 anc(u, 0) \neq anc(v, 0) 。

为什么是这样呢？其实观察上面的倍增递推式我们可以知道，对于深度比根节点还要小的点，但是程序会将这个点编号赋为根，这样一来，我们同时上跳的时候要是 anc(u, i) = anc(v, i) 的话我们就不知道这两个结点有没有跳过头（跳到 LCA 的上面去了），只有 anc(u, i) \neq anc(v, i) 才可以保证这两个点的深度还在 LCA(T, u, v) 之下，然后就可以 u \leftarrow anc(u,i) , v \leftarrow anc(v, i) 。

当这个枚举的过程结束时，我们可以得到 LCA(T, u, v) = anc(u, 0) = anc(v, 0) ，因为现在的 u 和 v 都已经上跳了最大限度，再往上跳是不符合条件的。

2.1.3. 利用倍增思想求解LCA问题

还是考虑模拟一下吧，因为是在线算法，所以只模拟初始化和三组询问，但是上面画的树对于倍增算法来说有点浅，不过就将就一下吧。

果然深度很浅啊，但是深一点的话接下来的欧拉序就要抗议了（表格花不下=汗=）

考虑 LCA(T, 6, 8) = 1 ，先运行把 8 跳到与 6 相同的深度，需要向上跳 4 - 3 = 1 个单位，跳到 7 号点，即 7=anc(8, 0) ，因为 2^0 = 1 。

接下来一起往上跳，再高位我们就不枚举了，当枚举到第 1 位时，6 和 7 的 2^1=2 个祖先恰好就是 LCA ，但是我们的程序并不知道这一点，于是，跳过。。

枚举到第 0 位的时候，2=anc(6, 0) \neq anc(7, 0)=4 ，满足条件，向上跳，同时枚举过程结束，1 = anc(2, 0)=anc(4, 0) 也就是答案。

接下来考虑 LCA(T, 5, 6) = 2 ，由于 5 和 6 的深度相同，省略单独上跳的过程。

接下来一起往上跳，枚举到第 0 位时，发现 anc(5, 0)=anc(6,0) ，不符合条件，忽略，枚举过程结束，2=anc(5, 0)=anc(6,0)，也是答案。

最后考虑 LCA(T, 1, 8) = 1，首先将 8 跳到与 1 相同的深度，需要上跳 4-1=3 个单位，跳到 1 号点，即 4=anc(8, 1), 1=anc(4, 0)，因为 2^0 + 2^1=1+2=3 。

此时发现两个点重合了直接返回答案 1。

以上就是模拟过程，因为树高较浅，枚举的过程比较短。如果还是不明白的话可以画一棵深度更大的树进行模拟，这里就不详细展开了。

2.1.4. 参考代码及注释

namespace LCA {
    int anc[MAXN][LOG], depth[MAXN];
    int dist[MAXN];
    inline void dfs(int u, int p, int d) {
        anc[u][0] = p; depth[u] = d;
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to;
            if (v == p) continue;
            dist[v] = dist[u] + edge[i].dist;
            dfs(v, u, d + 1);
        }
    }
    inline void init(int root, int n) {
        dist[root] = 0;
        dfs(root, 0, 1);
        for (int j = 1; j < LOG; j++)  //递推anc数组
            for (int i = 1; i <= n; i++)
                anc[i][j] = anc[ anc[i][j - 1] ][j - 1];
    }
    inline void swim(int& x, int h) { //将x上爬h个单位
        for (int i = 0; h > 0; i++) {
            if (h & 1) 
                x = anc[x][i];
            h >>= 1;
        }
    }
    inline int query(int x, int y) {
        if (depth[x] < depth[y]) std::swap(x, y); //置x为深度较深的点
        swim(x, depth[x] - depth[y]); //让x和y的深度相同
        if (x == y) return x;  //如果相等直接返回
        for (int i = LOG - 1; i >= 0; i--) //从高位开始枚举每个二进制位
            if (anc[x][i] != anc[y][i]) {
                x = anc[x][i];
                y = anc[y][i];
            } 
        return anc[x][0];
    }
}

2.1.5. 评注

这个算法主要就是比较好想（毕竟是优化版的暴力嘛~），一般比较容易理解，编程也容易。

还有就是其思想与用树链剖分求 LCA(T,u, v) 类似，后者求 LCA(T, u, v) 的过程实际上就是跳重链，每次跳到所在链的顶端的父亲上去，直至两个结点所在的重链相同（当然是重链顶端深度深的先开始跳咯）。

2.2.欧拉序+ST表

2.2.1. 欧拉序

对有根树T进行深度优先遍历，无论是递归还是回溯，每次到达一个节点就把编号记录下来，得到一个长度为 2N - 1 的序列，成为树 T 的欧拉序列 F。

按照深度优先遍历我们可以得到它的欧拉序和深度序列：

为了方便，我们定义 first(u) 表示 u 结点的第一次出现的位置，那么我们根据上面的表格就可以得到 n 个结点各自的 first 值：

根据深度优先遍历的特点，我们可以知道，对于结点 u 和结点 v, 我们不妨假设 u 在 v 之前被遍历，也就是说 first(u) < first(v) ，那么在 u 遍历到 v 过程中深度最小的点就是 LCA(T, u, v) （这一点在Tarjan算法中也有运用）,假设我们求的是 LCA(T, 6, 8) = 1 ，那么我们把从 6 遍历到 8 时涉及到的顶点单独取出来，就可以得到下面一幅图：

从图中，我们可以清晰得看出，6 遍历到 8 时深度最小的结点是 1 也就是 LCA(T, u, v) 。

这样一来，我们就可以将 LCA 问题转化为RMQ问题：LCA(T, u, v) = RMQ(B, first(u), first(v)) 。

2.2.2. 用欧拉序和ST表求解LCA问题

仍然以上图为例，假定 u = 6 , v = 8 在图上很明显能够看出 LCA(T, u, v) = 1 。同时我们把代表从 u 遍历到 v 的这个序列”抽“出来：

为什么要从原序列中抽取 5 ~ 12 这个串呢？原因很简单，first(6) = 5 ， first(8)=12 ，这个值上面的表已经给出了。

可以看出，在这个序列中，深度最小的点的序号是 7 和 9 其值是 1 ，这不就是我们要的 LCA(T, u, v) 吗！

有了这个例子大家应该就很清楚了，具体实现的时候还要注意 ST 表中存的不再只是那个最小值，而是最小值的下标，也就是表中的序号。

2.2.3. 参考代码及注释

代码中 value[] 代表欧拉序列 F，depth[] 代表深度序列 B 。

namespace LCA {
    int ST[MAXN << 1][LOG];
    int value[MAXN << 1], depth[MAXN << 1], first[MAXN], len; //欧拉序及深度序列相关
    int dist[MAXN];
    inline int calc(int x, int y) { //利用下标进行运算
        return depth[x] < depth[y] ? x : y;
    }
    inline void dfs(int u, int p, int d) {
        value[++len] = u; depth[len] = d; first[u] = len; //递归时将结点加入欧拉序列中，并记录first
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to;
            if (v == p) continue;
            dist[v] = dist[u] + edge[i].dist;
            dfs(v, u, d + 1);
            value[++len] = u; depth[len] = d; //回溯时将结点加入欧拉序列中
        }
    }
    inline void init(int root) {
        len = 0; dist[root] = 0;
        dfs(root, 0, 1);
        for (int i = 1; i <= len; i++) ST[i][0] = i;
        for (int j = 1; (1 << j) <= len; j++)  //ST表倍增过程
            for (int i = 1; i + (1 << j) - 1 <= len; i++) 
                ST[i][j] = calc(ST[i][j - 1], ST[i + (1 << (j - 1))][j - 1]);
    }
    inline int query(int x, int y) {
        int l = first[x], r = first[y]; 
        if (l > r) std::swap(l, r); //找到区间[l, r]
        int k = log2(r - l + 1);
        return value[calc(ST[l][k], ST[r - (1 << k) + 1][k])];
    }
}

2.2.4. 评注

思想比较巧妙，虽说查询复杂度是 O(1) 但是预处理的 O(n \log n) 复杂度常数比较大，因为欧拉序列的长度是 2n - 1 。所以有时候会跑不过倍增算法，心塞。

另外，我们可以观察到深度序列 B 相邻两个数的差为 1 ，在这种情况下求 RMQ 又被称为正负 1 RMQ问题，该问题是有 O(n)-O(1) 解法的，但是比较麻烦，常数比较大，所以这里不予展开。

2.3. Tarjan 算法

2.3.1. Tarjan算法的主要思想

Tarjan算法的核心思想是先进行一遍深度优先搜索，在讨论LCA与RMQ的关系的时候，我们已经论述过 u 向 v 遍历过程中深度最小的点就是 LCA(T, u, v) 。举个例子，假设我们求的是 LCA(T, 6, 8) = 1 ，那么我们把从 6 遍历到 8 时涉及到的顶点单独取出来，就可以得到下面一幅图：

从图中，我们可以清晰地看出，6 遍历到 8 时深度最小的结点是 1 也就是 LCA(T, u, v) 。

下面我们面临的问题就是如何快速求出两个给定结点去所回溯到的最远的点。

我们给每个结点 x 记录一个 f[x] 值，f[x] 的意义是搜索时曾经从 x 点回溯到 f[x] 点，初始化时 f[x]\leftarrow x 。

接下来开始深度优先遍历，当遍历完一个结点的所有子树时，更新 f[x]\leftarrow x 。同时，就可以处理关于 x 的一部分询问（有些结点没有被访问过所以不会被处理），很明显的，对于询问 LCA(T, x, y) ，如果 y 被访问过了，我们就可以认为 LCA(T, u, v) 是 v 在搜索时曾经回溯到的最远点，至于 f[x] 怎么维护，就要用到并查集了。

这样，一次深度优先遍历之后，我们便得到了所有问题的答案。

2.3.2. 用Tarjan算法求解LCA问题

有根树 T 最上面已经给出了，而我们面临这样几个询问： LCA(T, 5, 6), LCA(T, 5, 3), LCA(T, 6, 8) 。

我们首先搜索到了 1 号结点，向下搜索到 2 号结点，再从 2 号结点搜索到了 5 号节点。
由于 5 号节点时叶子结点，所以开始处理 5 号结点的有关询问，发现 6 号节点和 3 号节点均未访问，不处理.

回溯到 2 号节点，f[5] \leftarrow 2。

搜索到 6 号节点。
处理 6 号结点有关询问，发现 5 号节点已经被访问过，于是第一个询问得到处理:LCA(T, 5, 6) = seek(5) = f[5] = 2 。

回溯到 2 号结点，f[6] \leftarrow 2 。回溯到 1 号节点，f[2] \leftarrow 1 。

搜索 3 号结点。
处理 3 号结点有关询问，发现 5 号结点已经被访问过了，处理询问，LCA(T, 5, 3) = seek(5) = f[f[6]] = 1 ,同时因为路径压缩的原因 f[5] \leftarrow f[2] = 1 。

回溯到 1 号节点， f[3] \leftarrow 1 。

搜索 4 号结点，搜索 7 号结点，搜索 8 号结点
处理与 8 号结点有关询问，发现 6 号结点已经被访问过了，处理询问， LCA(T, 6, 8) = seek(6) = f[f[6]] = 1 。因为路径压缩 f[6] \leftarrow f[2] = 1 。

回溯到 7 号结点，f[8] \leftarrow 7 ，回溯到 4 号结点， f[7] = 4 ，回溯到 1 号结点 f[4] \leftarrow 1 。

算法结束。

其实最后的 f 数组不全部是 root = 1 的原因就是 7 号结点和 8 号结点没有进行路径压缩，否则的话所有结点最后的 f 值都是根节点的编号。

namespace LCA {
    edgetype qedge[MAXQ << 1];
    int qhead[MAXN], qcnt;
    inline void AddQuery(int from, int to, int index) { //添加询问的前向星
        qedge[++qcnt] = (edgetype){to, qhead[from], index};
        qhead[from] = qcnt;
    }
    int u[MAXN], v[MAXN], ans[MAXN]; //询问相关
    int f[MAXN], dist[MAXN];  
    bool visit[MAXN]; 
    inline int seek(int u) {  // 路径压缩
        return f[u] == u ? u : f[u] = seek(f[u]);
    }
    inline void dfs(int u, int p) {   //Tarjan算法的主要流程
        for (int i = head[u]; i; i = edge[i].next) {  
            int v = edge[i].to;
            if (v == p) continue;
            dist[v] = dist[u] + edge[i].dist;
            dfs(v, u); 
            f[v] = u; //回溯时修改 f 数组
        }
        visit[u] = true; //表示已访问
        for (int i = qhead[u]; i; i = qedge[i].next) {
            int v = qedge[i].to;
            if (visit[v]) //如果另一个顶点也被访问过则处理询问
                ans[qedge[i].dist] = seek(v);
        }
    }
    inline void init() {
        memset(qhead, 0, sizeof qhead); qcnt = 0;
    }
    inline void solve(int root, int n) {
        dist[root] = 0;
        memset(visit, false, sizeof visit);
        for (int i = 1; i <= n; i++) f[i] = i; //并查集初始化
        dfs(root, 0);
    }
}

2.3.3. 评注

由于Tarjan算法中存询问和存边所用到的struct的内容和加边函数是一模一样的，为了省事儿，就把两个拼在一起了，否则程序会比较复杂，写起来也麻烦。其实仅仅把这个当成一个像 STL 一样的黑盒代码，只要明白有哪些内置函数和作用就行了，写完赶紧折叠起来，不然强迫症就真的要受不了了（眼不见为净QAQ）。

2.4. 树链剖分

2.4.1 主要思想

树链剖分求解LCA的行为与倍增法类似，都是往上跳。

但树链剖分与倍增法的思想完全不同。

对一棵树进行树链剖分之后会产生若干条重链和若干条轻边。学树链剖分的时候可以形象理解，认为重链是高速公路，而轻边是普通公路，理解的话就是重链可以一整条进行操作，而轻边只能一条一条进行操作。

那么我们可以构筑出如下算法：

有一个询问 LCA(T, u, v) ，目标是让 u 和 v 跳到同一条重链上，然后深度浅的就是结果。
选择链顶深度深的那个结点往上跳，这里要注意一下，不是深度深的结点往上跳，这个反例在上图中不能体现，重新画个大点的图就明白了。

其中蓝色的是重链，黑色的是轻边，考虑结点 u 和结点 v ，很显然它们的 LCA 是 w ，但是假如我们让深度深的 u 往上跳的话就是整个树的根了，显然不符合条件，反而链顶深度深的结点 v （只有一个结点组成的重链），往上跳直接跳到 w 结点，此时 u 和 v 在同一根重链上，而 v 的深度较浅，则返回 v 作为答案就可以了。而很显然的，如果结点 u 要往上跳，那么就要 u \leftarrow u->chain->top->father ，也就是跳到链顶的父亲上去，放心，肯定不会有结点跳到根以上的地方去的，因为根所在的重链链顶深度是最浅的，而且拥有这个深度的重链是唯一的。所以根所在的重链肯定不会往上跳，顶多是别的结点跳到了根所在的重链上。
接下来就只要重复第 2 步，直到条件 1 达成就可以了。

由于上跳是树链剖分的基本操作，而且主要学习的是树链剖分的思想，我就不给出具体的模拟过程了，其实只要看懂了上面对算法的说明，具体的实现就很简单了。

2.4.2.\ 参考代码及注释

两个板子：

数组版树链剖分

int father[MAXN], depth[MAXN], size[MAXN], dist[MAXN]; //树剖部分
int son[MAXN], top[MAXN];
bool visit[MAXN];
void dfs1(int u, int p, int d) {
    father[u] = p, depth[u] = d, size[u] = 1, son[u] = 0, visit[u] = true;
    int maxsize = 0;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to;
         if (v == p || visit[v]) continue;
        dist[v] = dist[u] + edge[i].dist;
        dfs1(v, u, d + 1);
        size[u] += size[v];
        if (size[v] > maxsize) {
            maxsize = size[v];
            son[u] = v;
        }
    }
}
void dfs2(int u, int anc) {
    top[u] = anc, visit[u] = true;
    if (son[u]) dfs2(son[u], anc);
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (v == father[u] || v == son[u] || visit[v]) continue;
        dfs2(v, v);
    }
}
namespace LCA {
    void init(int root) {
        dist[root] = 0;
        memset(visit, false, sizeof visit);
        dfs1(root, 0, 1);
        memset(visit, false, sizeof visit);
        dfs2(root, root);
    }
    long long query(int x, int y) {
        while (top[x] != top[y]) { //如果不在同一条重链上
            if (depth[top[x]] < depth[top[y]]) std::swap(x, y); //让x成为链顶深度较浅的结点
            x = father[top[x]]; //x上跳
        }
        if (depth[x] > depth[y]) std::swap(x, y);
        return x; //在同一条重链上时，深度浅的就是解
    }
}

链式树链剖分（比较惊世骇俗）

struct Node { //树链剖分部分
    struct Edge *head;
    struct Chain *chain;
    Node *father, *son;
    int size, depth, number, dist;
    bool visit;
} info[MAXN];
struct Edge {
    Node *from, *to;
    Edge *next;
    int dist;
    Edge(Node *from, Node *to, int dist) : from(from), to(to), next(from->head), dist(dist) {}
};
struct Chain {
    Node *top;
    Chain(Node *top) : top(top) {}
};
inline void AddEdge(int from, int to, int dist) { //链式专属前向星
    info[from].head = new Edge(&info[from], &info[to], dist);
    info[to].head = new Edge(&info[to], &info[from], dist);
}
void dfs1(Node *u) {
    u->visit = true;
    u->size = 1;
    for (Edge *e = u->head; e; e = e->next) {
        Node *v = e->to;
        if (!v->visit) {
            v->father = u;
            v->depth = u->depth + 1;
            v->dist = u->dist + e->dist;
            dfs1(v);
            u->size += v->size;
            if (!u->son || u->son->size < v->size) 
                u->son = v;
        }
    }
}
void dfs2(Node *u) {
    if (!u->father || u != u->father->son) 
        u->chain = new Chain(u);
    else u->chain = u->father->chain;
    if (u->son) dfs2(u->son);
    for (Edge *e = u->head; e; e = e->next) { 
        Node *v = e->to;
        if (v->father == u && v != u->son) 
            dfs2(v);
    }
}
namespace LCA {
    inline void init(int root, int n) {
        for (int i = 1; i <= n; i++)
            info[i].number = i;
        info[root].dist = 0;
        info[root].depth = 1;
        dfs1(&info[root]); //dfs的参数是指针，所以要取地址再执行
        dfs2(&info[root]);
    }
    int query(int x, int y) {
        Node *u = &info[x], *v = &info[y]; //取出地址
        while (u->chain != v->chain) {
            if (u->chain->top->depth < v->chain->top->depth) std::swap(u, v);
            u = u->chain->top->father;
        }
        if (u->depth > v->depth) std::swap(u, v);
        return u->number; //返回深度浅的结点的编号
    }
}

2.4.3. 评注

其实这里重要的是思想，而不是代码（因为每个人的树剖板子不一样啊）。

然而网上很多标题称是树剖的题解里面都是用树链剖分实现LCA，导致找树剖题目练手时一时间找不到好的题目做。

3. 对LCA问题的四种算法的小结

上面论述了LCA问题的四种常用的基本解法，回答询问强制在线的话可以考虑转化为RMQ问题或者使用树链剖分。如果不强制在线的话Tarjan，ST表，树剖均可，具体问题具体分析。