树形背包算是这个背包九讲的最后几篇之一了，它的定义是：
有N个物品和一个容量为C的背包，物品编号为0...N-1。物品之间有依赖关系，该依赖关系为树形结构，当你选择某个物品时，必须也该物品的父节点。第i件物品体积为vi，价值为wi，其父节点的编号为pi，其中根节点的编号为-1。
树形背包的组织形式
先来看看这道题给的数据，他给的是每个子节点的父结点编号，是由下而上的结构，而如果我们需要使用DP来解决问题的话，需要由上而下构建一颗多叉树。
这时候我们可以使用之前在字典树中使用过的构建方法，链式向前星存图：
*// 链式向前星存图*
void add(int a, int b) {
e[idx] = b;
ne[idx] = he[a];
he[a] = idx++;
}这种链式向前星的数组写法其实并不是特别的直观，最好还是用结构体来实现。
经典的树形背包问题
分组背包思维
这题属于有依赖的背包问题，通常我们可以将这类树形背包问题看作是有依赖的分组背包。如果一个根结点有N个子节点，那么我们可以从任意一个子结点中选取占用k容量的的最大价值。对比分组背包的解决步骤，N个子节点对应N个分组，K容量对应决策，这样我们可以得到下面这个递推式：
对于这里dp的定义让我觉得有点不明白：
dp[u][j]为考虑以u为根的子树，背包容量不超过j的最大价值。问题在于，对于dpu(j-k)来说，这样它的涵义就是以u为根的子树，背包容量不超过j-k的最大价值。但是在实际代码中，你需要遍历j和k时，你无法直接获得dp[u][j-k]的最终值。而每一次迭代，其实都应该类比于分组背包中的前i个组中以u为根，容量不超过j的最大价值。
而上面的定义我觉得无法消除这个问题的后效性。
不过如果将i那一维优化掉的话，这个递推式应该是正确的。换而言之，对于这个问题而言上述的表达式中dpu(j-k)应该表达的是前i-1个u的子节点中容量不超过j-k的最大价值。
先贴一段三叶的代码，树形背包这个问题，肯定还有需要更多的讨论才能深刻理解。
code
class Solution {
int N = 110, M = N * 2;
int[] he = new int[N], e = new int[M], ne = new int[M];
int[] vi, wi;
int n, c, idx;
// 定义 f[u][j] 为考虑以 u 为根的子树，背包容量不超过 j 的最大价值
int[][] f = new int[N][N];
// 链式向前星存图
void add(int a, int b) {
e[idx] = b;
ne[idx] = he[a];
he[a] = idx;
idx++;
}
void dfs(int u) {
// 节点 u 的价值和体积
int cw = wi[u], cv = vi[u];
// 要选任一节点，必须先选 u，同时也限制了至少需要 cv 的容量
for (int i = cv; i <= c; i++) f[u][i] += cw;
// 遍历节点 u 的所有子节点 x（分组背包遍历物品组）
for (int i = he[u]; i != -1; i = ne[i]) {
int x = e[i];
// 递归处理节点 x
dfs(x);
// 从大到小遍历背包容量（分组背包遍历容量）
for (int j = c; j >= 0; j--) {
// 遍历给节点 x 分配多少背包容量（分组背包遍历决策）
for (int k = 0; k <= j - cv; k++) {
f[u][j] = Math.max(f[u][j], f[u][j - k] + f[x][k]);
}
}
}
}
public int maxValue(int N, int C, int[] p, int[] v, int[] w) {
n = N; c = C;
vi = v; wi = w;
Arrays.fill(he, -1);
int root = -1;
for (int i = 0; i < n; i++) {
if (p[i] == -1) {
root = i;
} else {
add(p[i], i);
}
}
dfs(root);
return f[root][c];
}
}下面来考虑一下这一道题：
这道题算是上面那题的简化版，所以我试着自己写了一下，发现果然还是有很多细节处理不好。例如链式向前星的写法我就没理解清楚，对循环条件不确定。事实上这种写法确实略带了一点trick，当我使用纯数组存图的时候he[a]中的值第一次为初始值，也是这一条链的末端点，而最后一次对该根节点add的时候he[a]将会保存这条链的起点。所以当我们遍历的时候起点应该为he[a]，终止条件则为he[a]中的初始值。
其次关于dp数组的初始化，在这个题中我们只需要针对只取一门课时的数组初始化为这门课的权重即可。
code
#include<bits/stdc++.h>
using namespace std;
const int n1 = 310;
vector<int>he(n1,-1),e(n1),ne(n1);
int idx = 0;
int dp[n1][n1];
int n , m;
vector<int>ki;
vector<int>si;
//struct edge
//{
// int to,pre;
//}e[n1];
void add(int a, int b){
e[idx] = b;
ne[idx] = he[a];
he[a] = idx++;
}
//void add(int a, int b){
// e[++idx].pre = he[a];
// e[idx].to = b;
// he[a] = idx;
//}
void dfs(int u){
for(int i = he[u]; i!= -1 ; i = ne[i]){
int x = e[i];
dfs(x);
// for(int i = he[u] ; i ; i = e[i].pre){
// dfs(e[i].to);
for(int j = m+1 ; j > 0 ; j --){
for(int k = j-1 ; k >= 0 ; k --){
dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[x][k]);
}
}
}
}
int main(void){
cin>>n>>m;
for(int i = 1 ; i <= n ; i ++){
int k , s;
cin>>k>>s;
dp[i][1] = s;
add(k,i);
}
dfs(0);
cout<<dp[0][m+1];
return 0;
}接下来是这道题：
首先这道题，显然是可以用上面的方式去做的，几乎就是一摸一样的套模板就可以了：
code
#include<bits/stdc++.h>
using namespace std;
int n , c;
const int MAXN = 33000;
int wi[61],vi[61];
int he[61],e[61],ne[61];
int dp[61][MAXN];
int cnt = 0;
void add(int from,int to){
e[cnt] = to;
ne[cnt] = he[from];
he[from] = cnt++;
}
void dfs(int u){
for(int i = wi[u] ; i <= c ; i ++){
dp[u][i] += vi[u]*wi[u];
}
for(int i = he[u]; i!=-1 ; i = ne[i]){
int x = e[i];
dfs(x);
for(int j = c ; j >= 0 ; j --){
for(int k = 0 ; k <= j-wi[u];k++){
dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[x][k]);
}
}
}
}
int main(void){
cin>>c>>n;
memset(he,-1,sizeof(he));
for(int i = 1 ; i <= n ; i ++){
int k;
cin>>wi[i]>>vi[i]>>k;
add(k,i);
}
dfs(0);
cout<<dp[0][c];
return 0;
}但是这道题的c为3.2*10^4，而上面解法的时间复杂度是，这样的做法会TLE。
而我们可以注意到，题目描述中还有给出几个关键数据并没有被使用，显然在符合某些条件的时候树形DP是可以做优化的。
注意本题中的容量维度很大，但是相对物品数量只有60，同时每件物品最多只有两个附件。
看到这里，我想起了我开头那一段——想法 ，是否可以直接对每个物品及附件进行拆分，然后使用分组背包求解呢？由于每个物品最多只有两个附件，所以我们最多只需要枚举三个物品状态。
这样问题就彻底转化成了分组背包问题。但是这种优化是有条件的，首先问题中明确说明了附件不会再有附件，所以这颗树只有三层（包括根节点），如果附件还能有附件的话，我不清楚是否能用其他方法进行优化。
实现上我们首先需要对主附结点进行预处理，存放在一个map<int,list>里，然后对这个map进行物品的划分，最后进行分组背包DP就可以了。
code
#include<bits/stdc++.h>
using namespace std;
int wi[61],vi[61],ki[61];
int n,c;
int dp[32000];
int solution(){
unordered_map<int,vector<int>> map;
for(int i = 1 ; i <= n ; i ++){
if(map.count(ki[i]) == 0){
map[i] = vector<int>();
}else{
if(map.count(ki[i]) == 0)
map[ki[i]] = vector<int>();
map[ki[i]].emplace_back(i);
}
}
vector<vector<pair<int,int>>> list;
for(auto it:map){
vector<pair<int,int>> temp;
int rootv = wi[it.first];int rootw = wi[it.first]*vi[it.first];
temp.emplace_back(make_pair(rootv,rootw));
vector<int>sub = it.second;
for(int i = 0 ; i < sub.size(); i ++){
int x = sub[i];
int xv = wi[x];int xw = vi[x]*wi[x];
temp.emplace_back(make_pair(rootv+xv,rootw+xw));
for(int j = i+1 ; j <sub.size() ; j ++){
int y = sub[j];
int yv = wi[y];int yw = wi[y]*vi[y];
temp.emplace_back(make_pair(rootv+yv+xv,rootw+yw+xw));
}
}
list.emplace_back(temp);
}
for(int i = 0 ; i < list.size() ; i ++){
vector<pair<int,int>> temp = list[i];
for(int j = c ; j >= 0 ; j --){
for(int k = 0 ; k <temp.size() ; k++){
if(temp[k].first<=j)dp[j] = max(dp[j],dp[j-temp[k].first]+temp[k].second);
}
}
}
return dp[c];
}
int main(void){
cin>>c>>n;
for(int i = 1 ; i <= n ; i ++){
cin>>wi[i]>>vi[i]>>ki[i];
}
cout<<solution();
return 0;
}准确来说，这种解法和我最上面的思路不一样，按那种解法来说应当是将n个点全部划分为状态，并且直接对这些状态进行01背包，好像也不能直接01背包，需要在dp的时候还需要用一个map存已经拿取了的状态，针对每个物品存入前都进行查询如果已经存在就跳过，未存入就递归存入。
这样的话可能复杂度能变成一个带常数的N*C?好像算上递归的话应该是N*C*N反正我也懒得写了，感觉很麻烦。不过这个思路给我带来的一点点想法可能就是，树形背包问题应该最少能优化到N*C*N级别，可能能到N*C。这里有个简单的说明——说明
最后总结一下这种类分组背包思路的树形背包问题把，通过上面几道题，可以体会到。树形背包的问题其实并不是一个特别复杂或者全新类型的背包问题，解法大致能从前面的背包类型找到思路。难点在于对于初始状态的划分，这种森林图，如果没有选择好的状态进行划分，很容易造成TLE。而选择一个好的状态划分，往往能大幅度提升运行速度。
对于上面的这一类朴素的树形背包问题来说，一般直接从已有维度上进行划分，例如我们知道根节点是由所有子树的状态组合更新而来的，这时候我们可以对所有子树状态组合，进行状态划分。从而找到一个更优的更新方式。
而最后一题的优化解法，则是利用了树的层级只有3层这一点，直接将二维树形背包（三层还要除去根节点相当于两层）转化为了一个一维的分组背包问题。从而避免了使用通用的树形背包解法的复杂度。
泛型背包的并优化
首先泛化背包的定义是这样的：
考虑这样一种物品，它并没有固定的费用（体积）和价值，而是它的价值随着你分配给它的费用（体积）变化而变化。
其实就是说将DP过程中的一些状态当成一个物品来看待，这种方式来看树形背包问题的话，其实就是将合并的两颗子树当成两个泛型背包，而将两颗子树的合并看作两个泛化物品的合并。每一次泛化物品合并的复杂度是，总共n个结点，这样复杂度就是
但是引入泛型背包这个概念的原因是能以一个更加理想的方式去划分状态。在前面的朴素写法中，对于我们都是通过合并所有的子节点然后更新根节点，但是那个写法中更新所有的子节点需要C^2的复杂度，那么有没有一种划分方法可以将这个复杂度变成C呢？
考虑将dpij定义为所有已经选择过的结点中选取j个结点，并且一定包含i结点的答案。这时候两棵子树可以被定义为dp[u][j]、dp[v][j]，合并时当前根节点dp[u][j]的状态就从这两个泛化物品中选择max更新即可。
但是在此之前我们还需要将dpvj求得，因为根据定义dpuj的含义是在已经选取了的结点中，选取j个结点且一定包含u结点的最大值，所以这个状态在更新当前结点之前就已经确定了。我们需要在dfs时将dpvj的状态更新出来，并且在dfs之前将dpvj进行初始化，初始化方式为在已经统计过的所有结点中选取j-1个并且一定包含当前结点的父节点u的状态，即dp[u][j-1]的状态上添加上当前子节点v的价值。
值得注意的是，在循环j的时候，通常会引入一个层数，因为当选取dpvj时，就代表着我们一定会将v的所有父节点选取，所以我们选取的j一定会大于当前的层数。
说到底，泛化物品是为了找到一个更好的状态划分方式，在这种写法中，我们在最终更新dpuj时，dpvj这个状态其实代表了一整个状态，包括了在dfs之前对于其父节点u的状态统计以及dfs时对其子结点的统计。dpuj其实是在已经处理的节点中选取s的所有方案和不选取s的所有方案中进行选择。关于泛化背包问题还需要在最后一章做一个更好的说明。
code
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
void dfs(int u,int dep);
void add(int u,int v);
const int N=310;
int head[N],nxt[N],to[N],cnt;
int n,m,a[N],f[N][N];
int main(){
int i,k;
scanf("%d%d",&n,&m);
for (i=1;i<=n;++i){
scanf("%d%d",&k,a+i);
add(k,i);
}
dfs(0,0); //按理来说应该将f[0][j]全部赋为a[0]，然后dfs(0,1)，但由于0是虚的根节点，就不需要这样做了。
printf("%d",f[0][m]); //答案是f[0][m]而非f[0][m+1]的原因同上
return 0;
}
void add(int u,int v){
nxt[++cnt]=head[u];
head[u]=cnt;
to[cnt]=v;
}
void dfs(int u,int dep){
int i,j,v;
for (i=head[u];i;i=nxt[i]){
v=to[i];
for (j=dep+1;j<=m;++j){
f[v][j]=f[u][j-1]+a[v];
}
dfs(v,dep+1);
for (j=dep+1;j<=m;++j){
f[u][j]=max(f[u][j],f[v][j]);
}
}
}上下界优化
前面提到过，树形背包问题的复杂度上界应该是 N*C，详情可以参考那篇博客，每个点对都只会在lca处合并一次，所以总的复杂度应该是的。
树形背包的优化方式有很多，除了前面提到的特殊情况的优化，还有先序遍历优化、上下界优化、求泛型物品的并，这里我也只讨论一下另外一种上下界优化，因为这种优化的通用性强而且理解简单，最适合我这种懒狗。
首先，观察朴素树形背包问题的循环：
for(int j = m+1 ; j > 0 ; j --){
for(int k = j-1 ; k >= 0 ; k --){
dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[x][k]);
}
}注意看这里的循环条件，因为DP数组的定义是i个物品，根为u，背包容量为j的最大价值，这里我们考虑每个结点包括其子节点都会有一个总的容量值，例如u这个结点本身的容量就应当是其子节点容量的和加上当前u结点的容量，这样我们在dfs的时候也可以求得x结点的容量。因此我们可以利用这个结点的容量值缩减这两个循环的大小。
void dfs(int u)
{
siz[u]=1;
f[u][1]=a[u];
int i,j,k,v;
for (i=head[u];i;i=nxt[i])
{
v=to[i];
dfs(v);
for (j=min(m+1,siz[u]+siz[v]);j>=1;--j)
{
for (k=max(1,j-siz[u]);k<=siz[v]&&k<j;++k)
{
f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);
}
}
siz[u]+=siz[v];
}
}可以看到siz数组用来记录结点的大小，每次遍历一个子结点的时候就对根节点的大小进行更新，因为虽然数组减少了一维，但实际上还是表达的前i个物品中根为u的价值。所以我们在对背包容量进行循环时，j这层循环应该将最大值控制为
min(m+1,siz[u]+siz[v]) 而里面的k层，则是控制在v结点的重量以下，并且已经完成的部分一定会包含u结点所以k大小一定小于j-w[u]，并且已经完成的部分一定小于siz[u]所以有siz[u]≥j-k即k一定大于等于j-siz[u]，可以使用这个条件作为初始值。总结
对于树形背包这个问题而言，最重要的肯定是要掌握朴素的树形背包解法，理解这种解法是理解其他多种优化的基础。而针对优化而言，这个问题有多种优化实现时间复杂度都在，其中最通用的也最简单的肯定是限定上下界的方法，这种方法很好用，也容易实现和理解，唯一比其他几种困难的是时间复杂度的分析。而泛型背包的优化则是利用泛化物品的概念将状态重新划分，从而将合并子树的步骤从C^2缩减至C，但是这种优化相对前面的那种更难理解。最后关于泛型背包的问题，还需要在最后一篇泛型背包里讨论。
