最近公共祖先（LCA）¶

概述¶

最近公共祖先（Lowest Common Ancestor，LCA）是树结构中的重要概念。对于树中的两个节点 u 和 v，它们的 LCA 是同时拥有 u 和 v 作为后代的最深节点。

核心应用：树上距离计算、路径查询、树上差分、虚树构建等问题的基石。

LCA 定义与性质¶

定义¶

设 root 为树的根节点，对于节点 u 和 v：

公共祖先：节点 w 满足 w 是 u 的祖先且 w 是 v 的祖先
最近公共祖先：所有公共祖先中深度最大的那个

数学表示¶

LCA(u, v) = argmax{ depth[w] | w 是 u 和 v 的公共祖先 }

性质¶

性质	描述
自反性	LCA(u, u) = u
对称性	LCA(u, v) = LCA(v, u)
祗辈关系	若 u 是 v 的祖先，则 LCA(u, v) = u
路径关系	LCA(u, v) 在 u 到 v 的唯一路径上
深度公式	dist(u, v) = depth[u] + depth[v] - 2 × depth[LCA(u, v)]

LCA 可视化¶

graph TB
    root(("root"))
    a(("A"))
    b(("B"))
    c(("C"))
    d(("D"))
    e(("E"))
    f(("F"))
    g(("G"))
    
    root --> a
    root --> b
    a --> c
    a --> d
    b --> e
    d --> f
    d --> g
    
    style root fill:#4CAF50,color:#fff
    style a fill:#FF9800,color:#fff
    style f fill:#2196F3,color:#fff
    style g fill:#2196F3,color:#fff

示例说明

LCA(F, G) = D — F 和 G 的父节点

LCA(F, C) = A — F 的祖先路径: F→D→A→root, C 的祖先路径: C→A→root, 最近的交点是 A

LCA(F, E) = root — F 和 E 分别在左右子树，LCA 是根

LCA(D, F) = D — D 是 F 的祖先

方法一：暴力法¶

思想¶

先让深度大的节点向上跳到同一深度，然后两个节点同时向上跳直到相遇。

实现¶

C
int parent[MAXN];
int depth[MAXN];

int lcaNaive(int u, int v) {
    // 将 u 调整到更深的节点
    while (depth[u] > depth[v]) u = parent[u];
    while (depth[v] > depth[u]) v = parent[v];
    
    // 同时向上跳直到相遇
    while (u != v) {
        u = parent[u];
        v = parent[v];
    }
    return u;
}

时间复杂度¶

操作	复杂度	说明
预处理	O(n)	一遍 DFS 求深度和父节点
查询	O(n)	最坏情况跳 n 次

方法二：倍增法（Binary Lifting）¶

思想¶

预处理每个节点向上跳 2^j 步到达的祖先，查询时利用二进制分解快速上跳。

原理图解¶

graph TB
    subgraph 倍增思想
        A["节点 u"]
        B["parent[u][0] = 向上跳 1 步"]
        C["parent[u][1] = 向上跳 2 步"]
        D["parent[u][2] = 向上跳 4 步"]
        E["parent[u][j] = 向上跳 2^j 步"]
        
        A --> B --> C --> D --> E
    end
    
    style A fill:#E3F2FD
    style E fill:#E8F5E9

递推关系：

parent[u][j] = parent[parent[u][j-1]][j-1]

解释: 从 u 跳 2^j 步 = 从 u 跳 2^(j-1) 步，再跳 2^(j-1) 步

可视化示例¶

树结构与倍增数组

节点 7 的倍增数组

parent[7][0] = 4 (跳 1 步)
parent[7][1] = 1 (跳 2 步: 7→4→1)
parent[7][2] = -1 (跳 4 步: 超出根节点)

节点 6 的倍增数组

parent[6][0] = 2 (跳 1 步)
parent[6][1] = 1 (跳 2 步: 6→2→1)
parent[6][2] = -1 (跳 4 步: 超出根节点)

预处理¶

C
int parent[MAXN][20];  // parent[u][j] = u 向上跳 2^j 步的祖先
int depth[MAXN];
int maxLog;

