从一道GESP六级真题出发：聊聊树形DP中的路径覆盖问题

COCOgsta

241人浏览 · 2026-09-04 10:37:05

COCOgsta · 2026-09-04 10:37:05 发布

题源：洛谷 P14919 [GESP202512 六级] 路径覆盖
题目链接

1. 背景

在算法竞赛中，"树上路径覆盖"是一类非常经典的问题，也是树形DP入门之后必然会遇到的重要题型。这类问题的核心表述通常是：选择若干个节点，使得所有叶子到根节点的路径上都至少有一个被选中的节点，在此基础上最小化选择代价。

乍看之下，这似乎是一个需要全局搜索的复杂组合优化问题——毕竟每个节点都有"选"与"不选"两种状态，暴力枚举是指数级的。但树形结构的天然递归性给了我们一个优雅的解法：自底向上的动态规划，每个节点的决策只依赖于其子树的子问题。

本题在GESP六级中定位为"普及"难度，是树形DP的入门级经典题。它不需要复杂的多状态设计——每个节点只需维护一个值 $w [u]$ ，代表以 $u$ 为根的子树满足条件的最小代价。转移方程也极其简洁：要么自己染黑，要么让所有子树各自搞定。

本文将带你从"直观理解覆盖问题"开始，逐步推导出树形DP的转移方程，并深入分析为什么自底向上是唯一正确的处理顺序。无论你是刚接触树形DP的新手，还是想巩固基础的老手，本文都能给你带来一些启发。

2. 核心思想章节

2.1 问题的本质：选点覆盖所有"根到叶"路径

想象一棵家族树，根节点是族长，叶子节点是家族中最小的成员。现在有一条规矩：从每个叶子到族长的路径上，至少要有一个被标记的人。标记每个人需要花钱。你想花最少的钱完成这个任务。

这个任务的本质是：用最少的钱在树上"拦截"所有从根到叶子的路径。如果在一个节点上花钱标记了它，那么所有经过该节点的叶子路径都被"拦截"了，不再需要在该节点的子树中额外花钱。

这就引出了一个关键的递归决策：对于任意一个节点 $u$ ，我们有两种选择：

在 $u$ 上花钱： $u$ 以下的所有叶子路径都被覆盖了，子树中不需要再花一分钱。
不在 $u$ 上花钱：那么每个子树 $v$ 必须自己搞定——即每个子树 $v$ 中必须至少有一个被标记的节点，覆盖从 $v$ 到其所有叶子路径。

两种方案取代价较小的那个，就是 $u$ 子树的最优解。这就是树形DP的最优子结构。

2.2 状态设计：一个值足以

很多树形DP需要设计多个状态（如"选/不选当前节点""当前节点是否被覆盖"等），但本题的状态设计极其精简：

$w [u]$ ：以 $u$ 为根的子树中，满足"所有叶子到 $u$ 的路径上至少有一个黑色节点"的最小代价。

注意这里的关键是"到 $u$ 的路径"而不是"到根的路径"。因为当我们处理 $u$ 的子树时， $u$ 上面的节点（祖先）还没决定是否染黑，我们不能依赖它们。每个子树问题都是独立的，边界条件就是 $u$ 本身。

转移方程：

如果 $u$ 是叶子节点： $w[u] = c_u$ 。叶子必须自己染黑，因为没有子节点可以依赖。
如果 $u$ 不是叶子节点：
$\min\left(c_u,\; \sum_{v \in \text{children}(u)} w[v]\right)$

这个方程的意思是：

$c_u$ ：在 $u$ 染黑，覆盖了所有经过 $u$ 的叶子路径，子树中不再需要黑色节点。
$\sum w[v]$ ：不在 $u$ 染黑，那么每个子树必须独立满足条件，总代价为各子树最优代价之和。

2.3 后序遍历：先算儿子，再算父亲

树形DP的核心执行顺序是后序遍历——先递归处理所有子节点，等子节点的 $w$ 值都计算完毕之后，再来计算当前节点的 $w$ 值。

为什么必须这样？因为当前节点的 $w$ 值依赖于所有子节点的 $w$ 值（求和），而子节点的 $w$ 值又依赖于它们的子节点……这种依赖关系是自底向上的。如果你从根开始向下算，子节点的值还没算出来，你什么也做不了。

这就像盖一栋楼——必须先打地基、再建楼层，最后封顶。你不能从楼顶往下盖。树形DP的后序遍历，就是"从地基到楼顶"的正确施工顺序。

2.4 叶子节点是边界

