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）问题，核心是通过后序遍历树，从叶子节点向上推导每个子树的最小覆盖代价。

解题思路

1. DP状态定义：dp[i]表示以节点i为根的子树，满足“所有叶子到i的路径至少有一个黑点”的最小染色代价。
2. 遍历方式：由于题目中父节点编号一定小于子节点（f_i < i），因此从n到1逆序遍历，等价于从叶子节点到根节点的后序遍历，能保证处理父节点时所有子节点已处理完毕。
3. 状态转移：
   • 若i是叶子节点（无任何子节点）：必须将i染黑，因此dp[i] = c[i]。
   • 若i是非叶子节点：有两种选择——
     ✅ 选择自己染黑：代价为c[i]；
     ✅ 选择子节点的覆盖代价之和：代价为所有子节点dp值的总和；
     取两种选择的最小值作为dp[i]。
4. 最终答案：根节点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的数据规模。

总结

1. 本题核心是树形DP，利用“父节点编号小于子节点”的特性，通过逆序遍历实现从叶子到根的后序遍历。
2. dp[i]的状态转移逻辑是：取“自己染黑的代价”和“所有子节点覆盖代价之和”的最小值。
3. 最终根节点的dp[1]即为满足条件的最小总代价，算法时间/空间效率均能适配题目数据范围。