树上算法：图的特殊骨架

前四篇文章中，我们学会了用 BFS/DFS 遍历图、用 low-link 分析连通结构、用拓扑排序处理 DAG 上的依赖关系。这些工具都作用于”一般的图”——允许环、允许多余的边。但在实践中，有一类图结构出现得极其频繁，而且因为它的特殊性质，许多在一般图上困难或低效的问题在它身上有优雅的高效解法。这就是树（tree）。

文件系统的目录层次是一棵树；HTML/XML 的 DOM 是一棵树；编译器的抽象语法树（AST）是一棵树；生物学中的物种演化关系是一棵树；甚至 BFS 和 DFS 本身产生的遍历结构也是树。树是无处不在的图的特殊骨架——少了一条边就不连通，多了一条边就有环。正是这种”刚好够连通”的极简结构，赋予了树独特的算法优势。

本文是 Part 1”探”的终结篇。我们将建立一套专属于树的算法工具箱：LCA（最近公共祖先）、直径、重心、重链剖分（HLD），以及树与其他图结构（生成树、支配树）的关系。这些工具将在后续的最短路径（Art. 6）、最小生成树（Art. 11）等篇章中反复出现。

算法范式：分治（重心分解）、动态规划（树上 DP）、穷举搜索（DFS/BFS 遍历树）

核心概念：为什么树值得单独研究？

树 $T = (V, E)$ 是一个连通无环图，满足 $|E| = |V| - 1$ 。这三个性质中的任意两个都能推出第三个（CLRS, Chapter B.4）。换一个等价说法：树是任意两个节点之间恰好存在一条路径的图。

这个”任意两点间唯一路径”的性质是树的一切算法优势的根源：

路径唯一：不需要搜索”最短路”——两点之间只有一条路可走
无环：DFS 永远不会遇到回边（back edge），时间戳和子树结构完全清晰
边数最少： $m = n - 1$ ，所有基于边的操作都是 $O(n)$ 级别
层次结构：选定根后，自然产生父子关系、深度、子树大小等丰富信息

一般图上 $O(n + m)$ 的算法，在树上因为 $m = n - 1$ 而自动变成 $O(n)$ 。更重要的是，树的层次结构允许我们用倍增（binary lifting）等技巧实现 $O(\log n)$ 级别的查询——这在一般图上是不可能的。

有根树 vs 无根树

算法中我们通常在有根树（rooted tree）上工作：选定一个节点 $r$ 作为根，所有其他节点按照到 $r$ 的路径自然产生层次关系。对于节点 $v$ ：

父节点 $\text{parent}(v)$ ： $v$ 到根路径上的下一个节点（根没有父节点）
深度 $\text{depth}(v)$ ： $v$ 到根的路径长度（根的深度为 0）
子树 $\text{subtree}(v)$ ：以 $v$ 为根的子树包含的所有节点
子树大小 $\text{size}(v)$ ： $|\text{subtree}(v)|$

这些信息只需一次 DFS 就能全部计算出来（ $O(n)$ ）。无根树的问题（如直径）可以先任意选根转化为有根树问题。

LCA：最近公共祖先

问题定义

给定有根树 $T$ 和两个节点 $u$ , $v$ ，它们的最近公共祖先（Lowest Common Ancestor, LCA） $\text{LCA}(u, v)$ 是 $u$ 和 $v$ 的所有公共祖先中深度最大的那个。等价地， $\text{LCA}(u, v)$ 是从根出发到 $u$ 的路径和到 $v$ 的路径的最后一个交叉点。

LCA 是树上路径查询的基石。 $u$ 到 $v$ 的路径必然经过 $\text{LCA}(u, v)$ ，路径长度为 $\text{depth}(u) + \text{depth}(v) - 2 \cdot \text{depth}(\text{LCA}(u, v))$ 。

朴素方法

