选课

选课

传送门
树型背包，结合树型dp（dfs）和背包dp。

#include<bits/stdc++.h>
using namespace std;
int n,m,f[1005][1005],k[1005];
vector<int> son[1005];

int dfs(int u)
{
	int p=1;
	f[u][1]=k[u];
	for(int v:son[u])
	{
		int siz=dfs(v);
		for(int i=min(m+1,p);i;i--)
		 for(int j=1;j<=siz&&i+j<=m+1;j++)
			f[u][i+j]=max(f[u][i+j],f[u][i]+f[v][j]);
		p+=siz;
	}
	return p;
}
int main()
{
	scanf("%d%d",&n,&m);
	int x;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&k[i]);
		son[x].push_back(i);
	}
	dfs(0);
	printf("%d",f[0][m+1]);
	
	return 0;
}

oi-wiki

1. 建树：
   son[x].push_back(i);可将所有课看成森林，设定一个“0号课”，将森林连城一棵大树，根节点为0.

2. 状态转移方程：
   f[u][i+j]=max(f[u][i+j],f[u][i]+f[v][j]); ， 类比背包来看，\(i+j\)看成当前剩余容量，将大小为\(i+j\)的总容量分给子树\(v\)和根节点\(u\)剩下的子树，遍历所有分割情况，对于子树\(v\) ，由于dfs从叶子到根回溯，可保证\(f[v][j]\) 一定已经求出，对于根节点\(u\) 剩下的子树，\(i\) 倒序循环类比01背包，确保不会重复选择\(v\)节点，则\(f[u][i]\)只会记录未选\(v\)时的状态。因此\(f[u][i+j]\)被更新时\(f[v][j]\)已经确定，\(f[u][i]\)在遍历过程中也会被确定。（可参考分组背包）。

3. 初始化：
   f[u][1]=k[u];，\(f[u][1]\)（节点原有的值）可看成初始化，由于\(i+j\)从2开始遍历，相当于\(f[u][i]\)中一定会包含\(f[u][1]\)，当dfs到叶子也会被更新为\(f[u][1]\)，也算初始值吧。