浅谈 LCA

作者：Gemini 2.5 flash

---

简介

在图论中，最近公共祖先（LCA） 是指在一棵树中，距离两个给定节点最近的公共祖先节点。寻找LCA是树结构算法中的一个经典问题，在很多应用中都有重要作用，比如在计算基因序列的相似性、文件系统路径查找等方面。

1. 朴素算法

实现思路

朴素算法通常指的是最直观、最简单的暴力解法。对于LCA问题，一种朴素的思路是：

1. 提升深度一致：将两个节点中深度较大的节点向上移动，直到它们与深度较小的节点处于同一深度。
2. 同时上移：两个节点再同时向上移动，直到它们相遇。相遇的节点就是它们的LCA。

这种方法简单易懂，但在极端情况下（例如，树退化成链），时间复杂度会很高。

核心代码示例

// 假设父节点数组 parent 和深度数组 depth 已预处理
int get_lca_naive(int u, int v) {
    // 确保 u 的深度不小于 v
    if (depth[u] < depth[v]) {
        swap(u, v);
    }
    // 将 u 提升到与 v 相同深度
    while (depth[u] > depth[v]) {
        u = parent[u];
    }
    // 如果 u 已经是 v 的祖先，或者 v 已经是 u 的祖先（经过深度调整后），则它们就是LCA
    if (u == v) {
        return u;
    }
    // 同时向上移动，直到相遇
    while (parent[u] != parent[v]) {
        u = parent[u];
        v = parent[v];
    }
    return parent[u]; // 相遇点的父节点即为LCA
}

2. 倍增法

实现思路

倍增法（Binary Lifting）是LCA问题的一种高效解决方案。其核心思想是预处理出每个节点向上跳 $2^k$ 步所能到达的祖先节点。

1. 预处理 up[i][k]：up[i][k] 表示节点 i 向上跳 $2^k$ 步所能到达的祖先。
   • up[i][0] 即为 i 的父节点。
   • up[i][k] = up[up[i][k-1]][k-1]，这意味着向上跳 $2^k$ 步等同于向上跳 $2^{k-1}$ 步两次。
2. 深度一致：首先将两个节点中深度较大的节点向上移动，使其与深度较小的节点处于同一深度。这里利用倍增思想，可以通过一次跳跃多个 $2^k$ 步来快速调整深度。
3. 同时上移：如果此时两个节点相同，则它就是LCA。否则，两个节点同时向上跳。为了找到最近公共祖先，我们从大到小枚举 $k$，如果 up[u][k] 和 up[v][k] 不同，则将 u 和 v 同时向上跳 $2^k$ 步。这样操作之后，u 和 v 的父节点就是它们的LCA。

核心代码示例

const int MAXN = 100005;
const int LOGN = 17; // log2(MAXN)
vector<int> adj[MAXN];
int depth[MAXN];
int up[MAXN][LOGN]; // up[i][k] 表示节点i向上跳2^k步的祖先

void dfs_lca(int u, int p, int d) {
    depth[u] = d;
    up[u][0] = p; // 向上跳2^0步就是父节点
    for (int k = 1; k < LOGN; ++k) {
        up[u][k] = up[up[u][k - 1]][k - 1]; // 倍增计算
    }
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs_lca(v, u, d + 1);
    }
}

int get_lca_binary_lifting(int u, int v) {
    if (depth[u] < depth[v]) {
        swap(u, v);
    }
    // 调整深度，使 u 和 v 位于同一深度
    for (int k = LOGN - 1; k >= 0; --k) {
        if (depth[u] - (1 << k) >= depth[v]) {
            u = up[u][k];
        }
    }
    if (u == v) {
        return u;
    }
    // 同时向上跳，找到LCA
    for (int k = LOGN - 1; k >= 0; --k) {
        if (up[u][k] != up[v][k]) {
            u = up[u][k];
            v = up[v][k];
        }
    }
    return up[u][0]; // 返回它们的父节点
}