最简单的方法：先将 $u$ 和 $v$ 提升到同一深度，然后同步向上走，直到汇合。

NaiveLCA(u, v):
    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)$ （最坏情况，树退化为链）。 $q$ 次查询总计 $O(qn)$ 。当 $q$ 很大时，太慢了。

倍增法（Binary Lifting）

核心洞察：如果我们预计算每个节点 $v$ 的”向上跳 $2^k$ 步的祖先”，就能把单次向上跳从 $O(n)$ 优化到 $O(\log n)$ 。这就像二进制搜索——任何正整数都可以分解为若干个 2 的幂之和。

预处理（ $O(n \log n)$ 时间和空间）：

构建倍增表 $\text{up}[v][k]$ ，表示节点 $v$ 的第 $2^k$ 个祖先：

基础： $\text{up}[v][0] = \text{parent}(v)$
递推： $\text{up}[v][k] = \text{up}[\text{up}[v][k-1]][k-1]$

递推的含义很直观：向上跳 $2^k$ 步 = 先跳 $2^{k-1}$ 步，再跳 $2^{k-1}$ 步。

查询（ $O(\log n)$ ）：

BinaryLiftingLCA(u, v):
    // 1. 将较深的节点提升到同一深度
    if depth[u] < depth[v]: swap(u, v)
    diff = depth[u] - depth[v]
    for k = ⌊log₂ diff⌋ downto 0:
        if diff ≥ 2^k:
            u = up[u][k]
            diff -= 2^k

    // 2. 如果已经汇合
    if u == v: return u

    // 3. 同步向上跳，找到恰好不汇合的最高位置
    for k = ⌊log₂ n⌋ downto 0:
        if up[u][k] ≠ up[v][k]:
            u = up[u][k]
            v = up[v][k]

    // 4. 再跳一步就是 LCA
    return parent[u]

第 3 步是倍增法最精妙的部分。从大的 $k$ 开始尝试：如果 $\text{up}[u][k] \ne \text{up}[v][k]$ ，说明 LCA 在更上方，放心跳；如果 $\text{up}[u][k] = \text{up}[v][k]$ ，说明跳太远了（跳过了 LCA），不跳。最终 $u$ 和 $v$ 停在 LCA 的两个子节点上。

数值走查

以上图为例，查询 $\text{LCA}(H, J)$ ：

$\text{depth}(H) = 3$ , $\text{depth}(J) = 3$ ，已在同一深度
尝试 $k = 1$ ： $\text{up}[H][1] = B$ , $\text{up}[J][1] = B$ ，相等，不跳
尝试 $k = 0$ ： $\text{up}[H][0] = D$ , $\text{up}[J][0] = E$ ，不等，跳！ $H \to D$ , $J \to E$
$\text{parent}(D) = B = \text{parent}(E)$ ，返回 $B$

$\text{LCA}(H, J) = B$ ，正确。

Tarjan 离线 LCA

如果所有 LCA 查询是提前已知的（离线），Robert Tarjan 在 1979 年提出了一个基于 DFS + 并查集（Union-Find）的优雅算法，均摊复杂度接近 $O(n + q)$ （其中 $\alpha$ 是反 Ackermann 函数，实际可视为常数）。

核心思想：DFS 遍历树。当节点 $v$ 的整棵子树处理完后，将 $v$ 与其父节点合并到同一个并查集集合中。如果此时有一个查询 $\text{LCA}(v, w)$ 且 $w$ 已经访问完毕，那么 $\text{Find}(w)$ （ $w$ 所在集合的代表元素）就是答案——它正好是 $v$ 和 $w$ 的最近公共祖先。

为什么这能正确工作？ 当 DFS 访问完 $v$ 的子树并回到 $v$ 的父节点时， $v$ 被合并到父节点的集合中。此时，已经处理完的节点被逐步”收缩”到越来越高的祖先节点上。对于一个查询 $(u, w)$ ，当 $u$ 被处理时， $w$ （如果已完成）的 $\text{Find}$ 值恰好指向 $u$ 和 $w$ 的 LCA——因为 LCA 以下的所有已完成节点都已经被合并上去了，而 LCA 以上的节点还没有合并。

