树上背包
二叉苹果树·选课
本课摘要
树上背包课程回答“树上选取数量约束如何在子树间做背包合并”。内容以二叉苹果树·选课为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。
- 判断树上背包的适用条件与状态边界
- 围绕“二叉苹果树·选课”推导转移与计算顺序
- 用演示、复杂度分析和配套题目校验实现
本课目录 · 0 节
正在整理目录…
当「选子必先选父」遇上容量限制
上一类的 只问「选不选」。但很多问题还带一个预算：一棵长满苹果的树， 只能保留 条树枝，且——要留一条枝，它上面那截主干必须先留住（否则这条枝就从树上掉了）。 在预算 下让保留的苹果最多，这是树上背包。
「容量受限的取舍」正是背包的本行，但这里多了一层依赖：孩子想被选中，得先为「连接它的那条边」付出一份容量。 于是每个点的状态要带上容量维：
读作 = 在 u 的子树里恰好保留 j 条边时的最大苹果数。答案在 。
把孩子当成一「组」物品
怎么合并？关键一步：把每个孩子子树看成分组背包里的一「组」。给孩子 分配 条边（）， 意味着——先用掉 1 条去接通「u 到 c 的边」（拿到它的边权），再把剩下 条留给 c 的子树内部去最优，即 。
于是父亲对每个孩子做一次分组背包合并（ 倒序，避免一组被算两次）：
这里 是 u 到孩子 c 的边权。注意 从 1 起步——要碰孩子子树里任何一条边，就必须先付这条连边，这就是依赖被自然编码进转移的方式。
本质
树上背包 = 子树维背包 + 依赖。「选子必选连父的边」不是额外判断，而是把 的下界设成 1、并把边权算进那一步——依赖就免费融进了分组背包的转移里。复杂度是每个点 ，全树合起来 （经典的「树上背包是平方」结论）。
跟着算一遍
小树：根 ，两个孩子 （连边苹果 2）、（连边苹果 5）； 再带两片叶 （连边 3）、（连边 4）。保留 条边：
每个节点一张小背包表
依赖成森林：接一个虚根
再看「选课」： 门课，有的课要先修另一门才能选；没有先修课的课可以直接选。选 门，最大化学分。 「先修」关系画出来是一片森林（多棵依赖树），不是单棵树——DFS 从哪开始？
技巧极简：造一个虚根 ，把每棵树的树根都挂到它下面。森林瞬间变成一棵以 为根的树，前面那套树上背包直接套用。 只是要记得——选 门真课，等价于在含虚根的树里选 个点（虚根白占一个名额），最后读 。
常见陷阱：虚根的「+1」不能漏
接虚根后，容量要留给虚根那一门。转移时 上界写 、每个点的 先塞自己（占 1 门），答案读 。漏掉这个 +1，会把真课数当成点数，答案系统性偏小一门。
例题
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 105;
struct E { int to, w; };
vector<E> g[N]; // 邻接表带边权（苹果数）
int f[N][N]; // f[u][j]：u 子树里保留 j 条边的最大苹果数
int sz[N]; // sz[u]：u 子树内的边数（dp 第二维上界）
int Q;
void dfs(int u, int fa)
{
for (E e : g[u])
{
if (e.to == fa) continue;
dfs(e.to, u);
sz[u] += sz[e.to] + 1; // 加上「连孩子的边」和孩子子树里的边
for (int j = min(sz[u], Q); j >= 1; j--) // ★分组背包：容量倒序
for (int t = 1; t <= sz[e.to] + 1 && t <= j; t++) // 给这个孩子分 t 条边
f[u][j] = max(f[u][j], f[u][j - t] + f[e.to][t - 1] + e.w);
}
}
int main()
{
int n;
cin >> n >> Q;
for (int i = 1; i < n; i++)
{
int a, b, w;
cin >> a >> b >> w;
g[a].push_back({b, w});
g[b].push_back({a, w}); // 无向，dfs 里用 fa 挡回边
}
dfs(1, 0);
cout << f[1][Q] << endl;
return 0;
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 305;
vector<int> g[N]; // g[u]：以 u 为先修课的那些课
int s[N]; // s[i]：第 i 门课的学分
int f[N][N]; // f[u][j]：在 u 子树里选 j 门课的最大学分
int m;
void dfs(int u)
{
f[u][1] = s[u]; // 选了 u 子树里的课，必先选 u 自己（占 1 门）
for (int v : g[u])
{
dfs(v);
for (int j = m + 1; j >= 2; j--) // ★+1：0 号虚根也算一门，容量留够
for (int k = 1; k <= j - 1; k++) // 给孩子 v 这一组分 k 门
f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
}
}
int main()
{
int n;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
int fa;
cin >> fa >> s[i];
g[fa].push_back(i); // fa == 0 表示无先修课，挂到虚根 0 下
}
dfs(0); // ★森林接一个虚根 0，问题化为一棵树
cout << f[0][m + 1] << endl; // 选 m 门真课 + 虚根 1 门 = m+1
return 0;
}