void dfs(int u, int p, int d, int *adj[], int n) {
    parent[u][0] = p;
    depth[u] = d;
    
    for (int i = 0; i < n; i++) {
        if (adj[u][i] && i != p) {
            dfs(i, u, d + 1, adj, n);
        }
    }
}

void preprocess(int n, int root, int *adj[]) {
    dfs(root, -1, 0, adj, n);
    
    maxLog = 0;
    while ((1 << maxLog) <= n) maxLog++;
    
    // 递推计算倍增数组
    for (int j = 1; j < maxLog; j++) {
        for (int i = 0; i < n; i++) {
            if (parent[i][j - 1] != -1) {
                parent[i][j] = parent[parent[i][j - 1]][j - 1];
            } else {
                parent[i][j] = -1;
            }
        }
    }
}

查询 LCA¶

C
int lcaBinaryLifting(int u, int v) {
    // 确保 u 是更深的节点
    if (depth[u] < depth[v]) {
        int temp = u; u = v; v = temp;
    }
    
    // 将 u 向上跳到与 v 同一深度
    int diff = depth[u] - depth[v];
    for (int j = 0; j < maxLog; j++) {
        if ((diff >> j) & 1) {
            u = parent[u][j];
        }
    }
    
    // 如果 u == v，则 v 就是 LCA
    if (u == v) return u;
    
    // 同时向上跳，找到 LCA
    for (int j = maxLog - 1; j >= 0; j--) {
        if (parent[u][j] != parent[v][j]) {
            u = parent[u][j];
            v = parent[v][j];
        }
    }
    
    return parent[u][0];
}

查询过程示例¶

求 LCA(6, 7)

depth[6] = 2, depth[7] = 2

步骤1

深度相同，跳过调整

步骤2

同时向上跳

j=2: parent[6][2] = -1, parent[7][2] = -1, 相等，不跳
j=1: parent[6][1] = 1, parent[7][1] = 1, 相等，不跳
j=0: parent[6][0] = 2, parent[7][0] = 4, 不相等 → u = 2, v = 4

步骤3

返回 parent[2][0] = 1

结果: LCA(6, 7) = 1

flowchart TD
    A["LCA 6, 7"]
    B["depth 6 = depth 7 = 2"]
    C["同时向上跳"]
    D["j=0: parent 6,0 = 2, parent 7,0 = 4"]
    E["不相等, u=2, v=4"]
    F["返回 parent 2,0 = 1"]
    
    A --> B --> C --> D --> E --> F
    
    style A fill:#E3F2FD
    style F fill:#E8F5E9

时间复杂度¶

操作	复杂度	说明
预处理	O(n log n)	每个节点 log n 个祖先
查询	O(log n)	最多跳 log n 次

方法三：Tarjan 离线算法¶

思想¶

利用并查集和 DFS，在遍历树的同时回答所有查询。对于节点 u，当访问其子树 v 后，将 v 合并到 u，然后回答 u 与其他已访问节点的 LCA 查询。

原理图解¶

flowchart TD
    A["DFS 访问节点 u"]
    B["标记 u 为已访问"]
    C["对于每个查询 u, v"]
    D["如果 v 已访问"]
    E["LCA u, v = Find v"]
    F["继续 DFS 子树"]
    G["回溯时合并到父节点"]
    
    A --> F --> G --> B --> C --> D --> E
    
    style A fill:#E3F2FD
    style E fill:#E8F5E9

核心思想¶

DFS 过程中的关键观察

当 DFS 完成子树 v 的遍历后，v 及其所有后代都会被合并到 v 的父节点。此时，对于已访问的节点 w，Find(w) 就是 v 和 w 的 LCA。

实现¶

C
#include <string.h>

int parentSet[MAXN];     // 并查集父节点
int visited[MAXN];       // 访问标记
int ancestor[MAXN];      // 当前集合的祖先

typedef struct Query {
    int v;
    int index;
    struct Query *next;
} Query;

Query *queries[MAXN];    // 查询链表
int lcaResult[MAXN];     // LCA 结果

