树上背包

树上背包问题是树形结构上的一种背包问题，通常涉及在树的节点或边上进行选择，以满足特定的约束条件，同时最大化或最小化某个目标函数（如权值和）。这类问题常见于计算机科学中的图论和动态规划领域。

树上背包是树形 dp 的常见模型，通常是分组背包的变形，而分组背包的本质就是多个泛化物品不断相加。因此掌握泛化物品的合并的方法有助于理解转移的过程。 此类问题一般也可以用 DFS 序、多叉转二叉等方法解决。

解题范式

转分组背包解法

伪代码

泛化物品求并解法

伪代码

例题：二叉苹果树

P2015 二叉苹果树

题意简述：在一个二叉树中，每个边有一个权值。我们要保留 $Q$ 条边组成的连通分量（必须包含根节点），求边权和最大值。

朴素解法：树形 dfs+ 分组背包合并

对于每个节点 $u$，我们用 $f_u[j]$ 表示在以 $u$ 为根的子树中选择 $j$ 条边（含连接边）所能获得的最大权值和。则状态转移方程为：

$$f_u[j]=\underset{1\le k\le j}{\max }\{f_u[j-k]+f_v[k-1]+w(u,v)\}$$

其中 $v$ 是 $u$ 的某个子节点，$w(u,v)$ 是边 $(u,v)$ 的权值。

TC: $O(N\cdot Q^2)$，其中 $N$ 是节点数，$Q$ 是需要选择的边数。 SC: $O(N\cdot Q)$。

代码实现

struct Node {
  int parent;  // -1 表示根节点
  vector<int> sons;
  int value;  // 表示该节点与其父节点之间的边的苹果数
};
 
// ============================================================
// 树形DP + 分组背包解法
// f[u][j] 表示以 u 为根的子树中，保留 j 条边的最大苹果数
// 对于每个子树，将其看作一个物品组，使用分组背包的思路合并
// ============================================================
 
void dfs(int u, const vector<Node>& nodes, int Q, vector<vector<int>>& f) {
  auto& root = nodes[u];
  if (root.sons.empty()) {
    return;
  }
 
  // 对每个子节点，使用分组背包合并
  for (int s : root.sons) {
    dfs(s, nodes, Q, f);  // 先递归处理子树
 
    // 倒序遍历，类似01背包，避免重复使用同一子树
    for (int j = Q; j >= 1; j--) {
      // 枚举分配给子树 s 的边数 j (包括连接边)
      for (int k = 1; k <= j; k++) {
        // f[u][j-k]: 不分配给s或分配较少边的最优状态
        // f[s][k-1]: 子树s内部选k-1条边的最大值
        // nodes[s].value: 连接u到s的边的苹果数
        f[u][j] = max(f[u][j], f[u][j - k] + f[s][k - 1] + nodes[s].value);
      }
    }
  }
}
 
int binaryAppleTree(const vector<Node>& nodes, int Q) {
  // f[u][i] 表示以 u 为根节点的子树中保留 i 条边的最大苹果数
  vector<vector<int>> f(nodes.size(), vector<int>(Q + 1, 0));
 
  // 假定第一个node就是根节点
  dfs(0, nodes, Q, f);
 
  return f[0][Q];
}
 

分组背包（边界优化）

$j$ 和 $k$ 的循环范围可以进行一些优化，最终得到边界优化版本.

代码实现

// ============================================================
// 边界剪枝优化版本
// 通过记录每个子树的边数上限，避免无效枚举，减少DP状态转移次数
// 返回以 u 为根的子树中的边数上限
// ============================================================
 