TarjanLCA(G, root, queries):
    // 初始化并查集
    for each v ∈ V: MakeSet(v), ancestor[v] = v

    DFS(u):
        for each child c of u:
            DFS(c)
            Union(u, c)
            ancestor[Find(u)] = u

        visited[u] = true
        for each query (u, w):
            if visited[w]:
                answer(u, w) = ancestor[Find(w)]

    DFS(root)

复杂度： $O((n + q) \cdot \alpha(n))$ ，其中 $\alpha$ 是反 Ackermann 函数。对所有实际输入 $\alpha(n) \le 4$ ，因此本质上是线性的。

树的直径

问题定义

树的直径（diameter）是树中最长的路径的长度（以边数或边权和计）。直径的两个端点称为最远点对。

两次 BFS 算法

这是求无权树直径最优雅的算法：

从任意节点 $s$ 出发做 BFS，找到离 $s$ 最远的节点 $u$
从 $u$ 出发做 BFS，找到离 $u$ 最远的节点 $v$
$d(u, v)$ 就是直径， $(u, v)$ 就是最远点对

为什么从任意节点出发就能找到直径端点？ 这个结论并不显然。

定理（两次 BFS 正确性）：在无权树中，从任意节点 $s$ 出发 BFS 到达的最远节点 $u$ ，必然是某条直径路径的端点。

证明思路（反证法）：假设 $u$ 不是任何直径的端点。设真正的直径端点为 $(a, b)$ 。由于树中路径唯一， $s$ 到 $u$ 的路径与 $a$ 到 $b$ 的路径要么不相交，要么有重叠段。在任一情况下，都可以证明存在一个比 $d(a, b)$ 更长的路径，矛盾。详细证明见 Diestel, Chapter 1。

复杂度： $O(n)$ （两次 BFS，每次 $O(n)$ ，因为 $m = n - 1$ ）。

树上 DP 求直径

另一种方法是用一次 DFS + 动态规划。对于每个节点 $v$ ，计算经过 $v$ 的最长路径：它等于 $v$ 的两个最深子树深度之和。

// 返回以 v 为根的子树中，从 v 出发的最长路径长度
DFS(v, parent):
    max1 = 0, max2 = 0    // 最长和次长
    for each child c of v (c ≠ parent):
        d = 1 + DFS(c, v)
        if d ≥ max1:
            max2 = max1
            max1 = d
        elif d > max2:
            max2 = d
    diameter = max(diameter, max1 + max2)
    return max1

这个方法同样是 $O(n)$ ，且可以处理带权树（将 1 替换为边权即可）。

树的重心

定义

树的重心（centroid）是这样一个节点 $c$ ：删除 $c$ 后，剩下的各个连通分量（即 $c$ 的各个子树）中，最大的那个尽可能小。形式化地：

$\text{centroid}(T) = \arg\min_{v \in V} \max_{i} \text{size}(\text{subtree}_i(v))$

其中 $\text{subtree}_i(v)$ 是删除 $v$ 后的第 $i$ 个连通分量。

重心定理

定理（重心性质，CLRS Exercise 12.2-4 的树版本）：

树的重心 $c$ 满足：删除 $c$ 后，每个连通分量的大小 $\le \lfloor n/2 \rfloor$
树至多有 2 个重心。如果有 2 个，它们必然相邻
重心是使所有节点到它的距离之和最小的节点

性质 1 最为关键——它保证了重心分解（centroid decomposition）的递归深度是 $O(\log n)$ 。

求重心算法