// 在主函数中调用：
// dfs_lca(root, 0, 0); // root为根节点，0为虚拟父节点，0为根节点深度

3. Tarjan 算法 (离线算法)

实现思路

Tarjan算法是一种离线LCA算法，它需要将所有的LCA查询预先存储起来，然后一次性处理。它基于并查集（Disjoint Set Union, DSU）和深度优先搜索（DFS）。

1. DFS遍历：对树进行DFS遍历。
2. 并查集维护：在DFS过程中，使用并查集来维护已经访问过的节点的集合。每个集合的代表元（root）是该集合中深度最小的节点。
3. 标记节点状态：
   • 当一个节点 u 第一次被访问时，将其标记为“正在访问中”（通常通过颜色标记）。
   • 当DFS回溯到 u 时，说明 u 的所有子树都已访问完毕。此时将 u 加入其父节点的并查集，并将其标记为“已访问完毕”。
4. 处理查询：对于每个LCA查询 (u, v)：
   • 当DFS遍历到 u 时，检查所有与 u 有LCA查询的另一个节点 v'。
   • 如果 v' 已经被标记为“已访问完毕”，那么 LCA(u, v') 就是 find(v') 的代表元。因为当 v' 访问完毕并回溯时，它会与它的父节点合并，find(v') 就会指向 v' 所在子树的祖先。而LCA恰好就是当 u 和 v' 同时都在其回溯路径上时，它们合并后的代表元。

核心代码示例

const int MAXN = 100005;
vector<int> adj[MAXN];
vector<pair<int, int>> queries[MAXN]; // queries[u] 存储与u相关的查询 {v, query_id}
int parent[MAXN]; // 并查集父节点
int ancestor[MAXN]; // 并查集每个集合的代表元
bool visited[MAXN];
int ans[MAXN]; // 存储查询结果

// 并查集查找函数，路径压缩
int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

// 并查集合并函数
void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b)
        parent[b] = a;
}

// Tarjan LCA函数
void tarjan_lca_dfs(int u, int p) {
    parent[u] = u; // 初始化并查集
    ancestor[u] = u; // 初始代表元是自己
    visited[u] = true;

    for (int v : adj[u]) {
        if (v == p) continue;
        tarjan_lca_dfs(v, u);
        union_sets(u, v); // 将v合并到u的集合
        ancestor[find_set(u)] = u; // 更新合并后的代表元为u
    }

    // 处理与 u 相关的查询
    for (auto& q : queries[u]) {
        int v = q.first;
        int query_id = q.second;
        if (visited[v]) { // 如果 v 已经访问过
            ans[query_id] = ancestor[find_set(v)];
        }
    }
}

// 在主函数中调用：
// for (int i = 1; i <= n; ++i) parent[i] = i; // 初始化并查集
// tarjan_lca_dfs(root, 0); // root为根节点，0为虚拟父节点

4. 树链剖分

实现思路

树链剖分（Heavy-Light Decomposition, HLD）可以将树上的路径操作转化为序列上的操作。虽然它主要是用来解决路径和子树查询问题，但也可以用来求LCA。

1. 两次DFS：
   • 第一次DFS：计算每个节点的深度 depth、父节点 parent、子树大小 size，并找出每个节点的重子节点（子树大小最大的子节点）。
   • 第二次DFS：进行重链剖分。从根节点开始，优先遍历重子节点，将重子节点连接起来形成重链。同时为每个节点分配一个DFS序 dfn，并将重链上的节点映射到连续的区间。维护每个节点所在重链的链顶 top。
2. LCA查询：
   • 当查询 LCA(u, v) 时，如果 u 和 v 不在同一条重链上，就将深度较大的节点 u（或 v）向上跳到其所在重链的链顶的父节点。重复此过程，直到 u 和 v 在同一条重链上。
   • 当 u 和 v 在同一条重链上时，深度较浅的那个节点就是LCA。

核心代码示例