int dfs_optimized(int u, const vector<Node>& nodes, int Q, vector<vector<int>>& f) {
  auto& root = nodes[u];
  if (root.sons.empty()) {
    return 0;  // 叶子节点，子树内没有边
  }
 
  int maxEdges = 0;  // 记录以u为根的子树中的边数上限
 
  // 对每个子节点，使用分组背包合并
  for (int s : root.sons) {
    int subTreeEdges = dfs_optimized(s, nodes, Q, f);  // 先递归处理子树，获取子树边数
    int limit = subTreeEdges + 1;                      // 子树s最多可以提供 subTreeEdges+1 条边（包括连接边）
    maxEdges += limit;                                 // 累计总边数
 
    // 倒序遍历，类似01背包，避免重复使用同一子树
    for (int j = min(Q, maxEdges); j >= 1; j--) {
      // 枚举分配给子树 s 的边数 k (包括连接边)
      // 优化：k 最多为 min(j, limit)，避免无效枚举
      for (int k = 1; k <= min(j, limit); k++) {
        // f[u][j-k]: 不分配给s或分配较少边的最优状态
        // f[s][k-1]: 子树s内部选k-1条边的最大值
        // nodes[s].value: 连接u到s的边的苹果数
        f[u][j] = max(f[u][j], f[u][j - k] + f[s][k - 1] + nodes[s].value);
      }
    }
  }
 
  return maxEdges;  // 返回子树的边数上限
}
 
int binaryAppleTree_optimized(const vector<Node>& nodes, int Q) {
  // f[u][i] 表示以 u 为根节点的子树中保留 i 条边的最大苹果数
  vector<vector<int>> f(nodes.size(), vector<int>(Q + 1, 0));
 
  // 假定第一个node就是根节点
  dfs_optimized(0, nodes, Q, f);
 
  return f[0][Q];
}

注意：该方法的 TC 为 $O(N\cdot Q)$ 而不是 $O(N\cdot Q^2)$，其中 $N$ 是节点数，$Q$ 是需要选择的边数。具体证明过程可参考 2.1.2 复杂度分析

Seealso

更详细的解析过程见 2.1 分组背包

泛化物品求并

来源： 徐持衡 - 国家集训队2009论文集 浅谈几类背包题 。

树形dp -（树上背包类） 中列出了树上背包问题的基础解法和几种优化解法，其中泛化物品求并解法是几种高效的优化解法中实现较为简单（但同样需要理解成本）的一种解法，值得重点掌握。

区别与分组背包的 dp 定义，泛化物品求并解法的 dp 定义为：$f_u[j]$ 表示从已遍历的子节点中选择 $j$ 条边且必选节点 u所能获得的最大权值和。在此题中，选择节点 u 表示选择连接 u 与其父节点的边。

Note

注意这里是“泛化物品求并”解法，而不是单纯的“泛化物品”解法，因为上述分组背包的解法本质也是泛化物品的思想。要使用泛化物品求并解法，必须精心设计 dp 的定义，使得 dp 状态能够满足“可并”的性质。更多参考 2.4 泛化物品求并解法。

代码实现

 
// ============================================================
// 泛化物品求并解法
// f[u][j] 表示从已遍历节点中选择，边数不超过j且必选u边（节点u与其父节点的边）的最大苹果数
// v 表示已经使用的边数（从根到u的路径上的边数）
// TC: O(N*Q)
//   - 每个节点 u 执行两次循环，范围都是 [depth[u]+1, Q]，每次迭代 (Q-depth[u]) 次
//   - 总循环次数 = Σ(u∈tree) 2*(Q-depth[u]) = 2*(N*Q - Σdepth[u])
//   - 对于任意树形，Σdepth[u] < N*Q，因此 TC = O(N*Q)
//   - 相比分组背包的 O(N*Q²)，避免了双重枚举，实现了算法级别的优化
// SC: O(N*Q)
// ============================================================
 
void dfs_union(int u, const vector<Node>& nodes, int Q, int v, vector<vector<int>>& f) {
  if (v > Q) {
    return;  // 剪枝：已用边数超过限制, 余下的点可以认为是死区，永远不会到达
  }
 
  for (int s : nodes[u].sons) {
    // 1. 第一次遍历到节点 s, 更新 f[s]
    for (int j = v + 1; j <= Q; j++) {
      f[s][j] = f[u][j - 1] + nodes[s].value;
    }
 
    // 2. 递归 s 子树
    dfs_union(s, nodes, Q, v + 1, f);
 
    // 3. 递归完 s 子树，f[s] 已经完备，但此时遍历的点集已经变化，f[u] 还需要更新
    // 此时 f[u][j] 表示的是在当前已遍历点中选 u节点与其父节点的边（后续简称选u边）且不选 s 边（因为前面还没遍历到
    // s，所以f[u] 不包含 s 边）的答案
    // f[s][j] 表示在当前已遍历点中选 s边 且共选 j 条边的最大边权和
    // 因为选 s边 必选 u边，所以 f[s][j] 就是选 u边 且 s 边的答案，正好和 f[u][j] 互补
    for (int j = v + 1; j <= Q; j++) {
      f[u][j] = max(f[u][j], f[s][j]);
    }
  }
}
 
