Sean's Blog

可压缩空间的树上背包问题

10分钟阅读

可压缩空间的树上背包问题

概述

树上背包问题通常需要 O(N × M) 的空间复杂度来存储所有节点的 DP 状态。但在大多数情况下，我们可以通过递归时使用临时数组的方式，将空间复杂度优化到 O(M × 树高)。

核心思想

标准实现（需要 O(N×M) 空间）

// 为所有节点预分配 DP 数组
vector<vector<int>> f(N, vector<int>(M + 1, NEG_INF));
 
int dfs(int u, ...) {
    if (叶子节点) {
        f[u][1] = value[u];
        return 1;
    }
 
    for (int s : sons[u]) {
        dfs(s, ...);
        // 使用 f[u] 和 f[s] 进行转移
        for (int j = ...; j >= 1; j--) {
            for (int k = ...; k <= ...; k++) {
                f[u][j] = max(f[u][j], f[u][j-k] + f[s][k] - cost);
            }
        }
    }
}

空间复杂度：O(N × M)

  • 需要为每个节点都分配一个大小为 M+1 的数组
  • 即使子树处理完毕，其 DP 数组也会一直占用内存

空间优化实现（只需 O(M×树高) 空间）

int dfs(int u, ..., vector<int>& g) {
    if (叶子节点) {
        g[1] = value[u];
        return 1;
    }
 
    int lim_u = 0;
    for (int s : sons[u]) {
        // 为子树 s 创建临时数组
        vector<int> g_s(M + 1, NEG_INF);
        g_s[0] = 0;
 
        int lim_s = dfs(s, ..., g_s);  // 递归处理子树
 
        // 将子树 s 的结果合并到当前节点 g
        for (int j = min(M, lim_u + lim_s); j >= 1; j--) {
            for (int k = max(1, j - lim_u); k <= min(j, lim_s); k++) {
                g[j] = max(g[j], g[j-k] + g_s[k] - cost);
            }
        }
 
        lim_u += lim_s;
        // g_s 在这里被销毁，释放内存！
    }
    return lim_u;
}

空间复杂度：O(M × 树高)

  • 递归栈上同时存在的数组数量 = 树的高度
  • 每层递归只需要一个大小为 M+1 的临时数组
  • 子树处理完后，临时数组立即销毁

关键理解

为什么可以这样优化？

  1. 子树独立性：每个子树的 DP 状态只在合并到父节点时使用一次
  2. 单向信息流：信息只从子节点流向父节点（自底向上）
  3. 合并即完成：子树状态合并到父节点后，不再需要访问原始状态

空间优化的本质

标准方法：f[0], f[1], ..., f[N-1] 全部分配并保留
          ↓
优化方法：只在递归栈上保留 "当前路径" 上的节点数组
          根 → ... → 当前节点 → 子节点 → ...
          只有这条路径上的节点才有 DP 数组

适用场景

✅ 可以使用空间优化的情况

必须满足所有条件：

  1. 自底向上合并

    • 从叶子节点向根节点递归
    • 每个节点只依赖直接子节点的状态

  2. 子树独立

    • 子树之间的 DP 状态不相互依赖
    • 处理完一个子树后，可以将其结果 ” 合并 ” 到父节点

  3. 不需要回溯方案

    • 只求最优值，不需要输出具体选择
    • 如需输出方案，必须保留完整 DP 数组

  4. 标准树结构

    • 每个节点只有一个父节点
    • 不是 DAG（有向无环图）

典型例题：

  • ✅ 有线电视网（P1273）
  • ✅ 选课（P2014）
  • ✅ 树的重心
  • ✅ 树上最大独立集

❌ 不能使用空间优化的情况

  1. 需要输出方案

    // 需要回溯路径，必须保留所有节点的 DP 数组
void backtrack(int u, int m) {
    // 需要访问 f[u][m] 和 f[s][k]
    if (f[u][m] == f[u][m-k] + f[s][k] - cost) {
        // 选择了子节点 s 的 k 个...
    }
}

  2. 换根 DP（两次 DFS）

    // 第一次 DFS：自底向上
dfs1(root);  // 计算每个节点为根的子树答案
 
// 第二次 DFS：自顶向下
dfs2(root);  // 需要使用第一次的结果！

  3. DAG 上的背包

    • 节点有多个父节点
    • 需要记忆化搜索，保留所有状态

  4. 需要访问兄弟/祖先节点状态

    f[u][j] = max(f[brother][k], f[ancestor][m], ...)

性能对比

以 P1273 有线电视网 为例：

方法时间复杂度空间复杂度Case 9 耗时
分组背包（无优化）O(N×M²)O(N×M)0.496ms
分组背包（边界优化）O(N×M×平均子树大小)O(N×M)0.018ms
分组背包（边界 + 空间优化）O(N×M×平均子树大小)O(M×树高)0.014ms ⭐

优势：

  • 空间减少：从 O(N×M) 到 O(M×树高)
  • 性能提升：临时数组的局部性更好，缓存命中率更高
  • 可处理更大规模：空间限制更宽松