const int MAXN = 100005;
vector<int> adj[MAXN];
int sz[MAXN], son[MAXN], depth[MAXN], fa[MAXN]; // size, heavy_son, depth, parent
int top[MAXN], dfn[MAXN], rnk[MAXN], timer; // top_of_chain, dfs_order, rank_in_dfs_order, timer

void dfs1(int u, int p, int d) {
    depth[u] = d;
    fa[u] = p;
    sz[u] = 1;
    son[u] = 0; // 重子节点初始化为0

    for (int v : adj[u]) {
        if (v == p) continue;
        dfs1(v, u, d + 1);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) { // 找到重子节点
            son[u] = v;
        }
    }
}

void dfs2(int u, int t) { // t 是当前链的顶部节点
    dfn[u] = ++timer;
    rnk[timer] = u; // 记录dfs序对应的节点
    top[u] = t;

    if (son[u]) { // 优先处理重子节点，形成重链
        dfs2(son[u], t);
    }

    for (int v : adj[u]) {
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v); // 处理轻子节点，开启新的重链
    }
}

int get_lca_hld(int u, int v) {
    while (top[u] != top[v]) { // 不在同一条重链上
        if (depth[top[u]] < depth[top[v]]) {
            swap(u, v);
        }
        u = fa[top[u]]; // 向上跳到链顶的父节点
    }
    // 在同一条重链上，深度小的就是LCA
    return depth[u] < depth[v] ? u : v;
}

// 在主函数中调用：
// dfs1(root, 0, 0); // root为根节点，0为虚拟父节点，0为根节点深度
// dfs2(root, root); // root为根节点，当前链的顶部初始化为根节点

5. 转换欧拉序用ST表求RMQ

实现思路

这种方法将LCA问题转化为范围最小值查询（Range Minimum Query, RMQ）问题。

1. 欧拉序：对树进行DFS遍历，每次进入一个节点和离开一个节点都将其记录下来，形成一个序列。这个序列就是欧拉序（或称为访问序列）。在欧拉序中，两个节点 u 和 v 的LCA是它们在欧拉序中第一次出现位置之间所有节点中深度最小的那个节点。
   • 例如，对于树 $1-2$, $1-3$, $2-4$, $2-5$，欧拉序可以是：$1, 2, 4, 2, 5, 2, 1, 3, 1$
   • 记录每个节点在欧拉序中第一次出现的位置 first[u]。
2. LCA转RMQ：LCA(u, v) 实际上就是欧拉序中从 first[u] 到 first[v]（假设 first[u] < first[v]）这一段子序列中，深度最小的那个节点。
3. ST表求RMQ：使用ST表（Sparse Table） 来高效地进行RMQ查询。ST表可以在 $O(N \\log N)$ 预处理后，以 $O(1)$ 的时间复杂度进行查询。
   • ST表 st[i][j] 存储从位置 i 开始的 $2^j$ 个元素中的最小值。
   • 查询 [L, R] 区间的最小值时，可以分解成两个长度为 $2^k$ 的区间（其中 $k = \log_2(R-L+1)$），然后取这两个区间的最小值。

核心代码示例

const int MAXN = 100005;
const int LOG_MAXN = 17;

vector<int> adj[MAXN];
int euler_tour[MAXN * 2]; // 欧拉序，最大长度为 2*N-1
int depth[MAXN];
int first_occurrence[MAXN]; // 节点第一次出现在欧拉序中的位置
int euler_timer;

// RMQ的ST表
int st_val[MAXN * 2][LOG_MAXN]; // 存储欧拉序中对应节点的深度
int st_idx[MAXN * 2][LOG_MAXN]; // 存储欧拉序中对应深度的节点索引

void dfs_euler(int u, int p, int d) {
    euler_tour[++euler_timer] = u;
    depth[u] = d;
    if (first_occurrence[u] == 0) { // 记录第一次出现的位置
        first_occurrence[u] = euler_timer;
    }

    for (int v : adj[u]) {
        if (v == p) continue;
        dfs_euler(v, u, d + 1);
        euler_tour[++euler_timer] = u; // 回溯时再次记录父节点
    }
}

