电视台信号覆盖优化：最多用户策略（完整代码PoJ1155）

"PoJ 1155题是一个关于电视台信号传播的问题，它涉及图论和动态规划的运用。题目设定在一个树状网络中，电视台（节点1）作为根，有N个节点，其中1到N-M是中转站，N-M+1到N是用户。节点之间的信号传输需要支付费用，每个用户有一定的付费意愿。目标是在电视台不亏损的前提下，最大化用户观看比赛的数量。 输入包括节点总数N、中转站数量M以及每条边的连接关系和费用。具体来说，前N-M行描述了中转站之间的连接和费用，最后一行是用户愿意支付的费用。输出则是电视台在满足条件下的最大用户接收数。 解题思路是采用树形动态规划。首先，使用`tree`结构体存储节点及其关联信息，`num[i]`表示节点i的子节点数，而`tem[i]`在此问题中可能并不重要。动态规划的状态定义为dp[i][j]，表示以节点i为根，子树包含j个用户时的最大剩余费用。核心递推公式为`dp[i][j]=max(dp[i][j],dp[i][k]+dp[son][j-k]-w[i][son])`，这里`w[i][son]`代表从节点i到其子节点son的费用。 值得注意的是，在计算过程中，由于不同状态之间可能存在依赖，所以需要使用`tem[MAX]`数组预先存储部分状态值，以避免重复计算。同时，由于价值可能为负，所以在初始化dp时应将其设置为负的最大值。 题目还提到了一个外部链接，建议阅读该博客文章，博主通过类比日常生活中的场景（如初中跑圈）来解释复杂概念，使得理解更加生动。最后，博主给出了一个名为`dfs`的深度优先搜索函数，用于处理树的遍历和状态更新。 总结起来，解决此题的关键在于理解树的结构，设计合适的动态规划状态和递推公式，并处理好状态的更新和依赖问题。通过这样的方法，可以在保证电视台不亏损的前提下，最大化用户观看比赛的数量。"