记录134#includebits/stdc.h // 引入C万能头文件包含vector等常用标准库 using namespace std; // 使用标准命名空间std #define ll long long // 定义长整型别名ll因为代价c[i]最大为1e9累加容易溢出int const int N 1e5 10; // 定义常量N表示结点数量的最大范围 int n; // 定义全局变量n表示结点的总数 vectorint g[N]; // 定义邻接表gg[u]存储结点u的所有子结点 ll c[N]; // 定义数组cc[i]表示将结点i染为黑色所需的代价 ll dp[N]; // 定义dp数组dp[i]表示以i为根的子树满足条件的最小代价 // 定义深度优先搜索函数u表示当前正在处理的结点 void dfs(int u){ ll sum0; // 定义变量sum用来累加当前结点所有子结点的dp值 bool is_leaftrue; // 定义布尔变量is_leaf标记当前结点是否为叶子结点 for(int v:g[u]){ // 遍历当前结点u的所有子结点v is_leaffalse; // 只要有子结点就说明u不是叶子结点 dfs(v); // 递归处理子结点v自底向上计算子结点的dp值 sumdp[v]; // 将子结点v的最小代价累加到sum中 } if(is_leaf){ // 如果当前结点u是叶子结点 dp[u]c[u]; // 叶子结点必须自己染色否则它到自己的路径就没有黑点 } else { // 如果当前结点u不是叶子结点 // 状态转移取“自己染黑”和“子结点们自己解决”两者中的较小值 dp[u]min(c[u], sum); } } int main(){ // 主函数入口 ios::sync_with_stdio(false); // 关闭标准流同步提升输入输出效率 cin.tie(0); // 解除cin与cout的绑定加快读取速度 cinn; // 读入结点的数量n // 循环读入n-1个父结点信息并建立邻接表 for(int i2;in;i){ int f; // 定义临时变量f表示结点i的父结点 cinf; // 读入结点i的父结点编号 g[f].push_back(i); // 在邻接表中将i加入f的子结点列表 } // 循环读入n个结点的染色代价 for(int i1;in;i){ cinc[i]; // 读入结点i的染色代价 } dfs(1); // 从根结点1开始进行DFS计算整棵树的最小代价 coutdp[1]\n; // 输出以根结点1为根的子树的最小代价即最终答案 return 0; // 程序正常结束 }题目传送门https://www.luogu.com.cn/problem/P14919前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道经典的树形动态规划Tree DP问题。问题转化题目要求所有叶子结点到根结点的路径上至少有一个黑色结点。我们可以将这个问题分解到每一棵子树中去解决。对于任意一个结点u要满足它子树内所有叶子到根的路径合法只有两种最优的决策方案方案一结点u自己染成黑色。如果u是黑色的那么从u的子树中任意叶子向上走到u时路径上就已经有了黑色结点。此时u的子结点们无需再为了“向上覆盖”而承担额外代价它们只需要各自管好自己的子树即可。方案二结点u保持白色。如果u不染黑那么为了覆盖u的子树中所有叶子的路径u的所有子结点v必须各自独立地满足条件即v的子树内的叶子到v的路径必须有黑点。状态定义与转移定义dp[u]为使得以u为根的子树中所有叶子到u的路径上至少有一个黑色结点的最小代价。如果u是叶子结点它必须自己染黑dp[u] c[u]。如果u不是叶子结点取上述两种方案的最小值即dp[u] min(c[u], sum(dp[v]))其中sum(dp[v])是u所有子结点v的dp值之和。代码分块详细解释1. 头文件、常量与全局变量定义#includebits/stdc.h using namespace std; #define ll long long // 定义长整型别名 ll因为代价 c[i] 最大为 1e9累加容易溢出 int const int N 1e5 10; // 定义常量 N表示结点数量的最大范围 int n; // 定义全局变量 n表示结点的总数 vectorint g[N]; // 定义邻接表 gg[u] 存储结点 u 的所有子结点 ll c[N]; // 定义数组 cc[i] 表示将结点 i 染为黑色所需的代价 ll dp[N]; // 定义 dp 数组dp[i] 表示以 i 为根的子树满足条件的最小代价详细分析由于染色代价c_i最大可达 10^9在极端情况下累加可能会超出int的范围因此c数组和dp数组必须使用long long类型。vectorint g[N]用于存储树的子结点关系因为题目保证了父结点编号小于子结点f_i i这实际上已经给出了一种拓扑序但使用 DFS 递归处理更加直观。2. 深度优先搜索DFS与状态转移// 定义深度优先搜索函数u 表示当前正在处理的结点 void dfs(int u){ ll sum 0; // 定义变量 sum用来累加当前结点所有子结点的 dp 值 bool is_leaf true; // 定义布尔变量 is_leaf标记当前结点是否为叶子结点 for(int v : g[u]){ // 遍历当前结点 u 的所有子结点 v is_leaf false; // 只要有子结点就说明 u 不是叶子结点 dfs(v); // 递归处理子结点 v自底向上计算子结点的 dp 值 sum dp[v]; // 将子结点 v 的最小代价累加到 sum 中 } if(is_leaf){ // 如果当前结点 u 是叶子结点 dp[u] c[u]; // 叶子结点必须自己染色否则它到自己的路径就没有黑点 } else { // 如果当前结点 u 不是叶子结点 // 状态转移取“自己染黑”和“子结点们自己解决”两者中的较小值 dp[u] min(c[u], sum); } }详细分析这是树形 DP 的核心。自底向上计算通过dfs(v)先递归处理完所有子结点拿到子结点的最优解dp[v]。叶子结点处理如果u是叶子它没有任何子结点可以分担“覆盖路径”的责任所以dp[u]只能等于它自身的染色代价c[u]。非叶子结点贪心如果u不是叶子我们面临抉择。要么花费c[u]染黑自己一劳永逸地覆盖所有子树路径要么自己不染把压力下放让所有子结点各自承担自己的子树代价即sum。取两者较小值即为dp[u]的最优解。3. 主函数建图与初始化int main(){ ios::sync_with_stdio(false); // 关闭标准流同步提升输入输出效率 cin.tie(0); // 解除 cin 与 cout 的绑定加快读取速度 cin n; // 读入结点的数量 n // 循环读入 n-1 个父结点信息并建立邻接表 for(int i 2; i n; i){ int f; // 定义临时变量 f表示结点 i 的父结点 cin f; // 读入结点 i 的父结点编号 g[f].push_back(i); // 在邻接表中将 i 加入 f 的子结点列表 } // 循环读入 n 个结点的染色代价 for(int i 1; i n; i){ cin c[i]; // 读入结点 i 的染色代价 }详细分析题目给出的输入是f_2, f_3, ..., f_n即每个结点的父结点。我们在读入时直接将其转化为子结点列表g[f].push_back(i)从而构建出一棵以 1 为根的有向树。4. 启动 DP 与输出结果dfs(1); // 从根结点 1 开始进行 DFS计算整棵树的最小代价 cout dp[1] \n; // 输出以根结点 1 为根的子树的最小代价即最终答案 return 0; // 程序正常结束 }详细分析调用dfs(1)从整棵树的根结点开始递归。当递归返回时dp[1]中存储的就是使得整棵树以 1 为根所有叶子到根的路径上都有黑色结点的最小总代价。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点数据类型#define ll long long使用 64 位长整型防止 105 个结点、每个代价 10^9 累加时发生数据溢出树的存储g[f].push_back(i)建立父到子的有向边将输入的父结点数组转化为便于 DFS 遍历的邻接表叶子判断bool is_leaf标记当前结点是否有子结点区分基础状态叶子必须染和递推状态非叶子做抉择状态转移dp[u] min(c[u], sum)树形 DP 核心贪心公式在“自己承担代价”与“下放代价给子结点”之间做出最优选择自底向上dfs(v); sum dp[v]先递归子结点再合并确保在计算父结点最优解时所有子结点的最优解已经计算完毕