依赖背包：一旦选了某门课 i，就只能继续往 i 的子树走，不能选其他兄弟节点的课，因此很多课程之间是互斥的，且要选某门课的话，就必须先选它的前置课程。

在做树上背包问题之前，建议把背包的基本题型全部复习一遍，然后对比在线性空间上做背包问题 VS 在树上做的区别。

例如，可以先回忆并完成此题：P1064 [NOIP2006 提高组] 金明的预算方案

#include <iostream>
#include<vector>
using namespace std;

const int N = 310, M = 310;
int f[N][M]; // f[u][i]：子树u选了i门课的最大学分数
int n, m, ans;
vector<int> g[N];

void dfs(int u) {
	for (int v : g[u]) { // 子-->父，先算出子节点的状态，然后综合得到父节点的状态
		dfs(v); // 先往下递归处理子节点
		// 对子节点（附件）跑0-1背包
        for (int i = m; i > 0; i--) // 倒序枚举0-1背包体积
			for (int k = 1; k < i; k++) // 枚举每个子节点分配到的选课门数
				f[u][i] = max(f[u][i], f[v][k] + f[u][i - k]);
	}
}

int main() {
	cin >> n >> m;
	int k;
	for (int i = 1; i <= n; i++) {
		cin >> k >> f[i][1]; // f初始化：只选课程i获得的学分数
		g[k].push_back(i);
	}

    // 一旦选了某门课 i，在往下递归搜后续过程时，千万别忘了课程 i 要计入已选课程数目内。
	m++;
    // 这里搞了个虚拟根（课程0），因此 m 的值要增加 1。
	dfs(0);
	cout << f[0][m];

	return 0;
}

以上解法是 $O(m^2\cdot n)$ 的，结合DFS序的更优解法请参考题解

以及这篇文章

补充使用DFS序的 $O(mn)$ 解法。若忘了请复习天河初二寒假集训LCA课程内容（LCA的倍增、DFS序、欧拉序、树剖求法）！！！

#include <iostream>
#include<vector>
using namespace std;

const int N = 310, M = 310;
// f[u][i]：从第u到第n个物品（课程），最多花费i元（课程门数），能得到的最大权值和（学分数）
int f[N][M];
int n, m, a[N]; // 点权
vector<int> g[N];
int sz[N]; // 子树节点总数（包括根）
int tot, list[N]; // DFS序（前序）

void dfs(int u) {
	list[++tot] = u;
	sz[u] = 1;
	for (int v : g[u]) {
		dfs(v); // 先往下递归处理子节点
		sz[u] += sz[v];
	}
}

int main() {
	cin >> n >> m;
	int k;
	for (int i = 1; i <= n; i++) {
		cin >> k >> a[i];
		g[k].push_back(i);
	}

	dfs(0);
	// DP：因转移方程的需要，逆序枚举物品（课程）。+1是因为虚根0的存在。
	for (int i = n + 1; i >= 1; i--)
		for (int j = 1; j <= m + 1; j++)
			f[i][j] = max(f[i + sz[list[i]]][j], f[i + 1][j - 1] + a[list[i]]);

	cout << f[1][m + 1];

	return 0;
}