LCA Notes

LCA(Lowest Common Ancestor)称为最近公共祖先。在一棵树中，两个结点u和v的LCA是从根结点到u和v的路径上最深的公共结点，也是u和v之间唯一最短路径上的深度最小的结点。在某些场景下，LCA也可以用于描述两个结点在有向无环图(DAG)中的公共祖先。

倍增法是一种高效的预处理技术，其核心思想在于预先计算每个结点向上跳跃2k步后所到达的结点。这种“倍增”策略使得我们能够迅速跨过任意数量的步骤，直达所需的结点。

倍增法求LCA的步骤：在倍增法求解LCA（最近公共祖先）的过程中，我们构建一个二维数组fa[N][20]​，其中20表示可以追踪到每个结点向上最多跳跃$2^{20}$步的祖先。对于大多数图结构而言，这样的深度已经足够使用；若遇到特殊情况，则可以适当增大此值。

考虑一棵有根树，我们可以使用以下方法预处理每个结点的2的整数幂祖先：

  1. 使用DFS从根结点开始遍历整棵树。
  2. 对于树上的每个结点u，其直接父结点是其距离为$2^0=1$的祖先，假设v为u的父结点，则有fa[u]​[0]=v。
  3. 使用先前计算的结果，结点u距离为$2^i$的祖先是结点u距离为$2^(i-1)$的祖先的距离为2^(i-1)的祖先，换句话说，就是先往上跳$2^(i-1)$步，再跳$2^(i-1)$步，相当于跳了$2^(i-1)$步。
  4. 如果往上跳$2^i$步不存在任何结点，怎么办？没关系，直接让这个祖先等于0，表示不存在，并且有fa[0]\​[i]=0。即虚拟结点0的父结点指向自己，根结点的父结点是虚拟结点0。
  5. 预处理完成后，给定任意两个结点u和v，我们可以使用其预处理的祖先信息，结合贪心思想，在O($logn$)时间内高效地找到它们的最近公共祖先LCA。

假设我们要求x、y两点的LCA，可按照以下步骤执行：

  1. 不妨设dep[x]≥dep[y]​，即结点x在结点y的下方，我们想办法让结点x和结点y达到相同的深度，方法是让结点x贪心地向上跳。每次结点x跳到fa[x]​[i]​，若dep[fa[x]​[i]​]≥dep[y]则跳，i从大到小枚举。这样一定能跳到与结点y同层的位置。
  2. 当dep[x]==dep[y]后，先检查结点x与结点y是否相等。若相等，则说明结点x（或结点y）就是最初的结点x和结点y的最近公共祖先(LCA)。
  3. 若不相等，让结点x和结点y一起向上跳，只要它们不会跳到相同的结点，就跳。这样最后一定会分别得到最近公共祖先的两个子结点的位置。
  4. 最后fa[x]​[0]或fa[y]​[0]就是最初结点x和结点y的最近公共祖先。

倍增法代码模板

下面给出倍增法模板。DFS 中需要判断父节点，避免无向树 DFS 时回到父节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int LOG = 21;

int n, q;
vector<int> g[N];      // 建图
int fa[N][LOG];        // fa[x][j] 记录 x 向上跳 2^j 步到达的节点编号
int dep[N];            // 记录深度

// 深度优先搜索，计算 dep 和 fa 数组
void dfs(int x, int parent)
{
    fa[x][0] = parent;
    dep[x] = dep[parent] + 1;

    for (int j = 1; j < LOG; ++j)
    {
        fa[x][j] = fa[fa[x][j - 1]][j - 1]; // 计算 2^j 祖先
    }

    for (auto y : g[x])
    {
        if (y == parent) continue;
        dfs(y, x);
    }
}

// 计算最近公共祖先
int lca(int x, int y)
{
    if (dep[x] < dep[y])
    {
        swap(x, y); // 确保 x 深度较大
    }

    // 先让深度大的点跳到同一深度
    for (int j = LOG - 1; j >= 0; --j)
    {
        if (dep[fa[x][j]] >= dep[y])
        {
            x = fa[x][j];
        }
    }

    // 如果 y 本身就是 x 的祖先
    if (x == y)
    {
        return y;
    }

    // 一起向上跳，直到二者即将跳到同一个父节点
    for (int j = LOG - 1; j >= 0; --j)
    {
        if (fa[x][j] != fa[y][j])
        {
            x = fa[x][j];
            y = fa[y][j];
        }
    }

    return fa[x][0];
}