选课

https://www.luogu.com.cn/problem/P2014

设dp[i][j]表示以i为根的子树中（必须选i），选j门课获得的最多学分

先递归求出i的所有孩子的dp值

然后背包

枚举儿子（物品）枚举j（容量）再枚举儿子子树中选几门（决策）（注意倒序）

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1100],dp[1100][1100];
struct node{
	int fa,nxt,first;
}tree[1100];
void build(int son,int father)
{
	tree[son].fa=father;
	tree[son].nxt=tree[father].first;
	tree[father].first=son;
}
void dfs(int root)
{
	dp[root][0]=0;
	for(int i=tree[root].first;i;i=tree[i].nxt)
	{
		dfs(i);
		for(int j=m;j>=0;j--)
		for(int k=j;k>=0;k--)
		{
			dp[root][j]=max(dp[root][j],dp[root][k]+dp[i][j-k]);
		}
	}
	if(root!=0)
	{
		for(int j=m;j>=1;j--)
		dp[root][j]=dp[root][j-1]+a[root];
	}
}
int main()
{

	memset(dp,-0x3f,sizeof(dp));
	cin>>n>>m;
	int x;
	for(int i=1;i<=n;i++)
	{
		cin>>x>>a[i];
		build(i,x);
	}
	dfs(0);
	cout<<dp[0][m];
	return 0;
}