// 辅助函数，比较两个节点深度，返回深度较小的那个
int get_min_depth_node(int u_idx, int v_idx) {
    if (depth[euler_tour[u_idx]] < depth[euler_tour[v_idx]]) {
        return u_idx;
    }
    return v_idx;
}

void build_st_table() {
    for (int i = 1; i <= euler_timer; ++i) {
        st_val[i][0] = depth[euler_tour[i]];
        st_idx[i][0] = i;
    }
    for (int j = 1; (1 << j) <= euler_timer; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= euler_timer; ++i) {
            int idx1 = st_idx[i][j - 1];
            int idx2 = st_idx[i + (1 << (j - 1))][j - 1];
            st_idx[i][j] = get_min_depth_node(idx1, idx2);
        }
    }
}

int query_rmq(int L, int R) { // 查询欧拉序 [L, R] 范围内的最小深度节点索引
    int k = log2(R - L + 1);
    int idx1 = st_idx[L][k];
    int idx2 = st_idx[R - (1 << k) + 1][k];
    return euler_tour[get_min_depth_node(idx1, idx2)];
}

int get_lca_euler_rmq(int u, int v) {
    int pos_u = first_occurrence[u];
    int pos_v = first_occurrence[v];
    if (pos_u > pos_v) {
        swap(pos_u, pos_v);
    }
    return query_rmq(pos_u, pos_v);
}

// 在主函数中调用：
// euler_timer = 0; // 重置计时器
// dfs_euler(root, 0, 0); // root为根节点，0为虚拟父节点，0为根节点深度
// build_st_table();

6. DFS序求LCA (欧拉序的变种)

实现思路

这种方法是欧拉序求LCA的一种优化或变种，它利用DFS序的特性结合ST表实现RMQ。与完整的欧拉序不同，这里通常指的是记录每个节点第一次被访问时的DFS序，并利用这个DFS序以及节点的深度信息来构建ST表。

参考代码中：

1. dfn[id] = ++dn：dfn[id] 记录了节点 id 的DFS序（即第一次访问时的顺序）。dn 是一个计数器，表示当前DFS序的值。
2. mi[0][dfn[id]] = f：mi[0][i] 存储的是DFS序为 i 的节点（即 rnk[i]）的父节点。注意，这里存储的是父节点，而不是深度。
3. get(x, y)：这个函数根据 dfn[x] 和 dfn[y] 的大小，返回DFS序更小的那个节点（即在DFS序中靠前的节点）。
4. lca(u, v)：
   • 首先，确保 u 的DFS序小于 v 的DFS序，方便处理区间。
   • 然后，利用ST表在 [dfn[u], dfn[v]] 这个DFS序区间内查找“深度最小的那个节点的父节点”。
   • 具体的ST表构建是 mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)])。这里的 get 函数不再是比较深度，而是比较DFS序。它返回的是在DFS序区间 [j, j + (1 << i) - 1] 中，其父节点在原始树中深度最小的那个节点的父节点。
   • 这实际上是利用了这样一个性质：如果 u 和 v 的LCA是 p，那么在它们的DFS序区间 [dfn[u], dfn[v]] 内，p 一定是某个节点的祖先，并且它的深度最小。这里的 mi 数组通过 get 函数间接保存了这些深度信息，但其存储的是节点的父节点。

这种方法的核心在于ST表存储的不是深度，而是节点。get 函数通过比较DFS序来间接处理区间，最终通过ST表的查询找到一个节点，其DFS序在 u 和 v 之间，并且它的父节点就是LCA。

核心代码示例

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e5 + 5;
int n, m, R, dn, dfn[N], mi[19][N]; // dfn[i] 存储节点i的dfs序，mi[k][j] 存储dfs序为j的节点向上跳2^k步的父节点
vector<int> e[N];

