一、先看原题：
二、题目解析：
1、先把题目“翻译成白话”
📘 原题意思（白话版）
有一棵树🌳：
有n 个节点
有一个根节点
每个节点一开始都是白色
现在你要做一件事：
👉把一些节点染成黑色（要花钱）
规则是：
从任意一个叶子节点走到根节点的那条路上，至少要有 1 个黑色节点
每个节点染黑：
都有一个花费 💰
目标是：
🎯在满足规则的前提下，让总花费最小
2、什么是“叶子到根的路径”？
🌳 举个小树例子
1 / \ 2 3 / 4根：1
叶子：3、4
🛣 路径有哪些？
4 → 2 → 1
3 → 1
👉每一条路径上，都要至少有 1 个黑点
3、最关键的一句“算法思想”
对每一个节点，我们只关心：
是“自己染黑便宜”，还是“让孩子们自己解决更便宜”。
这就是这题的核心！
4、一步一步拆解思路（非常重要）
🔍 从哪开始想？
👉从叶子开始
① 如果我是叶子节点
我的后面没有节点
那我的选择是：先要染黑自己
✅ 花费 =c[i]
② 如果我不是叶子节点
假设我有孩子 👶👶
每个孩子都会算出：
“为了保证下面路径安全，最少要花多少钱”
现在我有两个选择：
✨ 选择 1：我自己染黑
花费 =
c[i]所有孩子路径都安全了
✨ 选择 2：我不染
那就每个孩子自己保证
花费 = 所有孩子的最小花费之和
👉我选更便宜的那个！
六、这其实就是：树形 DP
形象比喻 👇
每个节点都会交一张“最省钱报告单”给爸爸
爸爸看看：
自己掏钱便宜
还是孩子们一起掏钱便宜
七、结合样例走一遍（非常关键）
📌 样例 1
4 1 2 3 5 6 2 3解释：
父节点关系：
2 的父亲是 1
3 的父亲是 2
4 的父亲是 3
形成一条链
1 | 2 | 3 | 4花费：
1: 5
2: 6
3: 2
4: 3
🧠 从叶子往上算
节点 4（叶子）
必须染
花费 = 3
节点 3
自己染：2
让 4 解决：3
👉 选 2
节点 2
自己染：6
让 3 解决：2
👉 选 2
节点 1
自己染：5
让 2 解决：2
👉 选 2
✅ 最终答案：2
八、参考程序（详细注释）
#include <iostream> using namespace std; const int N = 100005; int n; int parent[N]; // parent[i]：i 的父节点 int cost[N]; // cost[i]：把 i 染黑要花多少钱 int childCnt[N]; // childCnt[i]：i 有几个孩子 long long dp[N]; // dp[i]：保证“从 i 往下的路径”安全的最小花费 int main() { cin >> n; // 读父节点信息 for (int i = 2; i <= n; i++) { cin >> parent[i]; childCnt[parent[i]]++; // 统计孩子数量 } // 读染色花费 for (int i = 1; i <= n; i++) { cin >> cost[i]; } // 从编号大的往小算（孩子先算，爸爸后算） for (int i = n; i >= 1; i--) { // 如果是叶子节点 if (childCnt[i] == 0) { dp[i] = cost[i]; // 只能自己染 } // 不管是不是叶子，都可以选择自己染 dp[i] = min(dp[i], (long long)cost[i]); // 把自己的最小花费加给爸爸 if (i != 1) { dp[parent[i]] += dp[i]; } } // 根节点的答案 cout << dp[1] << endl; return 0; }九、一句话总结
🌳这道题的核心就是：
每个节点在想一件事：
“是我自己变黑省钱，
还是让孩子们一起变黑省钱？”
