福建省网站建设_网站建设公司_Logo设计_seo优化

一、先看原题：

二、题目解析：

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; }

九、一句话总结

🌳这道题的核心就是：
每个节点在想一件事：
“是我自己变黑省钱，
还是让孩子们一起变黑省钱？”