// 比较两个节点的dfs序，返回dfs序更小的那个节点
int get(int x, int y) {
  return dfn[x] < dfn[y] ? x : y;
}

// 深度优先搜索，构建dfn数组和mi[0]数组
void dfs(int id, int f) {
  mi[0][dfn[id] = ++dn] = f; // 记录节点的dfs序，并将其父节点存储在mi[0][dfn[id]]中
  for(int it : e[id]) {
    if(it != f) {
      dfs(it, id); 
    }
  }
}

// LCA查询
int lca(int u, int v) {
  if(u == v) return u; // 如果是同一个节点，LCA就是它自己
  
  // 确保 u 的dfs序小于 v 的dfs序，方便处理区间
  if((u = dfn[u]) > (v = dfn[v])) swap(u, v); 
  
  // 计算区间长度的log2值，用于ST表查询
  int d = __lg(v - u++); // u++ 是因为区间是 [u, v]，如果u从1开始，v-u+1是长度。这里v-u是长度-1，所以u要自增
  
  // 在dfs序区间 [u, v] 中，查询mi数组，找到对应LCA
  // mi[d][u] 代表从dfs序为u的节点向上跳2^d步的父节点
  // mi[d][v - (1 << d) + 1] 代表从dfs序为 v-(1<<d)+1 的节点向上跳2^d步的父节点
  // get函数在这里是比较这两个父节点的dfs序，返回dfs序较小的那个（即在原树中深度较大的那个）
  // 最终返回的节点就是LCA
  return get(mi[d][u], mi[d][v - (1 << d) + 1]);
}

int main() {
  scanf("%d %d %d", &n, &m, &R);
  for(int i = 2, u, v; i <= n; i++) {
    scanf("%d %d", &u, "%d", &v);
    e[u].push_back(v);
    e[v].push_back(u);
  }
  dfs(R, 0); // 从根节点R开始DFS，0为虚拟父节点
  
  // 构建ST表
  for(int i = 1; i <= __lg(n); i++) { // i 表示2^i步
    for(int j = 1; j + (1 << i) - 1 <= n; j++) { // j 表示起始dfs序
      // mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)]);
      // 这里的get是比较两个节点的dfs序，返回dfs序更小的那个。
      // 这意味着mi[i][j]存储的是在dfs序区间 [j, j + (1<<i)-1] 中，其父节点在原始树中深度最小的那个节点的父节点。
      // 这个mi数组实际上是在ST表中存储的父节点信息，用于间接查找LCA。
      mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << (i - 1))]);
    }
  }
  for(int i = 1, u, v; i <= m; i++) {
    scanf("%d %d", &u, &v);
    printf("%d\n", lca(u, v));
  }
  return 0;
}

每种LCA算法都有其独特的优缺点，在选择时需要根据实际应用场景进行权衡。以下是从不同维度对这六种方法进行的对比：

六种算法的区别

1. 朴素算法

• 编码难度：非常简单。核心逻辑就是循环向上跳，易于理解和实现。
• 预处理复杂度：O(N)，需要一次DFS来计算每个节点的深度和父节点。
• 每次查询复杂度：O(H)，其中 H 是树的高度。在最坏情况下（链式结构），查询复杂度可能达到 O(N)。
• 空间复杂度：O(N)，存储父节点和深度信息。
• 时间复杂度的常数因子：非常小，因为操作简单，没有复杂的数据结构。

2. 倍增法

• 编码难度：中等。需要理解倍增思想，构建 2k 级祖先表。
• 预处理复杂度：O(NlogN)。需要一次DFS来计算深度和父节点，然后填充 up[N][logN] 表。
• 每次查询复杂度：O(logN)。通过倍增跳跃，每次查询都只需要对 logN 个祖先进行检查。
• 空间复杂度：O(NlogN)，存储倍增祖先表。
• 时间复杂度的常数因子：中等，涉及位运算和数组查找。

