GESP 题解库 / 6 级题解 / [GESP202512 六级] 路径覆盖 · 第 4 / 27 题
GESP202512 六级 · P14919 · 中等

路径覆盖

树上选点染黑,使每条叶子到根的路径上至少一个黑点,最小化总代价。

📊
n ≤ 10⁵
结点数量
🔢
long long
代价范围
⚡
O(n)
时间复杂度
🎯
树形 DP(两状态)
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定一棵以 1 为根的有根树,结点初始全白。要把若干结点染黑,使所有叶子到根的路径上至少有一个黑点。结点 i 染黑需代价 cᵢ,求最小总代价。

叶子指没有子结点的结点。

💡
人话翻译:树形 DP 的经典模型。关键是为每个结点设计两个状态:
dp[u][0]:假设"u 到根的方向上还没有黑点",把 u 子树覆盖完的最小代价;
dp[u][1]:假设"u 上方已经有黑点",把 u 子树覆盖完的最小代价(此时子树其实已自动覆盖,只需保证递归一致)。

🔍 关键词提取

树形 DP状态设计自底向上避免递归爆栈

已知条件

项目说明
输入第一行 n;第二行 n−1 个 f₂…fₙ;第三行 n 个 cᵢ
输出最小染色代价
数据范围2 ≤ n ≤ 10⁵
树上性质fᵢ < i(父结点编号更小)
代价范围1 ≤ cᵢ ≤ 10⁹

需要解决的问题

02
思维导图
整理解题思路的全貌
🌳 树形 DP:两个状态定乾坤
🧠 状态定义
dp[u][0]:上方没有黑点
dp[u][1]:上方已有黑点
区别在于"谁来覆盖叶子"
自底向上计算
🍃 叶子
无子结点
dp[u][0] = c_u(必须自己染)
dp[u][1] = 0(已覆盖)
这是边界
🌲 内部结点
dp[u][1] = Σ dp[v][1]
dp[u][0] = min(c_u + Σ dp[v][1], Σ dp[v][0])
两种决策:染自己 or 让孩子自己解决
取较小值
⚠️ 易错点
只用一个状态(无法区分情形)
递归爆栈(n 达 10⁵)
用 int(代价可达 10¹⁴)
把根结点当成"上方有黑点"
03
样例手算推导
两个样例的完整推演

🧮 样例 1:一条链 1 → 2 → 3 → 4

n = 4,f = [1, 2, 3](即 f₂=1、f₃=2、f₄=3),c = [5, 6, 2, 3]。叶子只有结点 4。

1
结点 4(叶子)

dp[4][0] = c₄ = 3(上方没黑点,必须自己染)

dp[4][1] = 0(上方已有黑点,自动覆盖)

dp[4] = (3, 0)

2
结点 3(唯一孩子是 4)

dp[3][1] = dp[4][1] = 0

dp[3][0] = min(c₃ + dp[4][1], dp[4][0])

= min(2 + 0, 3) = min(2, 3) = 2

即"染结点 3 自己"(代价 2)比"让 4 自己染"(代价 3)划算

dp[3] = (2, 0)

3
结点 2

dp[2][1] = dp[3][1] = 0

dp[2][0] = min(6 + 0, dp[3][0]) = min(6, 2) = 2

让结点 3 染黑(2)比染结点 2(6)便宜

dp[2] = (2, 0)

4
结点 1(根,它上方一定没有黑点)

dp[1][1] = dp[2][1] = 0(实际上根用不到这个状态)

dp[1][0] = min(5 + 0, dp[2][0]) = min(5, 2) = 2

答案 = dp[1][0] = 2

✅ 答案 2

最优方案:只把结点 3 染黑(代价 2),叶子 4 到根 1 的路径 4→3→2→1 上经过了 3 ✓

🧮 样例 2:分叉树

n = 7,f = [1, 1, 2, 2, 3, 3] → 1 的孩子是 2、3;2 的孩子是 4、5;3 的孩子是 6、7。叶子是 4、5、6、7。c = [64, 16, 15, 4, 3, 2, 1]。

1
层 1:叶子 4、5、6、7

dp[4] = (4, 0)、dp[5] = (3, 0)

dp[6] = (2, 0)、dp[7] = (1, 0)

四个叶子的状态已定

2
层 2:结点 2 与 3

dp[2][1] = dp[4][1] + dp[5][1] = 0

dp[2][0] = min(c₂ + (dp[4][1]+dp[5][1]), dp[4][0]+dp[5][0])