int binaryAppleTree_union(const vector<Node>& nodes, int Q) {
  vector<vector<int>> f(nodes.size(), vector<int>(Q + 1, 0));
 
  dfs_union(0, nodes, Q, 0, f);
 
  return f[0][Q];
}

Note

理解这个解法的核心是要理解 $f[u][j]$ 的含义, 这个解法里 $f[u][j]$ 表示遍历到当前节点 u 时选节点 u 以及从其他已遍历的节点中选 j-1 个节点的解. 这里有几点需要注意:

• dfs 遍历是个有来有回的过程, 最开始从虚拟根节点出发, 来来回回逐个子节点 dfs 遍历,最后回到虚拟根节点, 因此当前已遍历节点这个集合是不断在变化的, 所以 $f[u][j]$ 也需要不断更新, 不可能一次遍历就完成所有的更新.
• 选的节点都是真节点, 不包括虚拟根节点 (因为 dep 从 0 开始)
• j -1 个节点中一定包含虚拟根节点到 u 的路径上的节点 (不然也遍历不到 u)

回到 dfs(u, dep) 的过程, 当循环到其子节点 s 时,

• f[s][j] = f[u][j - 1] + v[s]; 的含义是: 遍历 s 节点, 设当前已遍历节点集合为 $N_u$, 则 $f[s][j]$ 表示接下来遍历到 s, 选 s 及从 $N_u$ 中选 $j-1$ 个节点的解, 注意从虚拟根节点到 s 路径上的点 (包含 u) 是在这 j-1 个节点中的, 剩下的节点则是从 N_u 中 u 的其他已遍历的子树中的节点选的.
• dfs(s, dep + 1); 递归遍历 s 子树,直至遍历完其所有子节点,最后回到 u. 经过这一步后, 已遍历的点集为 $N_u\cup N_s^{\prime }$, 其中 $N_s^{\prime }$ 是 s 子树所有点 (含 s), 此时 $N_s^{\prime }$ 中的点对应的 f 是已经更新好的状态, 符合其定义.
• f[u][j] = max(f[u][j], f[s][j]); 因为前面遍历了 s 子树的所有节点 $N_s^{\prime }$ ,已遍历的点集变为 $N_u\cup N_s^{\prime }$, 而 $f[u][j]$ 的状态还停留在已遍历点集为 $N_u$ 的状态, 所以需要更新 $f[u][j]$ 的状态, 因为如果不选 s, 则 s 子树所有的点也不能选, 因此现在的 $f[u][j]$ 可以认为是从已遍历的点集 $N_u\cup N_s^{\prime }$ 中选 u 不选 s 共选 j 个节点的解, 而 $f[s][j]$ 则是从已遍历的点集 $N_u\cup N_s^{\prime }$ 中选 u 选 s 共选 j 个节点的解, 两种情况不可能同时发生, 只能取其一, 因此 $max(f[u][j],f[s][j])$ 便是从已遍历的点集 $N_u\cup N_s^{\prime }$ 中选 u 共选 j 个节点的解, 符合定义, 即 $f[u][j]$ 的状态得到了更新.
• 至此完成了对子节点 s 的处理, 回到 u, 继续处理 u 的其他子节点, 等处理完所有子节点, $f[u][j]$ 的含义就变成了从已遍历的点集 $N_u\cup N_u^{\prime }$ 中选 u 共选 j 个节点的解, 特别的,当节点 u 为虚拟根节点时, $f[u][j]$ 最后的含义就是从所有真节点 (不含虚拟节点) 中选 j 个节点的解, 也就是最终的答案.

Note