实现模板

模板代码

// 方法：分组背包（边界+空间优化）
// 空间复杂度：O(M × 树高)
 
int dfs(int u, const vector<Node>& nodes, int M, vector<int>& g) {
    // 叶子节点：初始化基础状态
    if (nodes[u].sons.empty()) {
        g[1] = nodes[u].value;
        return 1;
    }
 
    int lim_u = 0;  // 已处理子树的总物品数
 
    // 处理每个子树
    for (int s : nodes[u].sons) {
        // 为子树创建临时数组
        const int NEG_INF = -0x3f3f3f3f;
        vector<int> g_s(M + 1, NEG_INF);
        g_s[0] = 0;
 
        // 递归处理子树
        int lim_s = dfs(s, nodes, M, g_s);
 
        // 分组背包：合并子树 s 到当前节点 u
        for (int j = min(M, lim_u + lim_s); j >= 1; j--) {
            for (int k = max(1, j - lim_u); k <= min(j, lim_s); k++) {
                // g[j-k]: 从已处理子树选 j-k 个的最大价值
                // g_s[k]: 从子树 s 选 k 个的最大价值
                // cost: 选择子树 s 的额外代价
                g[j] = max(g[j], g[j-k] + g_s[k] - nodes[s].cost);
            }
        }
 
        lim_u += lim_s;
        // 离开作用域，g_s 被自动销毁
    }
 
    return lim_u;
}
 
// 主函数调用
int solve(const vector<Node>& nodes, int M) {
    const int NEG_INF = -0x3f3f3f3f;
    vector<int> g(M + 1, NEG_INF);
    g[0] = 0;
 
    dfs(0, nodes, M, g);
 
    // 找出最优解
    for (int j = M; j >= 0; j--) {
        if (g[j] >= 0) return j;
    }
    return 0;
}

边界优化说明

// 外层循环 j：总共选择的物品数
for (int j = min(M, lim_u + lim_s); j >= 1; j--) {
    //          ^^^^^^^^^^^^^^^^
    // 不超过背包容量 M
    // 不超过当前可选的总物品数
 
    // 内层循环 k：从子树 s 选择的物品数
    for (int k = max(1, j - lim_u); k <= min(j, lim_s); k++) {
        //       ^^^^^^^^^^^^^^^         ^^^^^^^^^^^^^^
        //       下界：至少选 1 个         上界：不超过 j
        //       保证 j-k <= lim_u       不超过子树 s 的物品数

边界优化的意义：

  • 避免无效状态的计算
  • 在大规模数据下性能提升显著（快 20-30 倍）

注意事项

1. 初始化

// ❌ 错误：每次都重新初始化整个数组
for (int s : sons) {
    vector<int> g_s(M + 1, NEG_INF);
    for (int i = 0; i <= M; i++) g_s[i] = NEG_INF;  // 多余
    g_s[0] = 0;
}
 
// ✅ 正确：构造时已经初始化
for (int s : sons) {
    vector<int> g_s(M + 1, NEG_INF);  // 已经全部初始化为 NEG_INF
    g_s[0] = 0;  // 只需要特殊处理 0
}

2. NEG_INF 的选择

// ❌ 危险：可能溢出
const int NEG_INF = INT_MIN;
f[j] = max(f[j], f[j-k] + f[s][k] - cost);
//                ^^^^^^^^^^^^^^^^ 可能溢出
 
// ✅ 安全：留有余地
const int NEG_INF = -0x3f3f3f3f;  // 约 -10^9

3. 倒序遍历

// 必须倒序遍历 j，避免重复使用同一子树
for (int j = min(M, lim_u + lim_s); j >= 1; j--) {  // 倒序
    for (int k = ...; k <= ...; k++) {
        g[j] = max(g[j], g[j-k] + ...);
        //                ^^^^^
        //                访问的是"旧值"（未被当前子树更新）
    }
}

总结

何时使用空间优化？

决策流程：

是否需要输出方案？
├─ 是 → 不能用，需要保留完整 DP 数组
└─ 否 → 继续判断
    │
    是否是标准树形DP（自底向上，子树独立）？
    ├─ 是 → ✅ 可以用空间优化
    └─ 否 → 继续判断
        │
        是否是换根DP、DAG等特殊情况？
        ├─ 是 → ❌ 不能用
        └─ 否 → ✅ 可以用

优化效果

  • 空间：O(N×M) → O(M×树高)，节省 N/树高 倍空间
  • 时间：可能略有提升（缓存局部性更好）
  • 适用率：约 70-80% 的树形背包问题都可以用

推荐策略

  • 竞赛/刷题：只求最优值时，优先使用空间优化版本
  • 工程/实际应用：需要输出方案时，使用标准版本
  • 学习/理解：先掌握标准版本，再学习空间优化

相关链接

参考题目

  1. P1273 有线电视网 ⭐⭐⭐
  2. P2014 选课 ⭐⭐
  3. 树的重心问题
  4. 树上最大独立集

目录

关系图谱