int findSet(int x) {
    if (parentSet[x] != x) {
        parentSet[x] = findSet(parentSet[x]);
    }
    return parentSet[x];
}

void unionSet(int x, int y) {
    parentSet[findSet(x)] = findSet(y);
}

void tarjan(int u, int *adj[], int n) {
    parentSet[u] = u;
    ancestor[u] = u;
    
    // 遍历子树
    for (int v = 0; v < n; v++) {
        if (adj[u][v] && !visited[v]) {
            tarjan(v, adj, n);
            unionSet(v, u);
            ancestor[findSet(u)] = u;
        }
    }
    
    visited[u] = 1;
    
    // 回答查询
    Query *q = queries[u];
    while (q != NULL) {
        if (visited[q->v]) {
            lcaResult[q->index] = ancestor[findSet(q->v)];
        }
        q = q->next;
    }
}

执行过程示例¶

Tarjan 算法执行过程

查询: LCA(4, 5), LCA(4, 3)

1. DFS 到 4，visited[4] = 1，无查询可回答

2. 回溯到 2，合并 4 到 2，ancestor[2] = 2

3. DFS 到 5，visited[5] = 1，查询 LCA(4, 5): visited[4] = 1 → 结果 = 2

4. 回溯到 2，合并 5 到 2

5. 回溯到 1，合并 2 到 1，ancestor[1] = 1

6. DFS 到 3，visited[3] = 1，查询 LCA(4, 3): visited[4] = 1 → 结果 = 1

时间复杂度¶

操作	复杂度	说明
预处理	O(n)	建邻接表
查询	O(1) 摊还	离线处理所有查询
空间	O(n + q)	并查集 + 查询存储

注意：Tarjan 算法是离线算法，需要预先知道所有查询。如果查询在线到来，无法使用此方法。

方法四：欧拉序 + RMQ¶

思想¶

将树转换为欧拉序列，LCA 问题转化为 RMQ（区间最值查询）问题。

欧拉序¶

DFS 遍历时，每次访问节点（进入和离开）都记录：

欧拉序 (记录进入和回溯)

访问 1 → 访问 2 → 访问 4 → 回溯 4 → 回溯 2 → 访问 3 → 回溯 3 → 回溯 1

欧拉序列: [1, 2, 4, 2, 1, 3, 1]

深度序列: [0, 1, 2, 1, 0, 1, 0]

首次出现: first[1]=0, first[2]=1, first[3]=5, first[4]=2

关键性质¶

定理：LCA(u, v) 等于欧拉序中从 first[u] 到 first[v] 区间内深度最小的节点。

可视化¶

graph LR
    subgraph 欧拉序列
        n1["1<br/>d=0"] --> n2["2<br/>d=1"] --> n3["4<br/>d=2"] --> n4["2<br/>d=1"] --> n5["1<br/>d=0"] --> n6["3<br/>d=1"] --> n7["1<br/>d=0"]
    end
    
    style n1 fill:#4CAF50,color:#fff
    style n2 fill:#2196F3,color:#fff
    style n3 fill:#FF9800,color:#fff
    style n5 fill:#4CAF50,color:#fff
    style n6 fill:#9C27B0,color:#fff

求 LCA(4, 3)

first[4] = 2, first[3] = 5

区间 [2, 5] 对应: [4, 2, 1, 3]

深度: [2, 1, 0, 1]

深度最小的节点是 1

结果: LCA(4, 3) = 1

实现¶

C
int euler[2 * MAXN];        // 欧拉序列
int depthEuler[2 * MAXN];   // 欧拉序列对应的深度
int firstOccur[MAXN];       // 每个节点首次出现的位置
int eulerCnt;
int st[2 * MAXN][20];       // Sparse Table

void dfsEuler(int u, int p, int d, int *adj[], int n) {
    firstOccur[u] = eulerCnt;
    euler[eulerCnt] = u;
    depthEuler[eulerCnt] = d;
    eulerCnt++;
    
    for (int v = 0; v < n; v++) {
        if (adj[u][v] && v != p) {
            dfsEuler(v, u, d + 1, adj, n);
            euler[eulerCnt] = u;          // 回溯时记录
            depthEuler[eulerCnt] = d;
            eulerCnt++;
        }
    }
}

