树上选点染黑,使每条叶子到根的路径上至少一个黑点,最小化总代价。
给定一棵以 1 为根的有根树,结点初始全白。要把若干结点染黑,使所有叶子到根的路径上至少有一个黑点。结点 i 染黑需代价 cᵢ,求最小总代价。
叶子指没有子结点的结点。
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⁹ |
dp[u][0] = c_u;若上方有黑点 → dp[u][1] = 0dp[u][1] = Σ dp[v][1](上方有黑点,孩子也都"被覆盖");dp[u][0] = min(c_u + Σ dp[v][1], Σ dp[v][0])(要么染 u 自己,要么让每个孩子自己解决)n = 4,f = [1, 2, 3](即 f₂=1、f₃=2、f₄=3),c = [5, 6, 2, 3]。叶子只有结点 4。
dp[4][0] = c₄ = 3(上方没黑点,必须自己染)
dp[4][1] = 0(上方已有黑点,自动覆盖)
dp[4] = (3, 0)
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)
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)
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 ✓
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]。
dp[4] = (4, 0)、dp[5] = (3, 0)
dp[6] = (2, 0)、dp[7] = (1, 0)
四个叶子的状态已定
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)
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
| 结点 | c | dp[·][0] | dp[·][1] | 决策说明 |
|---|---|---|---|---|
| 4(叶) | 4 | 4 | 0 | 必须自己染 |
| 5(叶) | 3 | 3 | 0 | 必须自己染 |
| 6(叶) | 2 | 2 | 0 | 必须自己染 |
| 7(叶) | 1 | 1 | 0 | 必须自己染 |
| 2 | 16 | 7 | 0 | 让孩子 4、5 自己染(4+3=7 < 16) |
| 3 | 15 | 3 | 0 | 让孩子 6、7 自己染(2+1=3 < 15) |
| 1(根) | 64 | 10 | — | 让 2、3 子树自己解决(7+3=10 < 64) |
最优方案:叶子 4、5、6、7 都染黑,总代价 4+3+2+1 = 10 ✓
dp[u][0] 里的 min 正好在这两种策略间取更便宜的那个。自底向上算 dp[u][0] 与 dp[u][1],答案是 dp[1][0]
dp[u][0] 表示"u 上方无黑点"、dp[u][1] 表示"u 上方有黑点"。转移里的 min 恰好对应"在 u 染色"与"让子树自己解决"两种策略的取舍。枚举所有染色方案,检查是否覆盖所有叶子路径
| 方案 | 复杂度 | 可行性 |
|---|---|---|
| 树形 DP | O(n) | ✅ 稳过 |
| 状压枚举 | O(2ⁿ) | ❌ n 大时不可行 |
| 贪心选点 | O(n) | ❌ 无正确性保证 |
第一行输入 n,第二行输入父结点,第三行输入代价,程序会自底向上算 dp。
点按钮开始 →
#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; }
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 的公式 |
int(n × cᵢ 可达 10⁵ × 10⁹ = 10¹⁴);④ 答案错误地取 dp[1][1](根上方没有黑点,应该取 dp[1][0])。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 | 2 | 题面样例 1(一条链,染结点 3) |
7 | 10 | 题面样例 2(四个叶子全染) |
2 | 3 | 一条边:染叶子更便宜 |
2 | 3 | 一条边:染根更便宜 |
3 | 2 | 根贵,两个叶子各染一次 |
dp[1][0]。需要存父结点、代价、以及每个结点的 dp 与孩子累加值,共约 6 个 O(n) 数组。
✅ 约 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⁵ 时递归爆栈 |