在树形DP中，叶子节点往往是递归的"出口"。对于本题，叶子节点没有子节点，所以 $\sum w[v]$ 为空，等于 0。如果直接套用转移方程 $w[u] = \min(c_u, 0) = 0$ ，会得到错误的结果——叶子必须自己染黑，代价是 $c_u$ ，而不是 0。

因此在代码实现中，通常需要显式判断叶子节点并特殊处理：如果 a[u].empty()，直接返回， $w [u]$ 保持初始值 $c_u$ 。

小结：本题的核心转移是"自己染黑"与"子树各自搞定"二者取最小。后序遍历保证了子问题的解在父问题计算前已经就绪。叶子节点的边界处理则是必须注意的实现细节。

3. 算法模板章节

3.1 算法到底在干什么？—— 直觉解释

你是一个项目经理，手下有一棵汇报关系树。每个员工（节点）都有一个"自爆价"——给这个员工发奖金让他搞定自己的部门。你需要确保每个部门的"底线员工"（叶子节点）到你的路径上至少有一个人拿了奖金。

对于每一个部门经理 $u$ ，他的决策很简单：

方案A：直接给 $u$ 发奖金。这样 $u$ 手下所有人都不用管了，成本就是 $u$ 的报价。
方案B：不给 $u$ 发奖金。那就让每个子部门各自搞定，成本就是所有子部门成本之和。

两个方案哪个便宜选哪个，算出来的就是 $u$ 这个部门的最小成本。

当你从最底层的小部门（叶子）开始，一层层往上算，最后算到总经理（根节点）的部门成本，就是整个公司的最小成本。

3.2 万能模板 —— 伪代码 + 实战代码

伪代码：

读入 n, 父节点 f[2..n], 代价 c[1..n]
建立邻接表 children[u]

dfs(u):
    if children[u] 为空:
        return          // w[u] 保持为 c[u]
    
    sum = 0
    for v in children[u]:
        dfs(v)
        sum += w[v]
    
    w[u] = min(w[u], sum)   // w[u] 初始为 c[u]

main:
    读入数据，建树
    dfs(1)
    输出 w[1]

完整 AC 代码（C++，带注释）：

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 100005;

int n;
int w[N];                 // w[u]: 以 u 为根的子树的最小代价
vector<int> children[N];  // children[u]: u 的所有子节点列表

// 后序遍历计算每个节点的 w 值
void dfs(int u) {
    // 叶子节点：没有子节点，无需计算，w[u] 保持为 c[u]
    if (children[u].empty()) {
        return;
    }

    int sum = 0;
    // 先递归处理所有子节点
    for (int v : children[u]) {
        dfs(v);
        sum += w[v];
    }

    // 决策：要么自己染黑（代价 w[u] 初始为 c[u]），
    // 要么让所有子树各自搞定（代价 sum）
    w[u] = min(w[u], sum);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    // 读入父节点信息，建树
    for (int i = 2; i <= n; i++) {
        int parent;
        cin >> parent;
        children[parent].push_back(i);
    }

    // 读入每个节点的染黑代价
    for (int i = 1; i <= n; i++) {
        cin >> w[i];   // w[i] 初始值为 c[i]
    }

    // 从根节点开始后序遍历
    dfs(1);

    cout << w[1] << endl;
    return 0;
}

3.3 例题实现 —— 本题完整运行流程

以样例为例：

n = 4
父节点: f[2]=1, f[3]=2, f[4]=3
树结构: 1 → 2 → 3 → 4 (一条链)
代价: c[1]=5, c[2]=6, c[3]=2, c[4]=3

后序遍历：

dfs(4)：4 是叶子节点，直接返回，w[4] 保持为 3。
dfs(3)：
- 子节点只有 4，sum = w[4] = 3
- w[3] = min(c[3]=2, sum=3) = 2（在 3 染黑更便宜）
dfs(2)：
- 子节点只有 3，sum = w[3] = 2
- w[2] = min(c[2]=6, sum=2) = 2（依赖子树更便宜）
dfs(1)：
- 子节点只有 2，sum = w[2] = 2
- w[1] = min(c[1]=5, sum=2) = 2

输出 2，与样例一致。✅

最优方案是：在节点 3 染黑（代价 2），叶子 4 到根 1 的路径（4-3-2-1）上经过节点 3，被覆盖。全部路径覆盖完毕，总代价 2。

3.4 对比实现 —— 如果错用了贪心会怎样？

有人可能会想：我每次选当前最便宜的节点染黑，然后删掉所有被覆盖的叶子路径，重复这个过程——这不就是贪心吗？

贪心策略：在所有叶子到根的路径上，选代价最小的"覆盖路径最多的节点"染黑。

