每日算法 — 使用java实现LCA：最近公共祖先倍增法与Tarjan离线算法

引言

在树结构中，两个节点的最近公共祖先（Lowest Common Ancestor，简称LCA）是指同时是这两个节点祖先的节点中深度最大的那个。LCA问题是图论与树算法中最基础、最经典的问题之一，广泛应用于网络路由、文件系统路径解析、生物信息学的物种分类树、编译器的语法树分析等众多领域。本文将使用Java实现两种主流LCA算法——在线查询的倍增法和离线查询的Tarjan算法，并展示LCA在树路径查询中的核心作用。

问题定义

给定一棵有根树和若干查询，每个查询要求找出两个节点的最近公共祖先。

示例：在如下树中

LCA(4, 5) = 2
LCA(4, 6) = 1
LCA(2, 3) = 1

算法一：倍增法（在线查询）

倍增法的核心思想是预处理每个节点向上跳2^k步的祖先，这样任意跳跃都可以通过二进制分解在O(log N)步内完成。

预处理

parent[k][u]：节点u向上跳2^k步的祖先
depth[u]：节点u的深度

状态转移：parent[k][u] = parent[k-1][parent[k-1][u]]

查询过程

将较深的节点上跳到与另一节点同深度
若两节点相同，则返回
从大到小枚举k，若parent[k][u] != parent[k][v]，则同时上跳
返回两节点的父节点

算法二：Tarjan离线算法

Tarjan算法利用并查集，在一次DFS中回答所有查询。其核心思想是：当某个节点的子树全部遍历完毕后，将该节点与其父节点在并查集中合并。对于查询(u, v)，若v已经被遍历过，则v所在的并查集集合的代表元就是LCA(u, v)。

时间复杂度：O(N + Q × α(N))，其中α为阿克曼函数反函数。

Java实现

import java.util.*;

/**
 * 图/树的邻接表表示
 */
class Graph {
    int n;
    List<Integer>[] adj;

    @SuppressWarnings("unchecked")
    Graph(int n) {
        this.n = n;
        adj = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) adj[i] = new ArrayList<>();
    }

    void addEdge(int u, int v) {
        adj[u].add(v);
        adj[v].add(u);
    }
}

/**
 * 倍增法LCA
 */
class BinaryLiftingLCA {
    private final int n, logN;
    private final int[][] parent; // parent[k][u]: u向上2^k的祖先
    private final int[] depth;
    private final Graph graph;

    public BinaryLiftingLCA(Graph graph, int root) {
        this.graph = graph;
        this.n = graph.n;
        this.logN = 32 - Integer.numberOfLeadingZeros(n);
        this.parent = new int[logN][n + 1];
        this.depth = new int[n + 1];

        // 初始化
        for (int[] row : parent) Arrays.fill(row, -1);
        Arrays.fill(depth, -1);

        dfs(root, -1, 0);

        // 倍增预处理
        for (int k = 1; k < logN; k++) {
            for (int v = 1; v <= n; v++) {
                if (parent[k - 1][v] != -1) {
                    parent[k][v] = parent[k - 1][parent[k - 1][v]];
                }
            }
        }
    }

    private void dfs(int u, int p, int d) {
        parent[0][u] = p;
        depth[u] = d;
        for (int v : graph.adj[u]) {
            if (v != p) {
                dfs(v, u, d + 1);
            }
        }
    }

    /**
     * 查询u和v的LCA，时间复杂度O(log N)
     */
    public int query(int u, int v) {
        if (depth[u] < depth[v]) {
            int tmp = u; u = v; v = tmp;
        }

        // 将u提升到与v同深度
        int diff = depth[u] - depth[v];
        for (int k = 0; k < logN; k++) {
            if ((diff & (1 << k)) != 0) {
                u = parent[k][u];
            }
        }

        if (u == v) return u;

        // 同时向上跳
        for (int k = logN - 1; k >= 0; k--) {
            if (parent[k][u] != -1 && parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }

        return parent[0][u];
    }

    /**
     * 获取节点u向上跳k步的祖先
     */
    public int kthAncestor(int u, int k) {
        for (int i = 0; i < logN; i++) {
            if ((k & (1 << i)) != 0) {
                u = parent[i][u];
                if (u == -1) return -1;
            }
        }
        return u;
    }

    /**
     * 获取两节点之间的距离（边数）
     */
    public int distance(int u, int v) {
        int lca = query(u, v);
        return depth[u] + depth[v] - 2 * depth[lca];
    }

    /**
     * 获取u到v路径上的第k个节点（从u开始计数）
     */
    public int kthNodeOnPath(int u, int v, int k) {
        int lca = query(u, v);
        int distU = depth[u] - depth[lca];
        int distV = depth[v] - depth[lca];

        if (k <= distU) {
            return kthAncestor(u, k);
        } else {
            return kthAncestor(v, distU + distV - k);
        }
    }
}

/**
 * Tarjan离线LCA算法（基于并查集）
 */
class TarjanLCA {
    private final Graph graph;
    private final int n;
    private final int[] dsuParent;
    private final boolean[] visited;
    private final int[] ancestor;
    private final List<int[]>[] queries; // 每个节点关联的查询
    private final int[] answers;

    public TarjanLCA(Graph graph) {
        this.graph = graph;
        this.n = graph.n;
        this.dsuParent = new int[n + 1];
        this.visited = new boolean[n + 1];
        this.ancestor = new int[n + 1];
        this.queries = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            this.queries[i] = new ArrayList<>();
            this.dsuParent[i] = i;
        }
        this.answers = new int[0];
    }

    /**
     * 添加查询，idx为查询编号
     */
    public void addQuery(int u, int v, int idx) {
        queries[u].add(new int[]{v, idx});
        queries[v].add(new int[]{u, idx});
    }

