Python树上倍增算法详解（LCA算法与倍增法求最近公共祖先实战教程）

为什么需要树上倍增？

最朴素的方法是让两个节点同时向上跳，直到相遇。但当树很深时（比如 10⁵ 层），每次查询可能需要 O(n) 时间，效率太低。

而树上倍增的核心思想是：预处理每个节点向上跳 2^k 步能到达的位置。这样在查询时，我们可以像二进制一样“跳跃式”上升，将单次查询时间优化到 O(log n)！

算法原理详解

我们定义 up[u][k] 表示节点 u 向上跳 2^k 步后到达的祖先节点。

预处理时，利用动态规划思想：

• up[u][0] = parent[u]（跳 1 步就是直接父节点）
• up[u][k] = up[ up[u][k-1] ][k-1]（跳 2^k 步 = 先跳 2^{k-1} 步，再跳 2^{k-1} 步）

查询 LCA(a, b) 的步骤：

1. 如果 a 和 b 深度不同，先把更深的那个跳到同一深度；
2. 如果此时 a == b，说明其中一个就是另一个的祖先，直接返回；
3. 否则，从最大的 k 开始尝试，只要 up[a][k] != up[b][k]，就同时往上跳；
4. 最后 a 和 b 的父节点就是 LCA。

Python 实现代码

下面是一个完整的、可运行的 Python 示例，包含建树、预处理和 LCA 查询：

import mathfrom collections import defaultdict, deque# 构建邻接表def build_tree(edges):    graph = defaultdict(list)    for u, v in edges:        graph[u].append(v)        graph[v].append(u)  # 无向图    return graph# DFS 预处理深度和父节点def dfs(root, graph, parent, depth):    stack = [(root, -1, 0)]  # (当前节点, 父节点, 深度)    while stack:        u, p, d = stack.pop()        parent[u] = p        depth[u] = d        for v in graph[u]:            if v != p:                stack.append((v, u, d + 1))# 主函数：LCA 类class LCA:    def __init__(self, edges, root=0):        self.graph = build_tree(edges)        self.n = len(set([u for e in edges for u in e]))        self.root = root                # 初始化深度和直接父节点        self.depth = [0] * self.n        self.parent0 = [-1] * self.n        dfs(root, self.graph, self.parent0, self.depth)                # 计算最大倍增层数        self.LOG = math.floor(math.log2(self.n)) + 1                # 初始化 up 表        self.up = [[-1] * self.LOG for _ in range(self.n)]                # 第0层就是直接父节点        for i in range(self.n):            self.up[i][0] = self.parent0[i]                # 动态规划填充 up 表        for j in range(1, self.LOG):            for i in range(self.n):                if self.up[i][j-1] != -1:                    self.up[i][j] = self.up[self.up[i][j-1]][j-1]        def query(self, a, b):        # 确保 a 是更深的节点        if self.depth[a] < self.depth[b]:            a, b = b, a                # 将 a 提升到与 b 同一深度        diff = self.depth[a] - self.depth[b]        bit = 0        while diff:            if diff & 1:                a = self.up[a][bit]                if a == -1:  # 超出根节点                    break            diff >>= 1            bit += 1                if a == b:            return a                # 从高到低尝试跳跃        for j in range(self.LOG - 1, -1, -1):            if self.up[a][j] != self.up[b][j]:                a = self.up[a][j]                b = self.up[b][j]                return self.up[a][0]  # 返回父节点即 LCA# 使用示例if __name__ == "__main__":    # 构建如下树：    #       0    #      / \    #     1   2    #    / \   \    #   3   4   5    edges = [(0,1), (0,2), (1,3), (1,4), (2,5)]    lca_solver = LCA(edges, root=0)        print("LCA of 3 and 4 is:", lca_solver.query(3, 4))  # 输出: 1    print("LCA of 4 and 5 is:", lca_solver.query(4, 5))  # 输出: 0    print("LCA of 3 and 5 is:", lca_solver.query(3, 5))  # 输出: 0

总结

通过本文，你已经掌握了Python树上倍增的基本思想和实现方法。这项技术不仅能用于LCA算法，还可扩展到路径最大值、路径和等更复杂的问题。

记住关键点：

• 预处理 up[u][k] 表，利用倍增思想；
• 查询时先对齐深度，再同步上跳；
• 时间复杂度：预处理 O(n log n)，查询 O(log n)。

现在，你已经具备了使用倍增法求最近公共祖先的能力！快去刷题巩固吧～