3. Tarjan 算法 (离线算法)

• 编码难度：较高。需要对并查集和DFS有深入理解，并且要处理好离线查询的存储和处理逻辑。
• 预处理复杂度：O(N+Q)，其中 Q 是查询的数量。它在一次DFS遍历中同时处理所有查询。并查集的路径压缩和按秩合并可以达到接近线性的时间复杂度。
• 每次查询复杂度：由于是离线算法，没有“每次查询”的概念，所有查询一起处理。可以看作均摊 O(1)。
• 空间复杂度：O(N+Q)，存储树结构、并查集以及所有查询。
• 时间复杂度的常数因子：中等，涉及并查集操作和DFS栈开销。

4. 树链剖分

• 编码难度：很高。涉及两次DFS、重链轻链概念、DFS序、链顶等多个复杂概念，实现细节较多。
• 预处理复杂度：O(N)。两次DFS遍历树，构建相关辅助数组。
• 每次查询复杂度：O(logN)。每次向上跳跃都可能跳过一条重链，直到LCA，重链数量最多为 logN 条。
• 空间复杂度：O(N)，存储各种辅助数组（如深度、父节点、子树大小、重子节点、DFS序、链顶等）。
• 时间复杂度的常数因子：较大，由于涉及较多的数组访问和条件判断。

5. 转换欧拉序用ST表求RMQ

• 编码难度：较高。需要构建欧拉序，并实现ST表进行RMQ查询。ST表的构建和查询逻辑相对复杂。
• 预处理复杂度：O(NlogN)。DFS生成欧拉序是 O(N)，ST表的构建是 O(MlogM)，其中 M 是欧拉序的长度（M≈2N）。
• 每次查询复杂度：O(1)。ST表查询是常数时间。
• 空间复杂度：O(NlogN)，存储欧拉序和ST表。
• 时间复杂度的常数因子：中等，ST表的查询是位运算和数组查找。

6. DFS序求LCA (欧拉序的变种）

• 编码难度：中等偏高。虽然核心代码相对简洁，但其内部原理（特别是 get 函数和 mi 数组的含义）需要仔细理解。它利用了DFS序的连续性以及ST表对区间最小值的快速查询能力。
• 预处理复杂度：O(NlogN)。一次DFS生成DFS序和 mi[0] 数组是 O(N)，ST表的构建是 O(NlogN)。
• 每次查询复杂度：O(1)。ST表查询是常数时间。
• 空间复杂度：O(NlogN)，存储 dfn 数组和 mi 数组（ST表）。
• 时间复杂度的常数因子：中等，与欧拉序+ST表类似，但因为数据结构略有不同，常数可能略有差异。

---

总结

方法	编码难度	预处理复杂度	每次查询复杂度	空间复杂度
朴素算法	非常简单	$O(N)$	$O(H)$	$O(N)$
倍增法	中等	$O(NlogN)$	$O(logN)$	$O(NlogN)$
Tarjan 算法	较高	$O(N+Q)$	均摊 $O(1)$	$O(N+Q)$
树链剖分	很高	$O(N)$	$O(logN)$	$O(N)$
欧拉序+ST表	较高	$O(NlogN)$	$O(1)$	$O(NlogN)$
DFS序+ST表	中等偏高	$O(NlogN)$	$O(1)$	$O(NlogN)$

选择建议：

• 对时间要求不高，追求实现简单：选择朴素算法。
• 需要在线查询，且数据规模适中（N 在 105 级别）：倍增法是经典且常用的选择，其平衡性较好。
• 需要处理大量离线查询：Tarjan算法是最佳选择，其总时间复杂度最优。
• 除了LCA，还需要进行树上路径的查询或修改操作：树链剖分虽然编码复杂，但功能强大，可以解决更多问题。
• 追求极致的在线查询速度（O(1)）：欧拉序/DFS序结合ST表是最佳选择，但预处理和编码复杂度相对较高。DFS序的变种在特定实现下可能更为简洁。