    /**
     * 执行离线查询，返回所有查询的答案
     */
    public int[] solve(int root, int queryCount) {
        this.answers = new int[queryCount];
        tarjanDFS(root, -1);
        return answers;
    }

    private void tarjanDFS(int u, int p) {
        visited[u] = true;
        ancestor[u] = u;

        for (int v : graph.adj[u]) {
            if (v != p && !visited[v]) {
                tarjanDFS(v, u);
                union(u, v);
                ancestor[find(u)] = u;
            }
        }

        // 回答所有与u相关的查询
        for (int[] q : queries[u]) {
            int v = q[0], idx = q[1];
            if (visited[v]) {
                answers[idx] = ancestor[find(v)];
            }
        }
    }

    private int find(int x) {
        if (dsuParent[x] != x) {
            dsuParent[x] = find(dsuParent[x]);
        }
        return dsuParent[x];
    }

    private void union(int x, int y) {
        int px = find(x), py = find(y);
        if (px != py) dsuParent[px] = py;
    }
}

/**
 * LCA应用：树上路径最值查询（配合线段树或ST表）
 * 思想：u到v的路径 = u到lca的路径 + v到lca的路径
 */
class PathQueryWithLCA {
    private final BinaryLiftingLCA lcaSolver;
    private final int[] nodeValue;
    private final int n;

    public PathQueryWithLCA(Graph graph, int root, int[] nodeValue) {
        this.lcaSolver = new BinaryLiftingLCA(graph, root);
        this.nodeValue = nodeValue;
        this.n = graph.n;
    }

    /**
     * 获取u到v路径上的节点值之和
     * 预处理时存储每个节点到根的前缀和即可O(1)查询
     */
    public int pathSum(int u, int v, int[] prefixSum) {
        int lca = lcaSolver.query(u, v);
        return prefixSum[u] + prefixSum[v] - 2 * prefixSum[lca] + nodeValue[lca];
    }
}

/**
 * 主程序：演示与测试
 */
public class LCADemo {
    public static void main(String[] args) {
        // 构建测试树
        //        1
        //       / \
        //      2   3
        //     / |   \
        //    4  5    6
        //   /
        //  7
        int n = 7;
        Graph graph = new Graph(n);
        int[][] edges = {{1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 6}, {4, 7}};
        for (int[] e : edges) graph.addEdge(e[0], e[1]);

        // 倍增法测试
        System.out.println("=== 倍增法LCA ===");
        BinaryLiftingLCA bl = new BinaryLiftingLCA(graph, 1);

        int[][] testQueries = {{4, 5}, {4, 6}, {2, 3}, {7, 5}, {7, 6}};
        for (int[] q : testQueries) {
            System.out.printf("LCA(%d, %d) = %d, 距离 = %d%n",
                q[0], q[1], bl.query(q[0], q[1]), bl.distance(q[0], q[1]));
        }

        System.out.println("\n7的第2个祖先: " + bl.kthAncestor(7, 2));
        System.out.println("7到6路径上的第3个节点: " + bl.kthNodeOnPath(7, 6, 3));

        // Tarjan离线算法测试
        System.out.println("\n=== Tarjan离线LCA ===");
        TarjanLCA tarjan = new TarjanLCA(graph);
        for (int i = 0; i < testQueries.length; i++) {
            tarjan.addQuery(testQueries[i][0], testQueries[i][1], i);
        }
        int[] tarjanAnswers = tarjan.solve(1, testQueries.length);
        for (int i = 0; i < testQueries.length; i++) {
            System.out.printf("LCA(%d, %d) = %d%n",
                testQueries[i][0], testQueries[i][1], tarjanAnswers[i]);
        }
    }
}

LCA的扩展应用

1. 树上差分

对路径(u, v)上的所有节点值加x，可利用LCA转化为四次单点操作：

cnt[u] += x, cnt[v] += x, cnt[lca] -= x, cnt[parent[lca]] -= x

最后自底向上合并子树计数即可。

2. 树的重心与LCA

树的重心是删除后使得剩余子树最大尺寸最小的节点。结合LCA可以快速判断节点间的从属关系，辅助重心分解。

3. 虚拟树（虚树）

给定一组关键点，构建仅包含这些点及其LCA的最小连通子树。虚树节点数O(K)，K为关键点数，是解决大规模树上路径问题的利器。

复杂度分析

算法	预处理	单次查询	空间复杂度
倍增法	O(N log N)	O(log N)	O(N log N)
Tarjan离线	O(N α(N))	O(1) 均摊	O(N + Q)
RMQ转欧拉序	O(N log N)	O(1)	O(N log N)
树链剖分	O(N)	O(log² N)	O(N)

其中N为节点数，Q为查询数。

工程实践建议

查询模式决定算法：若查询与输入交织（在线），选倍增法；若查询已知（离线），Tarjan更优。
频繁查询时：倍增法的O(log N)单次查询在大多数场景已足够快，且代码清晰易维护。
空间敏感时：Tarjan和树链剖分的空间开销更小。
路径聚合查询：LCA配合前缀和/线段树，可解决路径和、路径最值等进阶问题。

总结

LCA问题是树算法的基石。倍增法以清晰的二进制分解思想和适中的复杂度成为最常用的在线解法；Tarjan离线算法则以并查集的神来之笔，展示了离线处理与并查集结合的强大威力。掌握LCA后，树上路径查询、差分统计、虚拟树构建等高级技巧将迎刃而解。本文提供的Java实现可直接应用于文件系统路径解析、组织架构层级查询、网络路由最短路径等实际工程场景。

Tagged with: Java LCA Tarjan算法倍增法图论并查集最近公共祖先树结构