2021 CCPC威海问题：树形DP解决最小割求最大净收益

"最小割问题在2021年CCPC威海H题'city-safety'中的应用，目的是计算最大净收益，即最大收益减去最小花费。问题描述为一棵树，每个节点有加强费用wi，若所有距离某点p不超过p的节点都被加强，则有收益vp。求解方法采用树形动态规划。提供的代码示例展示了如何实现这一算法，但可能难以理解。" 本题主要涉及两个核心概念：最小割模型和树形动态规划。 最小割模型（Minimum Cut Model）是图论中的一个经典问题，它的目标是在图中找到一个割集，使得割集中边的权重之和最小。在这个问题中，最小割模型被用来求解最小花费。最小割的概念可以用来切割图，将一部分节点与其余部分隔离开来，这里的“切割”对应于“加强”，“花费”就是割集中边的权重之和。 树形动态规划（Tree Dynamic Programming）是一种在树结构上进行动态规划的方法，通常用于解决树上的一类问题。在本题中，动态规划的状态可以定义为以某个节点u为根的子树中，选取一部分节点进行加强，使得花费与收益之间的差值最大。状态转移方程通过遍历u的所有子节点v来更新，确保所有距离u小于q的节点都被考虑。 代码中的dfs函数是深度优先搜索的实现，用于进行树形动态规划。它维护了dp[u][i]表示以u为根，且距离u不超过i的节点集合的最大净收益。在遍历子节点v时，更新dp[u]的状态，寻找最佳策略，即将v子树的选择与u子树的选择相结合，以求得最大净收益。 对于n=20的情况，问题规模较小，可以直接用暴力穷举或优化过的动态规划方法求解。在实际比赛中，面对更大的n值，可能需要更高效的算法，如增广路径法、 Ford-Fulkerson算法或Karger's Algorithm等，这些算法能够有效地找到最小割并求解最大净收益。 这道题目考察了选手对图论中的最小割问题的理解以及在树形结构上运用动态规划解决问题的能力。解题的关键在于正确地设计状态和状态转移方程，并能理解提供的代码示例。