深入理解树链剖分（Python实现详解：从零开始掌握树链剖分算法）

为什么需要树链剖分？

假设我们要频繁查询树上两点之间的路径最大值、路径和，或修改某点权值，朴素做法每次都要遍历整条路径，时间复杂度 O(n)，效率极低。而通过Python树链剖分 + 线段树，可以将单次操作优化到 O(log²n)。

Python 实现步骤详解

第一步：构建树并进行第一次 DFS

我们需要记录每个节点的父节点、深度、子树大小、重儿子。

import syssys.setrecursionlimit(10**6)class TreeHLD:    def __init__(self, n):        self.n = n        self.graph = [[] for _ in range(n)]        self.parent = [-1] * n        self.depth = [0] * n        self.size = [0] * n        self.heavy = [-1] * n  # 重儿子    def add_edge(self, u, v):        self.graph[u].append(v)        self.graph[v].append(u)    def dfs1(self, u, p):        self.parent[u] = p        self.size[u] = 1        max_size = 0        for v in self.graph[u]:            if v == p:                continue            self.depth[v] = self.depth[u] + 1            self.dfs1(v, u)            self.size[u] += self.size[v]            if self.size[v] > max_size:                max_size = self.size[v]                self.heavy[u] = v

第二步：第二次 DFS 构建重链与 DFS 序

我们将为每个节点分配一个在线性数组中的位置（dfn），并记录每条重链的顶端节点（top）。

    def dfs2(self, u, top):        self.top[u] = top        self.dfn[u] = self.cur_pos        self.pos[self.cur_pos] = u        self.cur_pos += 1        if self.heavy[u] != -1:            self.dfs2(self.heavy[u], top)  # 优先遍历重儿子，保持链连续        for v in self.graph[u]:            if v == self.parent[u] or v == self.heavy[u]:                continue            self.dfs2(v, v)  # 轻儿子新开一条链    def build(self, root=0):        self.top = [0] * self.n        self.dfn = [0] * self.n        self.pos = [0] * self.n        self.cur_pos = 0        self.dfs1(root, -1)        self.dfs2(root, root)

第三步：路径查询（以求路径和为例）

我们不断将两个节点跳到各自链顶，直到它们在同一链上。每次跳转时，利用线段树查询对应区间。

    def query_path(self, seg_tree, u, v):        res = 0        while self.top[u] != self.top[v]:            if self.depth[self.top[u]] < self.depth[self.top[v]]:                u, v = v, u            # u 的链顶更深，跳 u            res += seg_tree.query(self.dfn[self.top[u]], self.dfn[u])            u = self.parent[self.top[u]]        # 现在 u 和 v 在同一链上        if self.depth[u] > self.depth[v]:            u, v = v, u        res += seg_tree.query(self.dfn[u], self.dfn[v])        return res

注意：上述代码依赖一个支持区间查询的 seg_tree（线段树）。你可以自行实现一个标准线段树来配合使用。

完整使用示例

# 假设我们有一棵 5 个节点的树n = 5tree = TreeHLD(n)edges = [(0,1), (0,2), (1,3), (1,4)]for u, v in edges:    tree.add_edge(u, v)tree.build(root=0)# 初始化节点权值vals = [1, 2, 3, 4, 5]# 构建线段树（此处省略线段树实现）# seg_tree = SegmentTree(vals, tree.dfn)# 查询节点 3 到 4 的路径和# result = tree.query_path(seg_tree, 3, 4)# print(result)  # 输出应为 2+4+5=11（路径 3-1-4）

总结

通过本教程，你已经掌握了树链剖分算法的基本原理和 Python 实现方法。虽然代码看起来有点长，但只要理解两次 DFS 的作用——第一次找重儿子，第二次拉链成线——就能轻松驾驭这一强大工具。

无论你是准备算法竞赛，还是研究Python图论算法，树链剖分都是值得深入学习的内容。希望这篇树链剖分教程能为你打下坚实基础！

关键词回顾：Python树链剖分、树链剖分算法、Python图论算法、树链剖分教程。