最近公共祖先(LCA)

最近公共祖先是树上的概念，不了解树的出门左转百度： 树（数据结构名词）_百度百科 。

定义

假设我们需要求 x 和 y 的最近公共祖先，这里有多种等价的定义 。

• 路径 x 到 y 上深度最小的点 。

• x 和 y 公共祖先中深度最大的点 。

• x 和 y 在这棵树上距离最近的公共祖先结点 。

如果 x 就是 y 的祖先，则 x 本身就是两者的最近公共祖先 。

求法

通常来说有四种 。

• 树上倍增 。

• dfs序与ST表 。

• 树链剖分 。

• Tarjan (离线算法) 。

这里我们只讨论前三种在线算法 。

方法一：树上倍增

倍增的思想可以看一下这篇文章： 算法学习笔记(3): 倍增与ST算法 。

这是基于朴素方法的优化，所以在讲树上倍增之前我们还需要讲一下朴素的方法 。

---

朴素算法

选择 x 和 y 中深度较大的点，向上跳直到两者深度相同，然后两者同时向上跳直到两者第一次相遇，此时两者所在即是最近公共祖先 。

---

显然，我们每次只跳一个显然不优，所以借鉴倍增与二进制拆分的思想 。

令 fa[x][k] 指从 x 开始，向上跳 2^k 次所能达到的祖先，特别的，如果深度不够，则 fa[x][k] = 0 。

那么，基于朴素算法的流程：我们只需要跳的时候利用倍增的思想就行了 。

这里给出一种参考代码:

notice : 这其实不是一种特别好的写法 。

                        
                          int lca(int x, int y) {
    int p;
    // 这里保证了x是深度相对较大那一个
    if (dep[x] < dep[y]) p = x, x = y, y = p;

    // 将x跳到与y深度相同的位置
    p = 0;
    while (p >= 0) {
        if (dep[fa[x][p]] >= dep[y]) x = fa[x][p], ++p;
        else --p;
    }

    // 达到同样深度就已经相遇（y是x的祖先）
    if (x == y) return x;

    // 两者同时向上跳直到相遇
    p = 0;
    while (p >= 0) {
        if (fa[x][p] != fa[y][p]) x = fa[x][p], y = fa[y][p], ++p;
        else --p;
    }
    // 最后还要向上跳一个才是公共祖先
    // 通过这种倍增写法得出的位置是最后一个满足if条件的位置！！！
    return fa[x][0];
}

                        
                      

那么问题来了，如何初始化?

显而易见，跳 2^k 步相当于跳 2 次 2^(k-1) 步，所以有了 。

                        
                          fa[x][i] = fa[fa[x][i - 1]][i - 1];

                        
                      

复杂度分析

在初始化的时候每一个点都需要 O(logN) ，那么总初始化需要 O(NlogN) 。

在询问时，令 k 为 x , y 到最近公共祖先的最大距离，根据倍增算法，则复杂度为 O(logk) ，当树退化成一条链时， k 最大取到 n ，那么最终复杂度应该为 O(logN) 。

综上，初始化需要 O(NlogN) ，单次询问需要 O(logN) 。

方法二：dfs序与ST表

这种方法相对难以理解，所以读者可以在掌握了一般的Tarjan缩点算法后再理解（这两个算法几乎没有关系，但是一些思想在Tarjan中有所体现) 。

下文中不是特别明白名词在后文中有所提及，或者可以参考讲解Tarjan算法的文章 。

先求出树每一个结点的 dfn ，不妨令 x 比 y 更先遍历到（ dfn[x] < dfn[y] ） 。

• 若 x 不是 y 的祖先

在 dfs 序列中，区间 [dfn[x], dfn[y]] 内一定包含了LCA子树的部分，但不包含LCA及其祖先，并且该区间一定包含了LCA到 y 路径上的第一个儿子，而且它的深度是最小的 。

所以，我们只需要找到区间 [dfn[x], dfn[y]] 中深度最小的点，它的父结点就是LCA 。

• 若 x 是 y 的祖先，则 x 就是LCA，且 x 是区间 [dfn[x], dfn[y]] 中深度最小的点，与上述情况不太一样，那么考虑我们将 x 排除在区间外，则在区间 [dfn[x] + 1, dfn[y]] 中深度最小的点的父亲结点就是 x 。返回考虑第一种情况，由于第一种情况 x 一定不是LCA，那么将区间替换为 [dfn[x] + 1, dfn[y]] 不影响答案。

综上，我们只需要求区间 [dfn[x] + 1, dfn[y]] 中深度最小的点的父结点即可.

初始化与查询

定义 rdfn 满足 x == rdfn[dfn[x]] ，ST表初始化时 f[i][0] = rdfn[i] .

其实可以只需要 dfn 就ok， f[dfn[i]][0] = i 。

定义区间操作 。

                        
                          int Min(int x, int y) {
    return depth[x] < depth[y] ? x : y;
}

                        
                      