void buildRMQ(int n) {
    // 初始化
    for (int i = 0; i < eulerCnt; i++) {
        st[i][0] = i;
    }
    
    // 构建 Sparse Table
    for (int j = 1; (1 << j) <= eulerCnt; j++) {
        for (int i = 0; i + (1 << j) <= eulerCnt; i++) {
            int a = st[i][j - 1];
            int b = st[i + (1 << (j - 1))][j - 1];
            st[i][j] = (depthEuler[a] < depthEuler[b]) ? a : b;
        }
    }
}

int lcaRMQ(int u, int v) {
    int l = firstOccur[u];
    int r = firstOccur[v];
    if (l > r) { int temp = l; l = r; r = temp; }
    
    // RMQ 查询
    int k = 0;
    while ((1 << (k + 1)) <= r - l + 1) k++;
    
    int a = st[l][k];
    int b = st[r - (1 << k) + 1][k];
    
    return euler[(depthEuler[a] < depthEuler[b]) ? a : b];
}

时间复杂度¶

操作	复杂度	说明
预处理	O(n)	欧拉序 + Sparse Table
查询	O(1)	RMQ 查询
空间	O(n log n)	Sparse Table

方法五：树链剖分¶

利用重链剖分求 LCA（详见 020-树链剖分）：

C
int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) {
            int temp = u; u = v; v = temp;
        }
        u = parent[top[u]];
    }
    return (depth[u] < depth[v]) ? u : v;
}

时间复杂度：预处理 O(n)，查询 O(log n)。

C++ 完整实现¶

C++
#include <vector>
#include <algorithm>

class LCA {
private:
    std::vector<std::vector<int>> adj;
    std::vector<std::vector<int>> parent;
    std::vector<int> depth;
    int n, maxLog;
    
    void dfs(int u, int p, int d) {
        parent[u][0] = p;
        depth[u] = d;
        
        for (int v : adj[u]) {
            if (v != p) {
                dfs(v, u, d + 1);
            }
        }
    }
    
public:
    LCA(int n) : n(n), adj(n + 1), depth(n + 1) {
        maxLog = 0;
        while ((1 << maxLog) <= n) maxLog++;
        parent.assign(n + 1, std::vector<int>(maxLog, -1));
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    void build(int root) {
        dfs(root, -1, 0);
        
        for (int j = 1; j < maxLog; j++) {
            for (int i = 1; i <= n; i++) {
                if (parent[i][j - 1] != -1) {
                    parent[i][j] = parent[parent[i][j - 1]][j - 1];
                }
            }
        }
    }
    
    int lca(int u, int v) {
        if (depth[u] < depth[v]) std::swap(u, v);
        
        int diff = depth[u] - depth[v];
        for (int j = 0; j < maxLog; j++) {
            if ((diff >> j) & 1) {
                u = parent[u][j];
            }
        }
        
        if (u == v) return u;
        
        for (int j = maxLog - 1; j >= 0; j--) {
            if (parent[u][j] != parent[v][j]) {
                u = parent[u][j];
                v = parent[v][j];
            }
        }
        
        return parent[u][0];
    }
    
    int dist(int u, int v) {
        return depth[u] + depth[v] - 2 * depth[lca(u, v)];
    }
    
    // 判断 a 是否在 u 到 v 的路径上
    bool onPath(int a, int u, int v) {
        int l = lca(u, v);
        return lca(a, u) == a && lca(a, v) == l;
    }
    
    // 求 u 到 v 路径上的第 k 个节点
    int kthNode(int u, int v, int k) {
        int l = lca(u, v);
        int d1 = depth[u] - depth[l];
        
        if (k <= d1) {
            // 在 u 到 l 的路径上
            for (int j = 0; j < maxLog; j++) {
                if ((k >> j) & 1) {
                    u = parent[u][j];
                }
            }
            return u;
        } else {
            // 在 l 到 v 的路径上
            int d2 = depth[v] - depth[l];
            k = d1 + d2 - k;
            for (int j = 0; j < maxLog; j++) {
                if ((k >> j) & 1) {
                    v = parent[v][j];
                }
            }
            return v;
        }
    }
};

算法对比¶

graph TB
    subgraph 算法选择
        A[需要 LCA]
        B{查询类型?}
        C[倍增法<br/>预处理Onlogn<br/>查询Ologn]
        D[Tarjan<br/>离线O1查询]
        E[欧拉序+RMQ<br/>预处理On<br/>查询O1]
        F[树链剖分<br/>支持更多操作]
    end
    