可以看出，带上下边界优化的分组背包解法和泛化物品求并解法的时间复杂度都是 $O(N\cdot Q)$，但泛化物品求并解法的实现更为简洁，且避免了双重枚举，效率更高一些。因此在实际应用中，推荐优先考虑使用泛化物品求并解法来解决树上背包问题。 但从实现难道和理解难度上来看，带上下边界优化的分组背包解法更容易被理解和实现。因此在学习阶段，可以先掌握带上下边界优化的分组背包解法，理解其原理后，再学习泛化物品求并解法，以便更好地理解树上背包问题的本质。

例题：选课

P2014 [CTSC1997] 选课

题意简述：在大学，有 $N$ 门课来学习，每个课程有一个先修课，或者没有（要学习某门课，必须先学习它的先修课）。学一门课可以得到相应的学分。请问学 $M$ 门课，最多能得多少学分。

典型的树上背包问题，这里就仅列两种解法。

分组背包（边界优化）

DP 定义： $dp[u][j]$ 表示在以节点 $u$ 为根的子树中选择 $j$ 个节点（包含节点 $u$）所能获得的最大学分和。

代码实现（核心 dfs）

// u - 当前节点
int dfs2(int u, int M, const vector<Node>& nodes, vector<vector<int>>& dp) {
  int nu = 1;
 
  // 先将当前节点放入背包
  dp[u][1] = nodes[u].score;
 
  for (int s : nodes[u].sons) {
    int ns = dfs2(s, M, nodes, dp);  // 先遍历子节点树, 确保 dp[s] ready
 
    // 优化边界, 让 1<=j-k<=nu, 1<=k<=ns, j<= nu+ns 且 j <= M
    for (int j = min(nu + ns, M); j > 1; --j) {  // 这里必须倒序, 因为是0-1背包
      int lim = min(ns, j - 1);
      for (int k = max(1, j - nu); k <= lim; ++k) {
        dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[s][k]);
      }
    }
    nu += ns;
  }
  return nu;  // 返回当前树的节点数
}
 

泛化物品求并

DP 定义： $dp[u][j]$ 表示从已遍历的子节点中选择 $j$ 个节点且必选节点 u所能获得的最大学分和。在此题中，选择节点 u 表示选择课程 u。

代码实现（核心 dfs）

// dep 表示从虚拟根节点到当前节点的路径上真实课程的数量
void dfs5(int u, int M, int dep, const vector<Node>& nodes, vector<vector<int>>& dp) {
  for (int s : nodes[u].sons) {
    // 遍历子节点 s
    for (int j = dep + 1; j <= M; ++j) {
      dp[s][j] = dp[u][j - 1] + nodes[s].score;
    }
 
    // 递归遍历 s 子树的所有节点
    dfs5(s, M, dep + 1, nodes, dp);
 
    // 此时 dp[s] 表示选s及u的方案, dp[u] 表示选u不选s的方案,两者仅可取其一
    for (int j = dep + 1; j <= M; ++j) {
      dp[u][j] = max(dp[u][j], dp[s][j]);
    }
  }
}

例题：有线电视网

P1273 有线电视网

给定一个树形结构。其中根节点是足球比赛的现场，叶子节点是用户终端，其他节点就是转播站。每条边都有一个边权，表示信号传递的消费。每个叶子都有一个点权，表示每个用户准备的钱数。

请问在不亏本的情况下，最多能让多少用户看到比赛？ （注意不是让赚的钱最多）

分组背包

代码实现

struct Node {
  int parent;  // -1 表示本节点为根节点
  vector<int> sons;
  int cost;   // 父节点到本节点的边值, 根节点该值为 0
  int money;  // 叶子节点为可获取的费用，中转节点该值为0
};
// 输入的 vector<Node>: 第1个是根节点，中间 N-M-1 个节点为中转节点，末尾的 M 个为叶子节点，
 
// 方法1: 分组背包
// f[u][j] 表示以 u 为根节点让 j 个终端（叶子节点）看上比赛的最大收益
 
void dfs1(int u, const vector<Node>& nodes, int M, vector<vector<int>>& f) {
  if (nodes[u].sons.empty()) {
    // 叶子节点（用户）：选0个用户收益0，选1个用户收益为money
    f[u][1] = nodes[u].money;
    return;
  }
 
  for (int s : nodes[u].sons) {
    dfs1(s, nodes, M, f);
    // 倒序遍历，避免重复使用同一子树
    for (int j = M; j >= 1; j--) {
      // 枚举分配给子树s的用户数k
      for (int k = 1; k <= j; k++) {
        // f[u][j-k]: 从其他已处理子树选j-k个用户的收益
        // f[s][k]: 从子树s选k个用户的收益
        // nodes[s].cost: 传输到子树s的成本
        f[u][j] = max(f[u][j], f[u][j - k] + f[s][k] - nodes[s].cost);
      }
    }
  }
}
 
