问题分析 这是一道树形动态规划问题。给定一棵以1为根的树，叶子节点是用户终端，每个用户终端有支付费用，每条边有传输费用。需要选择一部分叶子节点（用户），使得选中的用户支付总费用 ≥ 传输总费用，且选中的用户数最多。 状态定义 定义 dp[u][j] 表示：以节点 u 为根的子树中，恰好选择 j 个用户终端时，能够获得的最大净收益（用户支付费用 - 传输费用）。 * 净收益 ≥ 0 表示不亏本 * 我们最终要找最大的 j，使得 dp[1][j] ≥ 0 初始化： * 对于叶子节点（用户终端）：dp[u][1] = pay[u]（选择该用户，净收益为支付费用） * 对于叶子节点：dp[u][0] = 0（不选择任何用户） * 对于非叶子节点：初始化为 -INF 状态转移 对于节点 u，假设它有子节点 v，边权为 w（传输费用）。采用分组背包的方式进行合并： 其中： * cnt[u] 表示以 u 为根的子树中用户终端的数量 * dp[u][i] 在更新前表示已处理部分子树的状态 * 从子节点 v 转移时，需要扣除边权 w 转移含义： 从 u 的已处理子树中选 i 个用户，从子节点 v 的子树中选 j 个用户，总净收益为两部分之和减去连接边 v 的传输费用。 最终答案 遍历所有可能的 j 从 M 到 0，找到第一个满足 dp[1][j] ≥ 0 的 j，即为答案。 复杂度分析 * 时间复杂度：树形背包的复杂度为 O(N * M)，因为每个节点对合并时，总的枚举次数为 O(子树大小^2)，整体为 O(N * M) * 空间复杂度：O(N * M) 注意事项 1. 逆序更新：合并子节点时，为了避免同一子节点被重复使用，需要倒序遍历当前已选用户数 2. INF 处理：使用一个足够小的负数表示不可达状态，避免无效状态参与转移 3. 内存优化：N ≤ 3000，M ≤ 3000，二维数组 dp[3001][3001] 约 900 万，使用 int 大约 36MB，可以接受。也可以用 vector 动态分配，只分配 (cnt[u] + 1) 的大小