A91493.有线电视网 解题思路

问题分析

这是一道树形动态规划问题。给定一棵以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（传输费用）。采用分组背包的方式进行合并：

// 合并子节点 v 到当前节点 u
for (int i = cnt[u]; i >= 0; i--) {     // 当前已选用户数（逆序）
    for (int j = 0; j <= cnt[v]; j++) { // 从子节点选 j 个
        dp[u][i + j] = max(dp[u][i + j], dp[u][i] + dp[v][j] - 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) 的大小