最近公共祖先（LCA）

定义

最近公共祖先（Lowest Common Ancestor）简称 LCA。对于一个树上的两个节点的最近公共祖先，是这两个点中的公共祖先里面离根最远的一个。性质可见 OI Wiki。

向上标记法

过程

在两点中取得深度较大的一个点，让它不停的向上跳，同时标记所经过的每一个点，直到根节点，接着让另一个点不断向上跳，跳到的第一个被标记的点就是这两个点的 LCA。

时间复杂度

预处理树的深度的时间复杂度为 O(n)O(n)，单次查询的时间复杂度最坏情况下为 O(n)O(n)。

倍增算法

过程

我们可以定义一个数组 prei,kpre_{i, k} 表示编号为 ii 的点向上跳 2k2^k 次所到达的点。不难看出 prei,0pre_{i, 0} 表示的是节点 ii 的父亲。对于任意的 k≥1k \ge 1，prei,kpre_{i, k} 都相当于连续上跳两次 2k−12^{k - 1}，满足以下的递推式：

prei,k=preprei,k−1,k−1pre_{i, k} = pre_{pre_{i, k - 1}, k - 1}

因此根据每个节点的父亲就可以递推出整个 prepre 数组。以上所有操作均可以在 dfs 或者 bfs 的初始化中实现。

假设我们求出了所有节点的 depthdepth 数组。对于任意的两个节点 u,vu,v，它们的深度之差即为 h=depthu−depthvh = depth_u - depth_v ，我们可以使用多重背包优化中的二进制拆分的思想，将 hh 分为至多 log⁡h\log h 个数，从而达到 O(log⁡h)O(\log h) 的时间复杂度进行预上跳。

进行预上跳之后，特判一下此时的两个节点是否已经相同。如果不同，从 prepre​ 数组的第二维从大到小依次上跳找到第一个不是他们两个祖先的两个点，让两个点依次跳到这两个点。

最后所求的 LCA(u,v)\text{LCA}(u, v) 便是这两个点的父亲，即 preu,0pre_{u, 0}。

时间复杂度

dfs 或 bfs 进行预处理所花的时间复杂度均为 O(n)O(n)，进行 prepre 数组递推式处理的时间复杂度为 O(nlog⁡n)O(n \log n)，单次询问的时间复杂度为 O(log⁡n)O(\log n)。

模板代码

bfs 预处理 + 递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void bfs(int root)
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0, depth[root] = 1;
    queue<int> q;
    q.push(root);

    while (!q.empty())
    {
        int t = q.front(); q.pop();
        
        for (auto y : g[t])
        {
            if (depth[y] > depth[t] + 1)
            {
                depth[y] = depth[t] + 1;
                q.push(y);
                pre[y][0] = t;
                for (int k = 1; k <= 19; k ++)
                    pre[y][k] = pre[pre[y][k - 1]][k - 1];
            }
        }
    }
}

dfs + 递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs(int ver, int fa, int dep)
{
    pre[ver][0] = fa;
    depth[ver] = dep;
    for (auto y : g[ver])
        if (y != fa)
            dfs(y, ver, dep + 1);
}

void init()
{
    for (int j = 1; i <= 19; ++j)
        for (int i = 1; i <= n; ++i)
            pre[i][j] = pre[pre[i][j - 1]][j - 1];
}

求 LCA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int lca(int a, int b)
{
    if (depth[a] < depth[b]) swap(a, b);
    
    for (int k = 19; k >= 0; k --)
        if (depth[pre[a][k]] >= depth[b])
            a = pre[a][k];

    if (a == b) return a;

    for (int k = 19; k >= 0; k --)
        if (pre[a][k] != pre[b][k])
            a = pre[a][k], b = pre[b][k];
            
    return pre[a][0];
}