定义查询操作 。

                        
                          int query(int x, int y) {
    if (x == y) return x; // 同一个结点啊
    // 确保x是先遍历到的那一个结点
    if (dfn[x] > dfn[y]) std::swap(x, y);
    int k = log(dfn[y] - dfn[x]);
    return Min(f[dfn[x] + 1][k], f[dfn[y] - (1<<k) + 1][k]);
}

                        
                      

其余的就套模板就行了 。

复杂度分析

初始化其实主要是ST表的初始化，所以初始化的复杂度为 O(NlogN) （实际上应该是 O(N + NlogN ） 。

查询也是ST表的区间查询，复杂度为 O(1) 。

方法三：树链剖分

好高级的名字…… 。

树链剖分指将一棵树分割为若干条链，以维护树上信息。它包含重链剖分、长链剖分、实链剖分，在没有特殊说明的情况下，树链剖分一般指代重链剖分。这里也着重描述重链剖分.

这里先给出一些 。

DFS序

dfs序指dfs的顺序。具体方法是用一个计数变量cnt，遍历到结点x时，时间戳 dfn[x] = ++cnt ，对应dfs序列中第cnt个就是x 。

而上文定义中的 rdfn 则可以在同时通过 rdfn[cnt] = x 记录下来 。

性质

• 结点的 dfn 大于其任意父结点 。

• 对于任意结点（包含本身）的子树中，存在一个 dfn 是连续的一条链 。

如果子树在dfs序列中是连续的一段，在维护子树（子树求和之类的子树操作）时，直接把它看做一个序列，那么就和在线段树上操作没有区别了 。

重链

相邻重边链接形成的链 。

重边

重子结点（如果有）与其父结点相连的边 。

重子结点

一个结点的子结点中度最大的结点 （孩子个数最多的点） 。

剖分方法

重链剖分就是将每一条重链单独划分出来，从而通过 dfn 来维护链上信息 。

至于如何剖分，需要进行两次遍历 。

第一次遍历，获得所有节点的 siz , dep , fa , son 。

这里 siz 指结点的度， 三个字符统一一下，fa是个例外 ， dep 指结点的深度， fa 指结点的父结点， son 指结点的重子结点 。

第二次遍历，获得所有点的 dfn , top 。

这里 dfn 无需解释， top 指结点所在重链最顶部的结点 。

思路清晰，这里给出一种 参考 写法 。

注意前提，点编号从 1 ~ n ，且这里用的是前向星存图 （树） 。

                        
                          int top[N], dfn[N], son[N], dep[N], siz[N], fa[N];
// work son, siz, dep and fa
void workSSDF(int x, int par) {
    dep[x] = dep[par] + 1, fa[x] = par, siz[x] = 1;
    for (int y, i = head[x]; i; i = edge[i].next) {
        y = edge[i].to;
        if (y == par) continue;
        workSSDF(y, x);
        siz[x] += siz[y];
        if (siz[y] >= siz[son[x]]) son[x] = y;
    }
}

// work dfn and top
int cdfn = 0;
void workDT(int x, int ptop) {
    dfn[x] = ++cdfn, top[x] = ptop;
    if (son[x]) workDT(son[x], top[x]);

    for (int y, i = head[x]; i; i = edge[i].next) {
        y = edge[i].to;
        if (!dfn[y]) workDT(y, y);
    }
}

                        
                      

剖分作用

这么麻烦的求这个树链剖分有啥用?

如果我们随便画一个图并模拟一下上述过程…… 。

在两次遍历完之后:

考虑用纯markdown画图是真的难受，但树的结构是一样的……T^T 。

我们很容易发现，在同一条重链上的结点的 dfn 序是连续的……（这我们稍后在论述） 。

回到求LCA的流程，由于我们把树分为了从上到下的一些链 。

注意每一条链中没有深度相同的结点 。

所以，我们只需要不断的把两个结点通过 top 向上跳直到在同一条链上（此时 top[x] == top[y] ） 。

至于为什么要跳 top 结点的深度较大的结点……还请读者自行讨论 。

有一个需要注意的地方，不能直接 x = top[x] ，因为 top[top[x]] == top[x] !!.

所以还需要跳到 top[x] 的父节点上 。

流程清晰，这里给出一种参考代码 。

                        
                          int lca(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] >= dep[top[y]]) x = fa[top[x]];
        else y = fa[top[y]];
    }
    if (dep[x] <= dep[y]) return x;
    return y;
}

                        
                      

复杂度分析

太难写了 Q^Q 。

依据重链的定义，每一条重链至少占了重链顶端结点所在的子树结点的 \(logN\) 个结点（一条链就占满了） 。

所以，剖分之后差不多是有 \(logN\) 条重链，所以每次询问至多跳 \(logN\) 次，所以…… 。

初始化复杂度为 O(N) (两次dfs)，查询复杂度为 O(logN) 。

树链剖分拓展

看我的另一篇文章吧，太难写了，四千多个字呜啊 。

最后此篇关于算法学习笔记(5):最近公共祖先(LCA)的文章就讲到这里了,如果你想了解更多关于算法学习笔记(5):最近公共祖先(LCA)的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。