FindCentroid(T, n):
    // 第一步：DFS 计算所有子树大小
    DFS_size(v, parent):
        size[v] = 1
        for each child c of v (c ≠ parent):
            DFS_size(c, v)
            size[v] += size[c]

    // 第二步：找使最大子树最小的节点
    DFS_size(root, -1)
    centroid = -1, minMax = n
    for each v ∈ V:
        maxSubtree = n - size[v]    // "上面"的部分
        for each child c of v:
            maxSubtree = max(maxSubtree, size[c])
        if maxSubtree < minMax:
            minMax = maxSubtree
            centroid = v
    return centroid

注意”上面的部分”（ $n - \text{size}[v]$ ）也是删除 $v$ 后的一个连通分量。

复杂度： $O(n)$ 。

重心分解

重心不只是一个有趣的定义——它是分治策略应用在树上的关键支点。

重心分解（Centroid Decomposition）的过程：

找到树 $T$ 的重心 $c$
删除 $c$ ，得到若干子树 $T_1, T_2, \ldots$ （每个大小 $\le \lfloor n/2 \rfloor$ ）
对每个 $T_i$ 递归执行步骤 1-2
将每次选出的重心按递归关系连接，形成一棵重心分解树

重心分解树的深度为 $O(\log n)$ ——因为每次递归，子树大小至少减半。这意味着所有经过树上某节点的路径查询，都可以在 $O(\log n)$ 层上分别处理。重心分解是竞赛中树上路径计数问题的核心技术。

重链剖分（Heavy-Light Decomposition）

动机

很多实际问题需要回答树上路径查询：给定节点 $u$ 和 $v$ ，求路径上的边权和/最大值/最小值，或者将路径上所有边权加上一个值。

朴素方法逐个遍历路径上的边，单次查询 $O(n)$ 。有没有办法利用预处理将每次查询降到 $O(\log n)$ 级别？

核心思想

重链剖分（Heavy-Light Decomposition, HLD）将树的边分为重边和轻边两类：

重边（heavy edge）：从 $v$ 连向其子树最大的子节点的边
轻边（light edge）：其余所有边

连续的重边构成重链（heavy path/chain）。

关键性质

定理：从任意节点 $v$ 到根，经过的轻边数量不超过 $O(\log n)$ 。

证明：每经过一条轻边，意味着从子树大小较小的子节点向上走。走轻边之前，当前子树大小 $s$ ；走轻边之后，新的子树大小 $s' \ge 2s$ （因为轻子节点的子树大小 $\le$ 重子节点的子树大小 $<$ 父节点子树大小的一半，所以父节点子树大小 $> 2 \times$ 轻子节点的子树大小）。从 1 到 $n$ 最多翻倍 $\log_2 n$ 次。

推论：任意两个节点 $u$ 和 $v$ 之间的路径最多跨越 $O(\log n)$ 条重链。

这意味着：如果我们对每条重链维护一个线段树（segment tree），路径查询只需要在 $O(\log n)$ 个线段树上分别查询。每个线段树查询 $O(\log n)$ ，总复杂度 $O(\log^2 n)$ 。

HLD 路径查询流程

PathQuery(u, v):
    result = identity
    while head[u] ≠ head[v]:    // u 和 v 不在同一条重链上
        if depth[head[u]] < depth[head[v]]: swap(u, v)
        // u 的链头更深 → 处理 u 所在链的一段
        result = combine(result, query(pos[head[u]], pos[u]))
        u = parent[head[u]]     // 跳到链头的父节点（轻边）
    // 现在 u 和 v 在同一条重链上
    if depth[u] > depth[v]: swap(u, v)
    result = combine(result, query(pos[u], pos[v]))
    return result

其中 $\text{head}[v]$ 是 $v$ 所在重链的顶端节点， $\text{pos}[v]$ 是 $v$ 在 DFS 序中的位置（用于线段树索引）。

树与其他结构的关系

树不是孤立存在的——它与我们已经学过的很多图结构有深刻的联系。

DFS 树与 BFS 树（回顾 Art. 1）