让我们试一下样例：链 1-2-3-4，代价 5,6,2,3。最便宜的是节点 3（代价 2），选中 3 后，叶子 4 到根 1 的路径被覆盖，全部叶子（只有 4）路径都被覆盖了，完成。总代价 2，看起来好像没问题。

但如果树是分叉的：

    1 (100)
   / \
  2(1) 3(1)

叶子是 2 和 3。贪心会选 2 和 3（各代价 1，总 2），但最优方案是染黑根节点 1（代价 100？等等那反而不优）。这个例子中贪心就是最优的。

换一个：

       1 (10)
      / \
    2(6) 3(6)
   /       \
  4(1)     5(1)

叶子是 4 和 5。贪心会选 4 和 5（总 2），但最优方案是染黑 2 和 3（总 12）？2+12=14 > 2，贪心反而更好？不对，染黑 4 只覆盖了 4 到 1 的路径（4-2-1），叶子 5 的路径（5-3-1）还没覆盖，还需要染黑 5，总代价 2。所以贪心是对的。

那有没有贪心失败的例子？考虑：

       1 (100)
      / \
    2(50) 3(50)
   / \      \
  4(1) 5(1) 6(1)

叶子 4、5、6。贪心选代价 1 的节点：4、5、6 都是 1，任意选一个，比如选 4，覆盖路径 4-2-1；再选 5，覆盖 5-2-1；再选 6，覆盖 6-3-1。总代价 3。但最优方案是染黑 2 和 3（总 100），不优。或者染黑 1（100），也不优。所以贪心 3 确实是最优。

看来这个贪心在这个树上似乎总是对的？实际上不是。贪心会失败在"一个中等代价的节点能覆盖多个叶子"的场景。比如：

          1 (100)
         / \
       2(10) 3(10)
      / \    / \
    4(9) 5(9) 6(9) 7(9)

叶子 4,5,6,7。贪心选代价最小的叶子：4,5,6,7 都是 9，选一个覆盖一条路径；选完 4 个叶子总代价 36。但最优方案是染黑 2 和 3（总 20），覆盖所有叶子路径。贪心完败！

所以贪心不可靠，树形DP才是正解。贪心的局部最优无法保证全局最优，因为"一个节点覆盖多条路径"的价值需要在全局层面权衡。

3.5 变体清单

变体场景	处理方法	与本题的差异
节点染黑代价可正可负	DP 方程依然成立，但负代价节点会被优先选择	本题代价为正
要求路径上恰好一个黑色节点	多状态 DP，需要额外维护"是否已选"状态	本题为"至少一个"
不仅是叶子路径，而是所有节点到根路径	问题变为"根到所有节点的路径"，本质上一样	目标节点范围不同
不是染黑节点，而是覆盖边（选边覆盖路径）	对边进行 DP，状态定义变为边的代价	覆盖对象从点变为边
树不是有根树（无向树）	需要先任选一个根，转换为有根树处理	本题已给根
每个叶子到根路径上至少 k 个黑色节点	状态需要维护"离最近黑色节点的距离"，用树上背包	本题 k=1
需要输出具体方案（哪些节点染黑）	在 DP 过程中记录决策来源，最后回溯构造	本题只求代价

3.6 什么时候不能用？

图不是树：树形DP依赖无环结构，若图有环，需换用其他算法（如最小点覆盖的复杂版本）。
路径覆盖不是"根到叶子"方向：如果要求覆盖所有节点对之间的路径（任意两点），问题变为树上的最小点覆盖或 Steiner 树，更复杂。
每个节点有选择限制（如某些节点不能染黑）：将对应 $c_u$ 设为 $\infty$ 即可，DP 框架不变。
树规模极大（ $\ge 10^6$ ）：需要优化递归（改为迭代栈）或使用非递归 DFS，但 DP 框架不变。

4. 底层逻辑章节

4.1 为什么后序遍历是必要条件？

树形DP的状态依赖关系形成了一个有向无环图（DAG），方向从叶子指向根。 $w [u]$ 依赖于 $w [v]$ （ $v$ 是 $u$ 的子节点），而 $w [v]$ 依赖于更深的节点。这种依赖关系的拓扑排序，恰好就是后序（先子后父）。

如果我们尝试用前序（先父后子）或层序（从上往下），会发现父节点的值需要子节点的值，但子节点的值还没算出来——这就像想用明天的报纸预测今天的天气，逻辑上不通。

后序遍历保证了：当计算 $w [u]$ 时，所有子节点的 $w [v]$ 都已经是最终值，可以直接使用。这是树形DP能够高效运行的基础。

4.2 为什么"自己染黑"就无需再管子树？