= min(16 + 0, 4 + 3) = min(16, 7) = 7

dp[3][1] = 0

dp[3][0] = min(15 + 0, 2 + 1) = min(15, 3) = 3

dp[2] = (7, 0),dp[3] = (3, 0)

3
层 3:根结点 1

dp[1][0] = min(c₁ + (dp[2][1]+dp[3][1]), dp[2][0]+dp[3][0])

= min(64 + 0, 7 + 3) = min(64, 10) = 10

答案 = dp[1][0] = 10

✅ 答案 10

📊 各结点状态汇总

结点cdp[·][0]dp[·][1]决策说明
4(叶)440必须自己染
5(叶)330必须自己染
6(叶)220必须自己染
7(叶)110必须自己染
21670让孩子 4、5 自己染(4+3=7 < 16)
31530让孩子 6、7 自己染(2+1=3 < 15)
1(根)6410—让 2、3 子树自己解决(7+3=10 < 64)

最优方案:叶子 4、5、6、7 都染黑,总代价 4+3+2+1 = 10 ✓

🔑
这组数据很有启发:根结点染色要 64、结点 2 要 16、结点 3 要 15——都很贵;而四个叶子加起来只要 10。所以最优解是"在叶子处全部染黑"。dp[u][0] 里的 min 正好在这两种策略间取更便宜的那个。
04
解法对比
树形 DP vs 状压/贪心

⚔️ 解法对比

🟢 树形 DP(两状态)(推荐) 推荐

自底向上算 dp[u][0] 与 dp[u][1],答案是 dp[1][0]

  • 时间 O(n)
  • n = 10⁵ 时约 10⁵ 次
  • 代码 25 行(迭代版)
  • 空间 O(n)
💡
两个状态的含义要记清:dp[u][0] 表示"u 上方无黑点"、dp[u][1] 表示"u 上方有黑点"。转移里的 min 恰好对应"在 u 染色"与"让子树自己解决"两种策略的取舍。

🟠 状压 / 枚举染哪些结点

枚举所有染色方案,检查是否覆盖所有叶子路径

  • 复杂度 2ⁿ
  • 40% 测试点 n ≤ 16 时可得部分分
  • n = 10⁵ 完全不可行
  • 只适合小数据
⚠️
注意数据分档:40% 的测试点 n ≤ 16(可以状压拿 40 分),但想满分必须用树形 DP。另外注意:这题不能贪心——"从叶子往上找最便宜的点"这类贪心在多分支树上会被反例击破。

📈 性能对比

方案复杂度可行性
树形 DPO(n)✅ 稳过
状压枚举O(2ⁿ)❌ n 大时不可行
贪心选点O(n)❌ 无正确性保证
05
算法流程图
自底向上做两状态树形 DP
开始读入 n、父结点数组 f、代价数组 c初始化:sum0[u] = 0、sum1[u] = 0、deg[u] = 0i 从 n 递减到 2结点 i 是否有孩子(deg[i] 是否为 0)?是 ✓叶子:dp0 = c[i],dp1 = 0否 ✗内部:dp1 = sum1[i],dp0 = min(c[i] + sum1[i], sum0[i])把 dp0、dp1 累加到父结点 f[i] 的 sum0、sum1,并把 deg[f[i]] 加 1i 减 1 继续(这样保证孩子先于父亲算完)输出根结点的 dp0i 减 1 处理下一个
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🌳 最小染色代价

第一行输入 n,第二行输入父结点,第三行输入代价,程序会自底向上算 dp。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(迭代版,避免递归爆栈)

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

long long c[100005];
int par[100005], degCnt[100005];
long long sum0[100005], sum1[100005];   // 孩子 dp 的累加
long long dp0[100005], dp1[100005];

int main() {
    int n;
    scanf("%d", &n);
    par[1] = 0;
    for (int i = 2; i <= n; i++) scanf("%d", &par[i]);
    for (int i = 1; i <= n; i++) scanf("%lld", &c[i]);

    // 因为 f_i < i,孩子编号一定大于父亲
    // 所以从 n 递减到 2 处理,能保证"孩子先算完"
    for (int i = n; i >= 2; i--) {
        if (degCnt[i] == 0) {          // 叶子:上方没黑点就必须自己染
            dp0[i] = c[i];
            dp1[i] = 0;
        } else {                        // 内部结点
            dp1[i] = sum1[i];
            dp0[i] = min(c[i] + sum1[i], sum0[i]);
        }
        // 把结果累加给父亲
        int p = par[i];
        sum0[p] += dp0[i];
        sum1[p] += dp1[i];
        degCnt[p]++;
    }

    // 根结点(它上方一定没有黑点,所以取 dp0)
    long long ans;
    if (degCnt[1] == 0) ans = c[1];     // 特殊情形:n = 1
    else ans = min(c[1] + sum1[1], sum0[1]);

    printf("%lld\n", ans);
    return 0;
}
🔑
为什么不用递归?n 可达 10⁵,如果树退化成一条链,递归深度就是 10⁵,会爆栈(默认栈空间通常只够几万层)。
而题目给了关键条件 fᵢ < i——父亲的编号一定小于孩子,所以只要从 n 递减到 2 遍历,就一定能在处理父结点前算完所有孩子。这个"逆序迭代"技巧让代码既简单又不会爆栈。

