最近公共祖先(LCA)
riteme.site

最近公共祖先(LCA)

NOTICE: 这是一篇旧文,可能存在一些没有被勘察出的错误。另有一篇同主题的文章在此

1 概述

1.1 什么是LCA?

下面是一棵有根树,注意不一定是二叉树。

Sample Tree

我们先定义深度函数$ d(u): u \text{到根的最短距离} $

例如,在上图中$ d(1)=0,\,d(3)=1,\,d(9)=3$

我们再定义一个函数$ LCA(u, v) $表示节点$ u $$ v $的最小公共祖先。

其定义为:
$$ LCA(u,v):u和v的所有祖先p中,d(p)最大 $$

举个例子:$ LCA(5,6)=3,\,LCA(7,6)=3,\,LCA(1,8)=1 $

应该很简单吧。

1.2 有什么卵用?

一个简单的例子,计算完LCA后,可以在$ \Theta (1) $的时间内算出任意两点的距离。

还是下面这个图解释:

Sample Tree With Weight

上面的树边上带了权重,两点之间的距离就是两点间的简单路径上的边权之和。

例如$ distance(1,1)=0,\,distance(2,3)=3,\,distance(7,6)=6$

如果用DFS或BFS来计算的话,需要$ O(n) $的时间复杂度。

如果先预处理LCA,就只需$ \Theta (1) $的时间。

先不考虑是如何算出LCA的,先讲下如何快速求距离。

上图中,dist数组表示节点到树根的距离,在图中已经计算出来。
这个数组很好计算,根据下面的公式直接将树BFS一遍即可,其中$ u $$ v $的父节点,$w[u, v]$表示$ u $$ v $的边权。
$$ dist[v] = dist[u] + w[u,v] \tag{1.1}$$

那么两点之间的距离$ distance(u,v) $的计算非常简单:
$$ distance(u,v) = dist[u] + dist[v] - 2 \times dist[LCA(u, v)] \tag{1.2} $$

可以想象成是Link这个人从$ u $先走到根节点,再从根节点走到$ v $。由于从根节点到$ LCA(u,v) $走了两遍,因此Link走的总路程,减去这一段来回走的即可。

1.3 预备知识

因为LCA的算法中会用到并查集,但我们还没学,因此并查集的实现不会过多纠结,我们只需知道并查集提供的几个函数即可。

并查集提供查询和连接操作:

1
2
def find(u) -> int
def union(u, v) -> void
  • find函数会返回节点u所在的集合编号,如果find(a) == find(b)则表示ab处在一个集合中。

  • union函数会将uv所在的集合并起来,即使uv处在一个集合中。

后面会提到在线离线的概念,只要知道离线是先将所有操作读入后再作处理就行了。

2 LCA算法

计算LCA的算法有很多,这里介绍三个。

2.1 朴素算法

朴素算法是最简单的了,按照国际惯例,先放图:

Sample Tree

朴素算法的做法如下:

  1. 先将两个结点调为同一深度
  2. 将两个结点同时上调,直到这两个结点到达同一位置时,此时即为LCA

伪代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def Plain_LCA(u, v):
    if d(u) < d(v):
        swap(u, v)  # 始终保持u所处的深度较深

    while d(u) != d(v):
        u = father(u)  # 将u上调

    # 将u和v同时上调
    while u != v:
        u = father(u)
        v = father(v)

    # 最后会使u == v,即他们到达了LCA
    return u

2.2 离线算法:Tarjan-LCA

朴素算法很简单,大多数情况下能很快算出LCA。

然而在计算$ LCA(4,6) $时,需要从树的底部走到根节点。

因此朴素算法的时间复杂度为$ O(n) $,很容易TLE。

因此我们的前人想出了机智的Tarjan-LCA算法!