在 Art. 1 中我们已经看到：对一般图做 DFS 或 BFS 遍历时，选中的”树边”构成一棵生成树。

DFS 树：深而窄。非树边都是回边（无向图）或回边/前向边/横跨边（有向图）。DFS 树是发现割点、桥、SCC 的基础（Art. 2）
BFS 树：浅而宽。非树边只连接同层或相邻层的节点。BFS 树的层结构给出无权最短路

生成树（→ Art. 11）

连通图 $G$ 的生成树（spanning tree）是一个包含 $G$ 所有顶点的子图，且自身是一棵树。一张连通图可能有指数级多棵生成树。

当边有权重时，自然的问题是：哪棵生成树的边权和最小？这就是最小生成树（Minimum Spanning Tree, MST）问题，我们将在 Art. 11 详细讨论 Kruskal 和 Prim 算法。

支配树（Dominator Tree）

在有向图（特别是编译器的控制流图 CFG）中，节点 $a$ 支配（dominate）节点 $b$ ，当且仅当从入口节点到 $b$ 的每条路径都经过 $a$ 。每个节点 $b$ 的直接支配节点（immediate dominator, idom）是离 $b$ 最近的支配节点。将每个节点与其 idom 相连，就得到一棵支配树。

支配树是编译器构建 SSA（Static Single Assignment） 形式的基石。在 SSA 中，编译器需要确定在哪些位置插入 $\phi$ 函数——这正好由支配边界（dominance frontier）决定，而支配边界依赖支配树。

Lengauer-Tarjan 算法（1979）能在 $O(m \cdot \alpha(m, n))$ 时间内计算支配树，几乎是线性的。简化版本（使用 $O(m \log n)$ ）在实践中也表现良好。算法的核心是巧妙地利用 DFS 树的性质和路径压缩。完整实现超出本文范围，但概念上它建立了一个关键桥梁：控制流分析 → 支配关系 → 树结构 → 高效查询。

交互式工具箱

下面的交互组件在同一棵树上展示 LCA、直径、重心和重链剖分四种算法的不同视角。点击不同的标签页，观察同一棵树上哪些结构被高亮。

树算法工具箱

LCA（最近公共祖先）：H 和 J 的最近公共祖先是 B。路径 H→D→B←E←J 在 B 处汇合。

应用场景

编译器 SSA 与支配树

现代编译器（GCC、LLVM、V8）都使用 SSA 中间表示。SSA 的核心步骤—— $\phi$ 函数插入——依赖支配边界，而支配边界由支配树计算。没有高效的支配树算法，编译器优化（常量传播、死代码消除、循环不变量外提）都无法高效实现。Lengauer-Tarjan 算法是 LLVM 的标准选择。

文件系统与目录层次

Unix/Linux 文件系统是一棵以 / 为根的树。find 命令本质上是 DFS 遍历；两个文件的”最近公共目录”就是 LCA；du 命令计算每个目录的子树大小。

XML/JSON 解析与 XPath

HTML/XML 的 DOM（Document Object Model）是一棵树。XPath 查询语言中，“最近公共祖先”（lowest common ancestor）是常用操作。浏览器的 CSS 选择器引擎、React 的 Virtual DOM diff 算法、数据库的 XML 索引，都依赖高效的树上查询。

系统发育树（Phylogenetic Tree）

生物信息学中，物种的演化关系用系统发育树表示。两个物种的最近共同祖先直接对应 LCA 操作。大规模系统发育分析（如 Open Tree of Life 项目，200 万+ 物种）需要高效的 LCA 算法。树的直径对应演化距离最远的两个物种，重心对应演化”中心”。

复杂度对比表