📖 关键几行怎么看

代码作用为什么这样写
fᵢ < i 的利用逆序遍历的基础孩子编号更大 → 从 n 往下处理
degCnt[i] == 0判断叶子累加过程中统计孩子个数
dp0[i] = min(c[i] + sum1[i], sum0[i])核心转移染自己 vs 让子树自己解决
sum0[p] += dp0[i]向上汇总把孩子的 dp 累加到父亲
ans = min(c[1] + sum1[1], sum0[1])根的答案根上方无黑点,所以用 dp0 的公式
⚠️
四个坑:① 用递归导致爆栈(n 达 10⁵);② 只设一个状态(无法区分"上方有无黑点");③ 用 int(n × cᵢ 可达 10⁵ × 10⁹ = 10¹⁴);④ 答案错误地取 dp[1][1](根上方没有黑点,应该取 dp[1][0])。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4
1 2 3
5 6 2 3
2题面样例 1(一条链,染结点 3)
7
1 1 2 2 3 3
64 16 15 4 3 2 1
10题面样例 2(四个叶子全染)
2
1
5 3
3一条边:染叶子更便宜
2
1
3 5
3一条边:染根更便宜
3
1 1
10 1 1
2根贵,两个叶子各染一次
✅
自查清单:① 用迭代而非递归吗?② 两个状态都有吗?③ 答案取根结点的 dp0 吗?

🚨 易错点清单

⚠️
递归爆栈:n 达 10⁵ 且可能是链,要用"从 n 递减到 2"的迭代写法。
⚠️
单状态 DP:必须区分"上方有无黑点"两种情况,否则转移无法表达。
⚠️
答案取错:根上方一定没有黑点,所以答案是 dp[1][0]。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n)
空间复杂度
O(n)
n 最大
10⁵
运算量
约 10⁵

时间怎么算的?

空间都用在哪?

需要存父结点、代价、以及每个结点的 dp 与孩子累加值,共约 6 个 O(n) 数组。

✅ 约 10 万次运算,瞬间完成。本题的难点是"状态设计",不是复杂度。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 树形 DP 的通用套路
// 1. 设计状态:让"子树内的问题"能被独立描述
//    本题:dp[u][0]/dp[u][1] 取决于"上方是否有黑点"
// 2. 找边界:叶子结点
// 3. 写转移:枚举"u 的决策",用孩子的 dp 表达
// 4. 定答案:根结点的某个状态

// 避免递归爆栈的两种写法
// 写法 A(本题,利用 f_i < i):
for (int i = n; i >= 2; i--) { 计算 dp[i]; 累加到 par[i]; }
// 写法 B(一般树):先求拓扑序(BFS/DFS 迭代),再逆序处理
vector<int> order;  // BFS 顺序
for (auto it = order.rbegin(); it != order.rend(); ++it) { 计算 dp[*it]; }

// 如果真要递归,可以手动开大栈(部分评测环境支持):
// #pragma comment(linker, "/STACK:...")
// 但更稳妥的做法就是上面两种迭代写法

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
树形 DP状态 + 边界 + 转移所有树上选择/覆盖类问题
两状态设计"上方有无"决定子问题路径覆盖、支配集、最小点覆盖
逆序迭代利用 f_i < i 保证孩子先算避免 n = 10⁵ 时递归爆栈
🌟
思考题:如果题目改成"每条根到叶的路径上恰好有一个黑点"(恰好而不是至少),DP 要怎么改?(提示:需要第三个状态——记录"这条路径上已经放了几个黑点"(0 个 / 1 个 / ≥2 个)。因为"至少一个"只要两状态就够,而"恰好一个"必须防止放第二个。约束越精确,状态设计就越复杂——这是树形 DP(以及所有 DP)的核心难点。)