2025年12月GESP(C++六级): 路径覆盖

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问题，需要在有根树上选择一些节点染黑，使得：

1. 每个叶子节点到根节点的路径上至少有一个黑色节点
2. 最小化染色代价之和

关键点理解

• 叶子节点：没有子节点的节点
• 路径要求：每个叶子到根的路径都要被"覆盖"（至少有一个黑点）
• 代价最小化：每个节点染色有不同代价

状态定义

dp[u]：以节点u为根的子树，满足该子树内所有叶子节点到u的路径上至少有一个黑色节点的最小代价。

状态转移

1. 如果u是叶子节点：

   • 路径只有u自己，所以必须染色u
   • dp[u] = c[u]

2. 如果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])

代码实现

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