树上背包即在树上的背包（树上背包 理解2）

题目

选课，时间冲突就是拓扑排序

这题是一个前驱对应多个后继，所以可以用树形dp（多对一也可以用）

若多个前驱对应多个后继，要用拓扑排序

看出是背包（树上）（体积为1）

强制二叉树只是让你好理解树上背包

模型的形还是用背包的外观看出

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=3e2+7;
int const M=3e2+7;
struct node{
	int a,next,len;
}e[M<<1];
int cnt,head[N];
void add(int x,int y,int len){
	e[++cnt].a=y;
	e[cnt].len=len;
	e[cnt].next=head[x];
	head[x]=cnt;
}
int n,m;
int w[N],ru[N];
ll f[N][M];  //f[u][j]表示以u为根选j个点的最大价值，且u必选，因为u是前驱，只有前驱课学了，才能学后继课 
//树上背包一共有四维，四个循环 
void dfs(int u,int fa){	   //枚举根 
	f[u][1]=w[u];    //边界   //不管怎样都要选根
	for(int i=head[u];i!=-1;i=e[i].next){ //枚举物品 
		int v=e[i].a;
		if(v==fa) continue;
		dfs(v,u);    //预处理物品的价值 
		for(int j=m;j>=1;--j){   //枚举体积 
			for(int k=0;k<=j-1;++k){  //枚举物品的体积  //这里k也可以从1开始 
				f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);   //f[v][k]为物品v体积为k时的价值 
			}
		}
	}
}
int main(){
	cin >> n >> m;
	m++;  //加了0号节点，且0号节点必选 
	memset(e,-1,sizeof e);
	memset(head,-1,sizeof head);
	for(int i=1,b;i<=n;++i){
		cin >> b >> w[i];
		if(b==0) add(0,i,0);
		else add(b,i,0);
	}
	dfs(0,0);
	cout << f[0][m];
	return 0;
}