int solution1(const vector<Node>& nodes, int M) {
  int N = nodes.size();
  // 初始化为极小值，注意不要用INT_MIN避免溢出
  const int NEG_INF = -0x3f3f3f3f;
  vector<vector<int>> f(N, vector<int>(M + 1, NEG_INF));
  for (int i = 0; i < N; i++) {
    f[i][0] = 0;
  }
  dfs1(0, nodes, M, f);
 
  // 找出使 f[0][j] >= 0 的最大 j
  for (int j = M; j >= 0; j--) {
    if (f[0][j] >= 0) {
      return j;
    }
  }
  return 0;
}

分组背包（边界优化）

代码实现（核心 dfs）

// 方法2: 分组背包(边界优化)
// 关于这里 j 和 k 的边界优化：
// 核心是为让转移方程中的 j, j-k, k 三个变量的边界进行优化
// 0<=j-k<=lim_u; j-k 表示从已处理子树中选的用户数, 不能超过已处理子树的用户数 lim_u
// 1<=k<=lim_s; k 表示从子树 s 中选的用户数, 不能超过子树 s 的用户数 lim_s
// 1<=j<=min(lim_u+lim_s,M); j 表示总共选的用户数, 不能超过已处理子树和子树 s 的用户数之和, 且不能超过 M
 
int dfs2(int u, const vector<Node>& nodes, int M, vector<vector<int>>& f) {
  if (nodes[u].sons.empty()) {
    // 叶子节点（用户）：选0个用户收益0，选1个用户收益为money
    f[u][1] = nodes[u].money;
    return 1;
  }
 
  int lim_u = 0;  // 已处理子树中叶子节点的数量上限
  for (int s : nodes[u].sons) {
    int lim_s = dfs2(s, nodes, M, f);
    // 倒序遍历，避免重复使用同一子树
    for (int j = min(M, lim_u + lim_s); j >= 1; j--) {
      // 枚举分配给子树s的用户数k
      for (int k = max(1, j - lim_u); k <= min(j, lim_s); k++) {
        // f[u][j-k]: 从其他已处理子树选j-k个用户的收益
        // f[s][k]: 从子树s选k个用户的收益
        // nodes[s].cost: 传输到子树s的成本
        f[u][j] = max(f[u][j], f[u][j - k] + f[s][k] - nodes[s].cost);
      }
    }
    lim_u += lim_s;  // 此处再更新已处理子树的叶子节点数量上限
  }
  return lim_u;
}

分组背包（边界优化 + 空间优化）

代码实现

// 方法3: 分组背包（边界优化 + 空间优化）
// 在方法2的基础上进行空间优化：
// - 不再为每个节点维护 f[u][j]，而是只在递归中传递一维数组 g[j]
// - 每个子树用临时数组 g_s 表示，然后与父节点的 g 合并
// 空间复杂度从 O(N×M) 降到 O(M×树高)
 
int dfs3(int u, const vector<Node>& nodes, int M, vector<int>& g) {
  if (nodes[u].sons.empty()) {
    g[1] = nodes[u].money;
    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 = dfs3(s, nodes, M, g_s);
 
    // 将子树 s 的结果合并到当前节点
    // g[j]: 从已处理子树中选 j 个用户的最大收益
    // g_s[k]: 从子树 s 中选 k 个用户的最大收益
    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] - nodes[s].cost);
      }
    }
    lim_u += lim_s;
  }
  return lim_u;
}
 
int solution3(const vector<Node>& nodes, int M) {
  const int NEG_INF = -0x3f3f3f3f;
  vector<int> g(M + 1, NEG_INF);
  g[0] = 0;
  dfs3(0, nodes, M, g);
 
  for (int j = M; j >= 0; j--) {
    if (g[j] >= 0) {
      return j;
    }
  }
  return 0;
}

更多相关例题