算法	预处理时间	查询/执行时间	空间复杂度	适用场景
朴素 LCA	$O(n)$	$O(n)$ 每次查询	$O(n)$	单次查询或小树
倍增法 LCA	$O(n \log n)$	$O(\log n)$ 每次查询	$O(n \log n)$	多次在线查询
Tarjan 离线 LCA	—	$O((n + q) \cdot \alpha(n))$ 总计	$O(n + q)$	所有查询预先已知
两次 BFS 直径	—	$O(n)$	$O(n)$	无权树直径
树上 DP 直径	—	$O(n)$	$O(n)$	带权树直径
求重心	—	$O(n)$	$O(n)$	找重心节点
重心分解	$O(n \log n)$	$O(\log n)$ 层	$O(n \log n)$	树上路径计数/统计
HLD + 线段树	$O(n)$	$O(\log^2 n)$ 每次路径查询	$O(n)$	路径聚合查询/修改
Lengauer-Tarjan	—	$O(m \cdot \alpha(m, n))$	$O(n)$	支配树构建

🔁 迭代机器视角 — Tree traversal (BFS/DFS on trees)STR: 结构计算

Graph	树（无环连通图）
State[v]	visited + 遍历结果
SELECT	FIFO (层序) / LIFO (前/中/后序)
COMBINE	遍历子节点
重入	无（树无环）
TERMINATE	Frontier 空
求解方法	FI

树上遍历是 BFS/DFS 在无环图上的特化——无需 visited 检查（无回边）

→ 框架详解：Art. 0A — 图上的通用迭代机器

🔁 迭代机器视角 — LCA (Lowest Common Ancestor)STR: 结构计算

Graph	有根树
State[v]	depth + parent/sparse table
SELECT	DFS 后序（bottom-up）
COMBINE	合并子树深度/祖先信息
求解方法	DP

Binary Lifting 版本用 DP 预处理 sparse table，Tarjan 离线版本用 DFS + Union-Find

→ 框架详解：Art. 0A — 图上的通用迭代机器

总结

本文建立了一套完整的树上算法工具箱：

树 = 连通无环图： $|E| = |V| - 1$ ，任意两点间唯一路径，这是所有树算法高效性的根源
LCA：倍增法 $O(\log n)$ 在线查询，Tarjan 离线接近线性，LCA 是路径查询的基石
直径：两次 BFS 即可求出最远点对， $O(n)$
重心：删除后最大子树最小的节点，保证每个子树 $\le \lfloor n/2 \rfloor$ ，是分治策略在树上的支点
HLD：将树路径分解为 $O(\log n)$ 条重链，配合线段树实现 $O(\log^2 n)$ 的路径查询
支配树：控制流图的支配关系构成树结构，是编译器 SSA 的基石

树是图的”最简骨架”——连通但没有多余的边。正因如此，它拥有比一般图强大得多的结构化查询能力。

Part 1”探”至此收官。我们从 BFS/DFS 的基本遍历出发，经过连通性分析、拓扑排序、特殊路径问题，最终来到树这一图的极简形态。接下来进入 Part 2”量”——不再只是”看清结构”，而是开始度量：节点之间的距离有多远？哪些节点最重要？哪些节点抱团？第一站 Art. 6: 最短路径将回答最基本的度量问题：给定加权图，两个节点之间的最短距离是多少？

实现指引

算法	库	函数/方法
LCA	NetworkX	`nx.lowest_common_ancestor(G, node1, node2)`
LCA（所有对）	NetworkX	`nx.all_pairs_lowest_common_ancestor(G)`
树的判定	NetworkX	`nx.is_tree(G)`
树的直径（近似）	NetworkX	`nx.diameter(G)` （计算图直径，适用于树）
重心	NetworkX	`nx.center(G)` （返回图的中心，树上即重心）
支配树	NetworkX	`nx.immediate_dominators(G, start)`
支配边界	NetworkX	`nx.dominance_frontiers(G, start)`
LCA	igraph	`g.get_all_simple_paths()` 辅助实现
树操作	scipy	`scipy.sparse.csgraph` 子模块