    A --> B
    B -->|在线查询| C
    B -->|离线批量| D
    B -->|需要O1查询| E
    B -->|需要路径操作| F
    
    style C fill:#4CAF50,color:#fff
    style D fill:#2196F3,color:#fff
    style E fill:#FF9800,color:#fff
    style F fill:#9C27B0,color:#fff

算法	预处理	查询	空间	特点
暴力	O(n)	O(n)	O(n)	实现简单
倍增	O(n log n)	O(log n)	O(n log n)	最常用，支持在线
Tarjan	O(n)	O(1) 摊还	O(n + q)	离线算法
RMQ	O(n log n)	O(1)	O(n log n)	查询最快
树链剖分	O(n)	O(log n)	O(n)	支持路径操作

推荐：大多数情况下使用倍增法，代码简洁、支持在线查询、复杂度合理。如果需要 O(1) 查询，使用欧拉序 + RMQ。如果需要同时支持路径操作，使用树链剖分。

扩展应用¶

1. 树上距离¶

C++
int dist(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}

2. 路径上的第 K 个节点¶

C++
int kthOnPath(int u, int v, int k) {
    int l = lca(u, v);
    int d1 = depth[u] - depth[l];
    if (k <= d1) return jump(u, k);
    return jump(v, depth[v] - depth[l] - (k - d1));
}

3. 虚树构建¶

保留关键点及其两两 LCA，用于树上 DP 优化：

C++
vector<int> buildVirtualTree(vector<int>& keyNodes) {
    vector<int> nodes = keyNodes;
    for (int i = 0; i < keyNodes.size(); i++) {
        for (int j = i + 1; j < keyNodes.size(); j++) {
            nodes.push_back(lca(keyNodes[i], keyNodes[j]));
        }
    }
    sort(nodes.begin(), nodes.end(), [&](int a, int b) {
        return depth[a] > depth[b];
    });
    nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
    return nodes;
}

4. 树上差分¶

路径修改转单点修改：

C++
// 路径 u-v 加 val
void pathDiff(int u, int v, int val) {
    int l = lca(u, v);
    diff[u] += val;
    diff[v] += val;
    diff[l] -= val;
    if (parent[l][0] != -1) diff[parent[l][0]] -= val;
}

// 最终节点值 = 子树 diff 和

5. 多个节点的 LCA¶

C++
int multiLCA(vector<int>& nodes) {
    int result = nodes[0];
    for (int i = 1; i < nodes.size(); i++) {
        result = lca(result, nodes[i]);
    }
    return result;
}

典型问题示例¶

LeetCode 236. 二叉树的最近公共祖先¶

C++
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    
    if (left && right) return root;
    return left ? left : right;
}

LeetCode 1740. 找到二叉树中的距离¶

C++
int findDistance(TreeNode* root, TreeNode* p, TreeNode* q) {
    TreeNode* l = lowestCommonAncestor(root, p, q);
    return depth(p, l) + depth(q, l);
}

int depth(TreeNode* node, TreeNode* ancestor) {
    int d = 0;
    while (node != ancestor) {
        node = node->parent;
        d++;
    }
    return d;
}

参考资料¶

《算法竞赛入门经典》LCA 章节
Tarjan, R. E. (1979). Applications of Path Compression on Balanced Trees
Bender, M. A., & Farach-Colton, M. (2000). The LCA Problem Revisited