Tarjan-LCA算法比较难理解,最好的理解方法是手动模拟一下。
先放出伪代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def Tarjan_LCA(u):
    # ancestor数组表示一个集合的公共祖先
    # 如ancestor[i]表示标号为i的集合中所有结点的公共祖先。
    # marked数组表示结点是否被处理过

    ancestor[find(u)] = u

    for v in u.children:  # 遍历u的儿子节点
        Tarjan_LCA(v)
        union(u, v)
        ancestor[find(u)] = u

    marked[u] = true

    # query数组表示查询操作,保存的是(x, y),表示要计算LCA(x, y)
    for (x, y) in query:
        if y == u and marked[x] == True:
            LCA(x, y) = LCA(y, x) = ancestor[find(x)]

这个算法的进行类似于DFS,是个递归调用的过程。
因为DFS总是先将小的子树遍历完,因此ancestor数组中的祖先都是尽可能小的。

拿一棵较小的子树作为示例:

Sample Subtree

一开始先DFS到7处。

Step 1

处理到7时还并没有什么结点被处理过,只好默默的回到5。

Step 2

5处将7和自己相连,形成集合{5, 7}5是这个集合的公共祖先。

Step 3

现在DFS到9

Step 4

假设我们询问了$ LCA(7,9) $,那么在处理9时,会发现7被处理过了,7所在的集合的公共祖先为5
9是从5递归下来的,因此97的公共祖先中有5
又因为DFS会尽可能的处理较小的子树,因此5将会是$ LCA(7, 9) $

剩下的步骤都是一样的,大家可以自己手推一下。

为了方便理解,大家可以将Tarjan-LCA算法换个说法:

一个熊孩子Link从一棵有根树的最左边最底下的结点灌岩浆,Link表示很讨厌这种倒着长的树。
岩浆会不断的注入,直到注满整个树…

如果岩浆灌满了一棵子树,Link发现树的另一边有一棵更深的子树,Link会先去将那棵子树灌满。

岩浆只有在迫不得已的情况下才会向上升高,找到一个新的子树继续注入。

机(yu)智(chun)的Link发现了找LCA的好方法,即如果两个结点都被岩浆烧掉时,他们的LCA即为那棵子树上岩浆最高的位置。

Tarjan-LCA算法能在$ \Theta (n + q) $时间内计算出所有询问的LCA,其中$ q $为询问总数。
这得益于并查集的高效。
同样我们也能以此算出所有点对的LCA。

2.3 在线算法:倍增法

Tarjan-LCA算法速度很快,效果也很好,但有一个致命的问题…

就是内存占用。

首先它需要离线操作,如果空间比较紧且操作较多时,显然不合适。

另外,如果要处理任意结点对的LCA,就需要一个巨大的二维数组来存储,这意味着如果$ n > 10000 $此算法将报废。

但如果用朴素算法,就又太慢了…

这时,倍增法就来拯救世界了。

倍增法能以$ \Theta (\log n) $的时间复杂度和$ \Theta (n \log n) $的空间复杂度内完成LCA的计算。

相比与Tarjan-LCA的$ \Theta (n^2) $的空间复杂度,能节省更多的空间。
并且它是在线算法,弥补了LCA算法的不足。

倍增法运用了动态规划的思想,并利用二进制达到了$ \Theta (\log n) $的时间复杂度。

2.3.1 预处理

倍增法首先需要计算一个f数组,其含义为:
$$ f[i, j] : 离节点i相距2^j的父节点 $$

换言之
$$ distance(i, f[i, j]) = 2^j \tag{2.1} $$

Sample Tree

又是这个图。我们将树上的每一条边的长度都视为1,那么$ f[7, 0] = 5,\,f[7, 1] = 3 ... $
因此节点$ 5 $$ 7 $的距离为$ 1 = 2^0 $,节点$ 3 $$ 7 $的距离为$ 2 = 2^1 $
由此我们可以观察到f数组的一个特点:$ f[i, 0] $就是$ i $的父节点。

为了算出f数组,我们有如下的状态转移方程:
$$ f[i,j] = f[f[i, j - 1], j - 1] \tag{2.2} $$

如何理解这个转移方程呢?

我么设$ u = f[i,j],\,v=f[i, j-1] $

那么,根据$ (2.1) $式可得:

$$ \begin{aligned} distance(i, v) & = 2^{j-1} \\ distance(i, u) & = 2^j \\ distance(v, u) & = distance(i, u) - distance(i, v) \\ & = 2^j-2^{j-1} \\ & = 2^{j-1} \times 2 - 2^{j-1} \times 1 \\ & = 2^{j-1} \\ & \Rightarrow u = f[v, j - 1] \\ & \Rightarrow u = f[f[i, j-1],j-1] \end{aligned} $$

即证明$ (2.2) $式。

利用得到的状态转移方程,我们可以在$ \Theta (n \log n) $的时间内推出f数组。

1
2
3
4
5
6
7
8
# 初始化f[i, 0]
for i in [1, n]:
    f[i, 0] = father(i)

# 计算整个f数组
for j in [1, log(n)]:
    for i in [1, n]:
        f[i, j] = f[f[i, j - 1], j - 1]

2.3.2 在线算法

得到了f数组后,倍增法也就完成了50%了,剩下的任务就是计算LCA。

事实上,倍增法计算LCA的过程与朴素算法一样,也是要先调制同一深度,再同时上调。
而巧妙的是倍增法利用算出的f数组来加速提升的过程,使得节点的上升的距离可以达到$ 2^j $,而不是一格一格往上调。

思路已经很清晰了,然而难在如何运用f数组。

下面的伪代码展示了倍增法求LCA的过程:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def Double_LCA(u, v):
    if d(u) < d(v):
        swap(u, v)  # 始终保持u所处的深度较深

    # 将u上调dist个距离
    dist = d(u) - d(v)
    for i in [0, log(n)]:
        if (1 << i) & dist  # KEY #1
            u = f[u, i]

    if u == v:
        return u  # 特判此时u, v是否在同一位置,如果是,u和v都站在LCA上

    # 将u和v同时上调
    for i from log(n) to 0:
        if f[u, i] != f[v, i]:  # KEY #2
            u = f[u, i]
            v = f[v, i]

    # 最后会使u和v成为LCA的子节点
    return f[u, 0]

在代码中有两处比较奇特的地方,被注释打上了KEY

先看KEY #1,这里的代码是尝试将$ u $$ v $调制统一高度,而这里出现的位运算令人十分费解。

首先我们思考一下二进制:
对于一个二进制数$ k $,设其从右往左数的第$ i $位为$ k_i $,则当$ k_i = 1 $时,$ k - 2^{i-1} $的第$ i $位为$ 0 $

例如,对于二进制数$ 110010_{(2)} $,第$ 2 $位为$ 1 $$ 2^1 = 10_{(2)} $$ 110010_{(2)} - 10_{(2)} = 110000_{(2)} $,我们发现这个二进制数的第$ 2 $位变成了$ 1 $

利用这个特性,我们可以逐位将一个二进制数减成$ 0 $

在上面的代码中,就这样逐步上调节点$ u $,并使最后的深度差dist变为$ 0 $
下面有一张样例:

Sample #1

再来看KEY #2,此时$ u $$ v $处在同一深度上,$ j $从大到小逐一测试。

我们试图使$ u $$ v $尽可能靠近LCA,但又不直接到达LCA。

如果说$ 2^j $的距离上,$ u $$ v $的父节点相同,则这个父节点是它们的公共祖先,如果跳上去就有可能超过LCA了,因此忽略。

如果说$ 2^j $的距离上,$ u $$ v $的父节点不同,则$ f[u, j] $$ f[v, j] $的LCA也是$ u $$ v $的LCA,因此可以将$ u $$ v $上移至该位置,不影响结果。

因为这两个节点到LCA的深度差可以被分解成多个$ 2 $的幂之和,因此我们有办法逐步将它们上移至LCA的位置。

但是为了方便判断是否跳的太远,我们不让它们最后跳到LCA的位置,而是跳到LCA的儿子节点处。

此时其父节点就是LCA。

下面有一张样例:

Sample #2

至此,倍增法就结束了。

以上三种算法是比较常见的求LCA的算法。似乎二叉树还有一种分治的LCA算法,我没有做过多了解了。