树上的背包问题，也就是背包问题与树形 DP 的结合。
例题：P2014 [CTSC1997] 选课
有 \(n\) 门课程，第 \(i\) 门课程的学分为 \(a_i\)，每门课程有零门或一门先修课，有先修课的课程需要先学完其先修课，才能学习该课程。一位学生要学习 \(m\) 门课程，求其能获得的最多学分数。
数据范围：\(n,m \le 300\)
由于每门课最多只有一门先修课，与有根树中一个点最多只有一个父亲节点的特点类似。可以利用这个性质来建树，从而所有课程形成了一个森林结构。为了方便起见，可以新增一门 \(0\) 学分的课程（编号为 \(0\)），作为所有无先修课课程的先修课，这样原本的森林就变成了一棵以 \(0\) 号节点为根的树。
设 \(dp_{u,i,j}\) 表示以 \(u\) 为根的子树中，已经遍历了 \(u\) 号点的前 \(i\) 棵子树，选了 \(j\) 门课程的最大学分。
转移的过程结合了树形 DP 和背包问题的特点，枚举点 \(u\) 的每个子节点 \(v\)，同时枚举以 \(v\) 为根的子树选了几门课程，将子树的结果合并到 \(u\) 上。
将点 \(x\) 的子节点个数记为 \(s_x\)，以 \(x\) 为根的子树大小为 \(sz_x\)，则有状态转移方程：\(dp_{u,i,j} = \max \{ dp_{u,i-1,j-k} + dp_{v,s_v,k} \}\)，注意有一些状态是无效的，比如 \(k>j\) 或是 \(k>sz_v\) 时。
第二维可以通过滚动数组优化掉，此时需要倒序枚举 \(j\) 的值，同 0-1 背包问题。
该做法的时间复杂度为 \(O(nm)\)，证明见 子树合并背包类型的dp的复杂度证明。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 305;
vector<int> tree[N];
int s[N], dp[N][N], n, m;
int dfs(int u) {
int sz_u = 1;
dp[u][1] = s[u];
for (int v : tree[u]) {
int sz_v = dfs(v);
for (int i = min(sz_u, m + 1); i > 0; i--)
for (int j = 1; j <= sz_v && i + j <= m + 1; j++)
dp[u][i + j] = max(dp[u][i + j], dp[u][i] + dp[v][j]);
sz_u += sz_v;
}
return sz_u;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
int k;
scanf("%d%d", &k, &s[i]);
tree[k].push_back(i);
}
dfs(0);
printf("%d\n", dp[0][m + 1]);
return 0;
}
习题：P3177 [HAOI2015] 树上染色
解题思路
显然设 \(dp_{u,i}\) 代表以 \(u\) 为根节点的子树，将其中 \(i\) 个点染成黑色的状态。
但是这个值存什么呢？如果直接表示子树内黑点、白点间的收益，这个状态没有办法转移，因为子树内最大化收益的染色方案被合并上去后未必是最优的方案，也就是有后效性。
考虑每条边对最终答案的贡献，如果一条边的两侧有一对黑点或白点，则这条边对这两个点构成的路径是有贡献的。也就是说，一条边对总答案的贡献次数等于边的两侧同色点个数的乘积。而子树内每条边对总答案的贡献这个状态值在子树合并过程中是可以向上传递的。
因此 \(dp_{u,i}\) 代表以 \(u\) 为根节点的子树中有 \(i\) 个点被染成黑色后子树内每一条边对总答案的贡献，类似树上背包，当要合并某个子节点 \(v\) 对应的子树时，枚举子树中的黑点数量 \(j\)，则对应的转移为 \(dp_{u,i-j} + dp_{v,j} + w(u,v) \times c(u,v)\)，其中 \(w(u,v)\) 代表边权，\(c(u,v)\) 代表 u-v 这条边对总答案的贡献，而 \(c(u,v) = j \times (k - j) + (sz_v - j) \times (n - sz_v - (k - j))\)。
参考代码
#include <cstdio>
#include <utility>
#include <vector>
#include <algorithm>
using std::pair;
using std::vector;
using std::min;
using std::max;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2005;
int n, k;
vector<PII> tree[N];
LL dp[N][N]; // dp[u][i] u的子树内染i个黑点时边对答案的总贡献
int dfs(int u, int fa) {
int sz_u = 1;
for (PII p : tree[u]) {
int v = p.first, w = p.second;
if (v == fa) continue;
int sz_v = dfs(v, u);
for (int i = min(k, sz_u); i >= 0; i--) {
for (int j = 1; j <= sz_v && i + j <= k; j++) {
LL black = 1ll * w * j * (k - j);
LL white = 1ll * w * (sz_v - j) * (n - sz_v - (k - j));
dp[u][i + j] = max(dp[u][i + j], dp[u][i] + dp[v][j] + black + white);
}
// 若将j=0放在循环中，则会立马更新dp[u][i]
// 导致接下来计算dp[u][i+j]时用到的dp[u][i]已经不是之前的值了
LL white = 1ll * w * sz_v * (n - sz_v - k);
dp[u][i] += dp[v][0] + white;
}
sz_u += sz_v;
}
return sz_u;
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = 1; i < n; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
tree[u].push_back({v, w}); tree[v].push_back({u, w});
}
dfs(1, 0);
printf("%lld\n", dp[1][k]);
return 0;
}