跳转至

最近公共祖先 (Lowest Common Ancestor / LCA)

在有根树中，两个节点 \(u\) 和 \(v\) 的最近公共祖先（LCA）是离根节点最远且同时是 \(u\) 和 \(v\) 的祖先节点。常用于求树上两点距离、树上路径修改与查询等。

树上倍增法 (Binary Lifting)

倍增法实现在线查询，预处理时间复杂度 \(\mathcal{O}(n \log n)\)，单次查询时间复杂度 \(\mathcal{O}(\log n)\)。

#include <vector>
#include <algorithm>
#include <cmath>

struct TreeLCA {
    int n;
    int root;
    int max_log;
    std::vector<int> depth;
    std::vector<std::vector<int>> up; // up[k][u] 表示 u 向上走 2^k 步的祖先

    TreeLCA(int n, int root, const std::vector<std::vector<int>> &adj) 
        : n(n), root(root), depth(n + 1, 0) {
        max_log = std::__lg(n) + 2;
        up.assign(max_log, std::vector<int>(n + 1, 0));

        dfs(root, 0, adj);

        for (int k = 1; k < max_log; ++k) {
            for (int u = 1; u <= n; ++u) {
                up[k][u] = up[k - 1][up[k - 1][u]];
            }
        }
    }

    void dfs(int u, int p, const std::vector<std::vector<int>> &adj) {
        depth[u] = depth[p] + 1;
        up[0][u] = p;
        for (int v : adj[u]) {
            if (v != p) {
                dfs(v, u, adj);
            }
        }
    }

    // 查询 u 与 v 的 LCA
    int query(int u, int v) const {
        if (depth[u] < depth[v]) std::swap(u, v);

        // 1. 将 u 跳跃到与 v 相同深度
        int diff = depth[u] - depth[v];
        for (int k = max_log - 1; k >= 0; --k) {
            if ((diff >> k) & 1) {
                u = up[k][u];
            }
        }

        if (u == v) return u;

        // 2. 同时向上倍增跳跃
        for (int k = max_log - 1; k >= 0; --k) {
            if (up[k][u] != up[k][v]) {
                u = up[k][u];
                v = up[k][v];
            }
        }

        return up[0][u];
    }

    // 树上两点之间的边数距离
    int dist(int u, int v) const {
        return depth[u] + depth[v] - 2 * depth[query(u, v)];
    }
};

经典应用

  1. 树上路径点权/边权和：利用树上前缀和 \(S[u]\)，两点 \(u, v\) 之间的路径和可表示为 \(S[u] + S[v] - S[\text{lca}] - S[\text{parent}[\text{lca}]]\)。

  2. 树上差分：

    • 点差分：在路径 \(u \to v\) 上所有点权加 \(1\)，只需对差分数组操作：diff[u]++, diff[v]++, diff[lca]--, diff[parent[lca]]--。
    • 边差分：在路径 \(u \to v\) 上所有边权加 \(1\)，操作为：diff[u]++, diff[v]++, diff[lca] -= 2。

[!TIP] 进阶演进：如果需要支持树上动态点权/边权的区间修改与区间求和/最值查询，或者需要常数更小的 LCA 算法，推荐使用 树链剖分 (HLD) 配合线段树。通过将树上路径映射为至多 \(\mathcal{O}(\log N)\) 段连续 DFS 序区间，可在 \(\mathcal{O}(\log^2 N)\) 内高效完成动态路径操作。

LeetCode 经典真题精选与题解提示