P14919 [GESP202512 六级] 路径覆盖
题目描述
给定一棵有nnn结点的有根树TTT，结点依次以1,2,…,n1,2,\ldots,n1,2,…,n编号，根结点编号为111。方便起见，编号为iii的结点称为结点iii。
初始时TTT中的结点均为白色。你需要将TTT中的若干个结点染为黑色，使得所有叶子到根的路径上至少有一个黑色结点。将结点iii染为黑色需要代价cic_ici，你需要在满足以上条件的情况下，最小化染色代价之和。
叶子是指TTT中没有子结点的结点。
输入格式
第一行，一个正整数nnn，表示结点数量。
第二行，n−1n-1n−1个正整数f2,f3,…,fnf_2,f_3,\ldots,f_nf2,f3,…,fn，其中fif_ifi表示结点iii的父结点的编号，保证fi<if_i<ifi<i。
第三行，nnn个正整数c1,c2,…,cnc_1,c_2,\ldots,c_nc1,c2,…,cn，其中cic_ici表示将结点iii染为黑色所需的代价。
输出格式
一行，一个整数，表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下，染色代价之和的最小值。
输入输出样例 #1
输入 #1
4 1 2 3 5 6 2 3输出 #1
2输入输出样例 #2
输入 #2
7 1 1 2 2 3 3 64 16 15 4 3 2 1输出 #2
10说明/提示
对于40%40\%40%的测试点，保证2≤n≤162\le n\le 162≤n≤16。
对于另外20%20\%20%的测试点，保证fi=i−1f_i=i-1fi=i−1。
对于所有测试点，保证2≤n≤1052\le n\le 10^52≤n≤105，1≤ci≤1091\le c_i\le 10^91≤ci≤109。
题解：路径覆盖（GESP202512 六级）
题目分析
你需要解决的问题是：给定一棵以1为根的树，将若干节点染黑，使得所有叶子到根的路径上至少有一个黑点，且染色总代价最小。这是典型的树形动态规划（树形DP）问题，核心是通过后序遍历树，从叶子节点向上推导每个子树的最小覆盖代价。
解题思路
- DP状态定义：
dp[i]表示以节点i为根的子树，满足“所有叶子到i的路径至少有一个黑点”的最小染色代价。 - 遍历方式：由于题目中父节点编号一定小于子节点（
f_i < i），因此从n到1逆序遍历，等价于从叶子节点到根节点的后序遍历，能保证处理父节点时所有子节点已处理完毕。 - 状态转移：
- 若
i是叶子节点（无任何子节点）：必须将i染黑，因此dp[i] = c[i]。 - 若
i是非叶子节点：有两种选择——
✅ 选择自己染黑：代价为c[i]；
✅ 选择子节点的覆盖代价之和：代价为所有子节点dp值的总和；
取两种选择的最小值作为dp[i]。
- 若
- 最终答案：根节点
1的dp[1]即为整棵树的最小覆盖代价。
#include<bits/stdc++.h>usingnamespacestd;intn;// 树的节点总数intf[100005];// f[i] 存储节点i的父节点编号（i≥2）intc[100005];// c[i] 存储将节点i染黑的代价longlongdp[100005];// dp[i]：以i为根的子树的最小覆盖代价（用long long避免溢出，c[i]可达1e9，n可达1e5）intmain(){// 输入节点总数cin>>n;// 输入2~n号节点的父节点（题目保证f[i]<i）for(inti=2;i<=n;i++){cin>>f[i];}// 输入每个节点的染色代价for(inti=1;i<=n;i++){cin>>c[i];}// 逆序遍历（从n到1）：等价于从叶子到根的后序遍历for(inti=n;i>=1;i--){// 状态转移核心：// 1. 叶子节点：dp[i]初始为0，会被赋值为c[i]（必须自己染黑）// 2. 非叶子节点：比较「子节点代价和」与「自己染黑代价」，取更小值if(dp[i]==0||dp[i]>c[i]){dp[i]=c[i];}// 将当前节点的最小代价累加到父节点的dp中（父节点的初始代价是所有子节点代价的和）// 注意：根节点1没有父节点，f[1]无意义，但i=1时执行此语句不影响（数组越界？不，f数组仅2~n有值，f[1]未初始化，但i=1时dp[f[1]]不会被后续使用）dp[f[i]]+=dp[i];}// 根节点1的dp值即为整棵树的最小覆盖代价cout<<dp[1];return0;}复杂度分析
- 时间复杂度：
O(n)，仅需遍历节点1~n各一次，所有操作均为常数级。 - 空间复杂度：
O(n)，主要消耗在存储父节点、代价、DP数组的数组空间，能满足n≤1e5的数据规模。
总结
- 本题核心是树形DP，利用“父节点编号小于子节点”的特性，通过逆序遍历实现从叶子到根的后序遍历。
dp[i]的状态转移逻辑是：取“自己染黑的代价”和“所有子节点覆盖代价之和”的最小值。- 最终根节点的
dp[1]即为满足条件的最小总代价，算法时间/空间效率均能适配题目数据范围。