这是本题最核心的直觉：如果节点 $u$ 被染黑，那么从 $u$ 子树中的任意一个叶子 $L$ 到根节点的路径（ $\to \dots \to u \to \dots \to root$ ）上， $u$ 本身就是一个黑色节点。因此， $u$ 到其所有叶子的路径已经被覆盖，子树内部不需要任何额外的黑色节点。

换句话说，染黑 $u$ 相当于在 $u$ 的位置"拦截"了所有经过 $u$ 的叶子路径，把问题在 $u$ 处截断了。所以子树内部的代价为 0，只需要付出 $c_u$ 即可。

这就是为什么转移方程中是 $\min(c_u, \sum w[v])$ ，而不是 $\min(c_u + \text{something}, \sum w[v] + \text{something})$ 。染黑 $u$ 后，子树就完全不需要管了。

4.3 叶子节点的特殊处理：为什么不能套用转移方程？

对于叶子节点 $u$ ，它没有任何子节点。如果套用转移方程：
$\min(c_u, \sum_{v \in \emptyset} w[v]) = \min(c_u, 0) = 0$

这显然是错的——叶子必须自己染黑，因为没有子节点可以替代它覆盖"叶子到根"的路径。实际上，叶子节点的"让子树各自搞定"方案是不可行的（因为根本没有子树），所以 $w [u]$ 只能是 $c_u$ 。

在代码中，我们通过"叶子直接返回，不执行 w[u] = min(w[u], sum)"来处理这个边界。另一种常见的写法是：在 DP 前将叶子节点的 $w [u]$ 初始化为 $c_u$ ，在转移时如果 $u$ 是叶子则跳过 min 操作。

4.4 与"树的最小顶点覆盖"的对比

树的最小顶点覆盖问题是：选择最少的节点，使得每条边至少有一个端点被选中。而本题是：选择节点覆盖所有根到叶子的路径。两者有本质区别：

最小顶点覆盖关心的是边，每条边都需要被端点覆盖。
本题关心的是路径，每条叶子到根的路径都需要至少一个选中节点。

这导致了两者的 DP 状态设计不同：最小顶点覆盖需要用两个状态（选/不选当前节点），而本题用一个状态就够了，因为决策是"自己染黑 vs 子树各自搞定"，不需要区分"当前节点是否被覆盖"，因为根到叶子的路径天然包含了当前节点。

可以这样理解：最小顶点覆盖是一个"局部"约束（每条边），而路径覆盖是一个"全局"约束（每条根到叶子的完整路径），但树的层级结构让后者反而更容易用单状态 DP 处理。

5. 决策表：不同思路的适用场景

场景	方案	时间复杂度	空间复杂度	优点	缺点
树形DP（后序）	自底向上计算每个子树的最优代价	$O (n)$	$O (n)$	最优解，效率高	需要理解DP思想
贪心（每次选最便宜节点）	选代价最小的覆盖最多路径的节点	可能 $O(n^2)$	$O (n)$	实现简单	不保证最优，可能失败
暴力枚举所有子集	枚举每个节点的选/不选状态	$O(2^n)$	$O (n)$	保证最优（小数据）	指数级，不可扩展
将树转为线性序列	用树链剖分 + 线段树维护DP	$O(n \log^2 n)$	$\log n)$	支持动态修改	本题无修改，杀鸡用牛刀
最小割（网络流）	建图跑最大流，割对应染黑方案	$O(\text{maxflow})$	$O (n + m)$	适用于带额外约束的变体	实现复杂，不如DP直观
多状态DP（选/不选）	维护两个状态，覆盖更多变体	$O (n)$	$O (n)$	扩展性强	本题不需要，单状态即可

6. 工程视角

"树形DP选点覆盖路径"的模型在实际场景中有许多应用：

网络监控系统的传感器部署：在树形网络拓扑中，需要在一些节点部署传感器，使得从任何叶子节点（终端设备）到根节点（数据中心）的路径上至少有一个传感器。传感器的部署成本不同，需要最小化总成本。
供应链中的安全检查点：供应链从原材料（叶子）到最终工厂（根）是一条路径，需要在中间节点设置检查点，使得每条供应路径至少经过一个检查点。不同位置设置检查点的成本不同。
软件开发中的代码审查：在模块依赖树中，从底层模块（叶子）到主模块（根）的每条依赖链上至少需要一个代码审查节点。不同模块的审查成本不同。
分布式系统中的容错备份：在树形服务依赖中，从依赖叶子到根服务的每条调用链需要至少一个备份节点。不同服务的备份成本不同。
教育体系中的资源分配：从每个基层学校（叶子）到教育局（根）的管理路径上至少需要一个资源协调员，不同层级设置协调员的成本不同。