好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

---

题目描述

原题来自：CTSC 1997

大学实行学分制。每门课程都有一定的学分，学生只要选修了这门课并通过考核就能获得相应学分。学生最后的学分是他选修各门课的学分总和。

每个学生都要选择规定数量的课程。有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其他的一些课程基础上才能选修。例如《数据结构》必须在选修了《高级语言程序设计》后才能选修。我们称《高级语言程序设计》是《数据结构》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述，每门课都有一个课号，课号依次为 $1,2,3,\dots$。

下面举例说明：

课号	先修课号	学分
1	无	1
2	1
3	2	3
4	无
5	2	4

上例中课号 1 是课号 2 的先修课，即如果要先修课号 2，则课号 1 必定已被选过。同样，如果要选修课号 3，那么课号 1 和课号 2 都一定被选修过。

学生不可能学完大学开设的所有课程，因此必须在入学时选定自己要学的课程。每个学生可选课程的总数是给定的。请找出一种选课方案使得你能得到的学分最多，并满足先修课优先的原则。假定课程间不存在时间上的冲突。

---

输入格式

输入的第一行包括两个正整数 $M, N$，分别表示待选课程数和可选课程数。

接下来 $M$ 行每行描述一门课，课号依次为 $1,2,\dots,M$。每行两个整数，依次表示这门课的先修课课号（若不存在，则该项值为 $0$）和该门课的学分。

各相邻数值间以空格隔开。

---

输出格式

输出一行，表示实际所选课程学分之和。

---

样例

样例输入

7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2

样例输出

13

样例解释

$M=7$（课程数），$N=4$（最多选 4 门课）。

课程信息（课号、先修课、学分）：

1. 2 2 → 课号1（隐含）？注意：第一行是课号1，先修课2，学分2？这里数据给出顺序是课号从1开始：
   实际上输入顺序是：第一行对应课号1：先修课2，学分2；
   第二行课号2：先修课0，学分1；
   第三行课号3：先修课0，学分4；
   第四行课号4：先修课2，学分1；
   第五行课号5：先修课7，学分1；
   第六行课号6：先修课7，学分6；
   第七行课号7：先修课2，学分2。

先修关系构成森林（因为有先修课为0的根节点）。为了统一处理，可以添加一个虚拟的课程0（学分为0），作为所有无先修课程的先修课，这样整个森林变成一棵树，根为0。

转换后树形结构（0为根）：

• 0
  • 2（学分1）
    • 1（学分2）
    • 4（学分1）
    • 7（学分2）
      • 5（学分1）
      • 6（学分6）
  • 3（学分4）

题目要求选 $N$ 门课（不包括虚拟课程0），求最大总学分。

通过树形 DP（树上背包），可以求得选4门课的最大学分和为13。

---

数据范围

对于 $100\%$ 的数据：

• $1 \le N \le M \le 100$
• 每门课的学分不超过 $20$

---

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$

---

提示
此题为 树形 DP（依赖背包） 问题。

由于每门课最多只有一门先修课，整个课程体系是一个森林。我们可以添加一个虚拟的课程0（学分0），作为所有无先修课的课程的先修课，这样整个体系成为一棵以0为根的树。

状态定义：$dp[u][k]$ 表示以 $u$ 为根的子树中选择 $k$ 门课（包括 $u$ 本身）能获得的最大学分。

转移方程：
对于节点 $u$，将其子节点看作物品组，做分组背包：

$$dp[u][j] = \max_{0 \le t \le j-1} \{ dp[u][j-t] + dp[v][t] \}$$

其中 $v$ 是 $u$ 的子节点，$t$ 表示在子节点 $v$ 的子树中选择的课程数（不包括 $v$ 本身？注意定义是否包括根）。

更准确地说，$dp[u][j]$ 中 $j$ 表示在 $u$ 为根的子树中选择的总课程数（包括 $u$ 本身），所以枚举 $v$ 子树中选择 $t$ 门课时，$u$ 已占一门，因此 $dp[u][j]$ 由 $dp[u][j-t]$ 和 $dp[v][t]$ 转移而来。

初始化：$dp[u][1] = \text{score}[u]$。

最终答案为 $dp[0][N+1]$（因为虚拟课程0不占选课数，但计算时多一个节点）。

复杂度 $O(M \cdot N^2)$，可以接受。