树上背包是树形dp的常见模型，通常是分组背包的变形。
引入：二叉苹果树
P2015 二叉苹果树
题意简述：在一个二叉树中，每个边有一个权值。我们要保留\(Q\)条边组成的连通分量（必须包含根节点），求边权和最大值。
我们思考，从节点\(1\)（根节点）开始保留\(Q\)条边，最大答案是什么？
我们分出\(3\)种情况，根节点的答案就是这\(3\)种情况的最大值：
- 保留连接左子结点的边。这种情况下我们消耗\(1\)条边连接左子结点，那么从根节点开始保留\(Q\)条边，就相当于从左子结点开始保留\(Q-1\)条边的答案。
- 保留连接右子节点的边。同上，相当于从右子结点开始保留\(Q-1\)条边的答案。
- 左右都保留。连接左右消耗\(2\)条边，剩下\(Q-2\)条边，我们需要循环枚举分给左边多少，右边多少。
用\(f[i][j]\)表示以\(i\)为根的子树，保留\(j\)条边的最大答案。
实现细节：因为题目输入边的方向不定，所以我们双向存图，并且使用\(vis\)数组。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
struct edge{
int to,w;
};
vector<edge> G[110];
int f[110][110],n,q;
bool vis[110];
void dfs(int pos,int cnt){
if(G[pos].size()==1) return;
int ch[2],w[2],len=0;
//储存左右子节点编号和连接它们的边权
for(auto i:G[pos]){
if(!vis[i.to]){
w[len]=i.w;
ch[len++]=i.to;
}
}
vis[pos]=1;
dfs(ch[0],cnt-1);
dfs(ch[1],cnt-1);
for(int i=1;i<=cnt;i++){
f[pos][i]=max(f[ch[1]][i-1]+w[1],f[ch[0]][i-1]+w[0]);
for(int j=0;j<=i-2;j++){
f[pos][i]=max(f[pos][i],f[ch[0]][j]+w[0]+f[ch[1]][i-j-2]+w[1]);
}
}
vis[pos]=0;
}
int main(){
cin>>n>>q;
for(int i=1;i<n;i++){
int u,v;
edge e;
cin>>u>>v>>e.w;
e.to=v,G[u].emplace_back(e);
e.to=u,G[v].emplace_back(e);
}
dfs(1,q);
cout<<f[1][q];
return 0;
}
例1：选课问题
P2014 [CTSC1997] 选课
题意简述：在大学，有\(N\)门课来学习，每个课程有一个先修课，或者没有（要学习某门课，必须先学习它的先修课）。学一门课可以得到相应的学分。请问学\(M\)门课，最多能得多少学分。
因为给定的图是一片森林，不好操作，我们把所有无先修课的课程，都设置上一个公共的先修课——节点\(0\)。这样变成树后就好操作了。注意相应地，\(M\)需要\(+1\)。
我们再回到这个题，与上一道题最大的不同点就在于——不是二叉树了。
回想上一题，如果是二叉树，我们可以枚举从这一节点开始保留的\(M\)门课，分给左右子结点各多少门。但现在这不是二叉树了，我们该怎么考虑呢？
如上图，\(a,b,c\)的前驱都是\(x\)。我们设正在求从\(x\)开始学习\(q\)门课的最大学分。
我们受上一道题的影响，考虑枚举每个子节点分配多少。
首先根节点必须选，自己用去\(1\)后，子节点还能用\(q-1\)个。
但我们仔细思考，会发现这是一个对\(q-1\)分拆成\(3\)个自然数之和的问题。我们需要枚举每个子节点分配多少。思路以及代码实现都比较复杂。所以我们考虑使用背包。
1.1.1 - 完全背包
受上一题的启发，我们用\(f[x][q]\)表示以\(x\)为根的子树，学\(q\)门课的最大学分。
对于\(x\)的每个子节点，我们可以对其分配\(0,1,2,…,siz\)门课（\(siz\)是该子树的大小）。
不难看出这是一个分组背包问题（物品分组，每组内物品最多选\(1\)个的背包问题，具体见此文）。
背包容量为\(q\)，每个子节点\(i\)都是一组，每组内有\(siz[i]\)个元素，组内第\(k\)个元素重量为\(k\)，价值为\(f[x][k]\)。
注意：根节点\(x\)必须要选，所以搜索之前我们需要赋初值\(f[i][1]=w[i]\)。
虽然我们的状态表示是\(f[i][j]\)，但是\(i\)表示的是根节点编号，和背包没有任何关系，不要被迷惑了。真正起作用的只有\(j\)而已。所以用于背包的其实只有一维，这是一个空间压缩为一维的分组背包。
附上一维分组背包Code：
for(int i=1;i<=s;i++){
for(int k=m;k>=1;k--){
for(int j=1;j<=n[i];j++){
if(k>=w[i][j]) f[k]=max(f[k],f[k-w[i][j]]+v[i][j]);
}
}
}
最终求出的答案是\(f[0][M]\)，注意这里的\(M\)已经加过\(1\)了。
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> G[1010];
int f[1010][1010];
void dfs(int pos){
for(auto i:G[pos]){
dfs(i);
for(int j=m;j>1;j--){
for(int k=1;k<j;k++){
f[pos][j]=max(f[pos][j],f[pos][j-k]+f[i][k]);
}
}
}
}
int main(){
cin>>n>>m;
m++;
for(int i=1;i<=n;i++){
int u;
cin>>u>>f[i][1];
G[u].emplace_back(i);
}
dfs(0);
cout<<f[0][m];
return 0;
}
1.1.2 - 上下界优化
我们发现这份代码只是一个雏形，其实还有许多地方可供优化。首先上文我们提到了边界\(siz\)的问题。故我们用\(siz[i]\)表示以\(i\)为根节点的子树大小，在搜索的同时求出，便可以得到以下优化（建议结合代码理解）：
- 枚举\(k\)（组内元素/给该子节点分配的个数）只需从\(k=\max(1,j-siz[pos]\)开始，枚举到\(k\leq\min(j-1,siz[i])\)即可。
其原因就是：以\(pos\)的子节点\(i\)为根的子树最多只有\(siz[i]\)个节点，超出\(siz[i]\)后的最大权值就，没有遍历的必要性了。 - 相应地，既然超过子树大小就调用不到了，我们还额外求它有什么用呢？
所以，枚举\(j\)（背包大小）只需要从\(j=\min(m,s)\)开始。其中\(s\)表示以\(pos\)为根节点，遍历过的子树大小之和，文字描述比较抽象，可以结合下图和代码理解：
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> G[1010];
int f[1010][1010],siz[1010];
void dfs(int pos){
siz[pos]=1;
for(auto i:G[pos]){
dfs(i);
for(int j=min(m,siz[pos]+siz[i]);j>1;j--){
//j>siz[pos]+siz[i]就没有计算的必要了，
//因为根本调用不到这个值
int lim=min(j-1,siz[i]);
//k之所以要<=siz[i]是因为下面调用了f[i][k]，
//如果k>siz[i]是没有必要遍历的
for(int k=max(1,j-siz[pos]);k<=lim;k++){
//k之所以从j-siz[pos]开始是因为下面调用了f[pos][j-k]，
//而如果j-k>siz[pos]是没有必要遍历的
f[pos][j]=max(f[pos][j],f[pos][j-k]+f[i][k]);
}
}
siz[pos]+=siz[i];
//注意这里siz[pos]是实时累加的
}
}
int main(){
cin>>n>>m;
m++;
for(int i=1;i<=n;i++){
int u;
cin>>u>>f[i][1];
G[u].emplace_back(i);
}
dfs(0);
cout<<f[0][m];
return 0;
}
这个优化十分重要，\(m\leq n\leq 1000\)情况下，可以把时间从100ms左右降到10ms以内。
理解起来可能有一定难度，建议自己造一个样例模拟填表的过程。下图可能会给你帮助：
1.1.3 - 复杂度分析
我们简单分析一下算法的复杂度。
空间的话，就是\(O(nm)\)。
而时间，我们先考虑朴素算法，每个节点都遍历自己的子节点\(1\)遍，共\(n\)；对于每个子节点，枚举背包大小，共\(m\)；对于每个背包大小我们枚举\(k\)，共\(m\)。所以时间复杂度上界是\(O(nm^2)\)。
优化上下界之后，我们可以结合上表进行理解。我们填写的行数的数量级显然是\(n\)，而列的上界是\(m\)。所以优化后的时间复杂度上界是\(O(nm)\)。
U53204 【数据加强版】选课
这道加强版数据范围是\(1\le m\le n\le 10^5\)，\(n*m\le 10^8\)。
因此用这种方法做需要注意用vector，根据\(m\)的大小动态开数组，才不会MLE。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> G[1010],f[1010];
int siz[1010],v[1010];
void dfs(int pos){
f[pos].resize(m+1);
//其实根据上下界优化，有些情况不用开到m
//但是此时该节点的大小还没计算出来
//如果提前计算代码就得翻新了（懒）
f[pos][1]=v[pos];
siz[pos]=1;
for(auto i:G[pos]){
dfs(i);
for(int j=min(m,siz[pos]+siz[i]);j>1;j--){
int lim=min(j-1,siz[i]);
for(int k=max(1,j-siz[pos]);k<=lim;k++){
f[pos][j]=max(f[pos][j],f[pos][j-k]+f[i][k]);
}
}
siz[pos]+=siz[i];
}
}
int main(){
cin>>n>>m;
m++;
for(int i=1;i<=n;i++){
int u;
cin>>u>>v[i];
G[u].emplace_back(i);
}
dfs(0);
cout<<f[0][m];
return 0;
}
1.2.1 - DFS序解法
我们把树上的节点按DFS序编号：
那么，我们用\(f[i][j]\)表示编号为\(1\sim i\)的节点中，选\(j\)个节点，所能获得的最大学分。
用\(awa[i]\)表示DFS序中第\(i\)个是什么。
那么对于\(1\)个点，我们分两种情况讨论：
- 选当前点。那么，该点的子树中，所有点都可以参与考虑。\(f[i][j]=f[i-1][j-1]+v[awa[i]]\)。
- 不选当前点。那么，该点的子树都不能参与考虑。此时需要退回到该节点为根的子树以外。因为是后序遍历，所以节点\(i\)为根的子树前，最晚遍历的点就是\(i-siz[awa[i]]\)。故\(f[i][j]=f[i-siz[awa[i]]][j]\)。
两种情况取最大即可。
时空复杂度显然都是\(O(nm)\)。
实现细节的话，还是请注意vector需要动态开大小。否则会MLE。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,m,v[100010];
vector<int> G[100010],f[100010];
int siz[100010],awa[100010],len;
void dfs(int pos){
siz[pos]=1;
for(auto i:G[pos]){
dfs(i);
siz[pos]+=siz[i];
}
awa[++len]=pos;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int u;
cin>>u>>v[i];
G[u].emplace_back(i);
}
dfs(0);
f[0].resize(m+1);
for(int i=1;i<=n;i++){
f[i].resize(m+1);
for(int j=1;j<=m;j++){
f[i][j]=max(f[i-1][j-1]+v[awa[i]],f[i-siz[awa[i]]][j]);
}
}
cout<<f[n][m];
return 0;
}