: 路径覆盖)
2025年12月GESP(C++六级): 路径覆盖
题目描述
给定一棵有n nn结点的有根树T TT，结点依次以1 , 2 , … , n 1,2,\ldots,n1,2,…,n编号，根结点编号为1 11。方便起见，编号为i ii的结点称为结点i ii。
初始时T TT中的结点均为白色。你需要将T TT中的若干个结点染为黑色，使得所有叶子到根的路径上至少有一个黑色结点。将结点i ii染为黑色需要代价c i c_ici，你需要在满足以上条件的情况下，最小化染色代价之和。
叶子是指T TT中没有子结点的结点。
输入格式
第一行，一个正整数n nn，表示结点数量。
第二行，n − 1 n-1n−1个正整数f 2 , f 3 , … , f n f_2,f_3,\ldots,f_nf2,f3,…,fn，其中f i f_ifi表示结点i ii的父结点的编号，保证f i < i f_i<ifi<i。
第三行，n nn个正整数c 1 , c 2 , … , c n c_1,c_2,\ldots,c_nc1,c2,…,cn，其中c i c_ici表示将结点i ii染为黑色所需的代价。
输出格式
一行，一个整数，表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下，染色代价之和的最小值。
输入输出样例 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 ≤ 16 2\le n\le 162≤n≤16。
对于另外20 % 20\%20%的测试点，保证f i = i − 1 f_i=i-1fi=i−1。
对于所有测试点，保证2 ≤ n ≤ 10 5 2\le n\le 10^52≤n≤105，1 ≤ c i ≤ 10 9 1\le c_i\le 10^91≤ci≤109。
思路分析
这是一个典型的树形DP问题，需要在有根树上选择一些节点染黑，使得：
- 每个叶子节点到根节点的路径上至少有一个黑色节点
- 最小化染色代价之和
关键点理解
- 叶子节点：没有子节点的节点
- 路径要求：每个叶子到根的路径都要被"覆盖"（至少有一个黑点）
- 代价最小化：每个节点染色有不同代价
状态定义
dp[u]：以节点u为根的子树，满足该子树内所有叶子节点到u的路径上至少有一个黑色节点的最小代价。
状态转移
如果u是叶子节点：
- 路径只有u自己，所以必须染色u
dp[u] = c[u]
如果u不是叶子节点：
- 方案一：染黑当前节点u，代价为
c[u]- 染黑u后，所有经过u的路径都满足条件，不需要考虑子树
- 方案二：不染黑当前节点u，代价为所有子节点的
dp[v]之和- 因为u不黑，所以每个子树v必须自己保证覆盖
- 每个子树的dp[v]已经保证了v的子树内叶子到v的路径有黑点
- 由于路径是从叶子到u，且经过v，所以这个黑点也覆盖了到u的路径
dp[u] = min(c[u], Σdp[v])
- 方案一：染黑当前节点u，代价为
代码实现
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;intn;intmain(){cin>>n;vector<int>f(n+1);// f[i]存储节点i的父节点// 输入父节点关系，注意题目保证f_i < ifor(inti=2;i<=n;i++){cin>>f[i];}vector<ll>c(n+1);// c[i]存储染色节点i的代价for(inti=1;i<=n;i++){cin>>c[i];}// 构建树结构：s[p]存储节点p的所有子节点vector<vector<int>>s(n+1);for(inti=2;i<=n;i++){intp=f[i];// 节点i的父节点s[p].push_back(i);// 将i添加到父节点的子节点列表中}// dp[u]表示：以u为根的子树，满足所有叶子到u的路径上至少有一个黑色节点的最小代价vector<ll>dp(n+1);// 从下往上计算（从叶子节点到根节点）// 由于输入保证f_i < i，所以倒序遍历就是从叶子往根for(intu=n;u>=1;u--){// 如果u是叶子节点（没有子节点）if(s[u].empty()){dp[u]=c[u];// 叶子节点必须染色，因为路径上只有它自己}else{// u不是叶子节点ll sum=0;// 计算所有子节点的dp值之和for(intv:s[u]){sum+=dp[v];}// 关键转移方程：// 方案1：染黑当前节点u，代价为c[u]// 方案2：不染黑当前节点，让所有子树自己保证覆盖，代价是子节点dp值之和// 取两者较小值dp[u]=min(c[u],sum);}}// 最终答案是以根节点为根的子树的最小代价cout<<dp[1];return0;}功能分析
1、核心算法
自底向上的树形DP算法
核心思想是：
从叶子节点开始向上计算
每个节点有两种选择：自己染黑，或者让子树各自保证覆盖
取最小代价的方案
2、算法复杂度分析
- 时间复杂度：O(n)
- 构建树结构：O(n)
- DP计算：每个节点和每条边被访问一次，O(n)
- 空间复杂度：O(n)
- 存储树结构：O(n)
- DP数组：O(n)
3、示例验证
示例1
4 1 2 3 5 6 2 3 树结构： 1 │ 2 │ 3 │ 4 计算过程： dp[4] = c[4] = 3 (叶子) dp[3] = min(c[3]=2, dp[4]=3) = 2 dp[2] = min(c[2]=6, dp[3]=2) = 2 dp[1] = min(c[1]=5, dp[2]=2) = 2 输出：2示例2
7 1 1 2 2 3 3 64 16 15 4 3 2 1 树结构： 1 / \ 2 3 / \ / \ 4 5 6 7 计算过程： 叶子节点：dp[4]=4, dp[5]=3, dp[6]=2, dp[7]=1 dp[2] = min(16, 4+3=7) = 7 dp[3] = min(15, 2+1=3) = 3 dp[1] = min(64, 7+3=10) = 10 输出：10各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}- 一、CSP信奥赛C++通关学习视频课：
- C++语法基础
- C++语法进阶
- C++算法
- C++数据结构
- CSP信奥赛数学
- CSP信奥赛STL
- 二、CSP信奥赛C++竞赛拿奖视频课：
- 信奥赛csp-j初赛高频考点解析
- CSP信奥赛C++复赛集训课（12大高频考点专题集训）
- 三、考级、竞赛刷题题单及题解：
- GESP C++考级真题题解
- CSP信奥赛C++初赛及复赛高频考点真题解析
- CSP信奥赛C++一等奖通关刷题题单及题解
详细内容：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
3、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
- 2025 csp-j 复赛真题及答案解析（最新更新）
- 2025 csp-x(山东) 复赛真题及答案解析（最新更新）
- 2025 csp-x(河南) 复赛真题及答案解析（最新更新）
- 2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
- 2025 csp-x(江西) 复赛真题及答案解析（最新更新）
- 2025 csp-x(广西) 复赛真题及答案解析（最新更新）
- 2020 ~ 2024 csp 复赛真题题单及题解
- 2019 ~ 2022 csp-j 初赛高频考点真题分类解析
- 2021 ~ 2024 csp-s 初赛高频考点解析
- 2023 ~ 2024 csp-x (山东)初赛真题及答案解析
- 2024 csp-j 初赛真题及答案解析
- 2025 csp-j 初赛真题及答案解析（最新更新）
- 2025 csp-s 初赛真题及答案解析（最新更新）
- 2025 csp-x (山东)初赛真题及答案解析(最新更新)
- 2025 csp-x (江西)初赛真题及答案解析(最新更新)
- 2025 csp-x (辽宁)初赛真题及答案解析(最新更新)
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
- 129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图
4、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
