题目大意：有n门学分在1到11的课，可以选m门，但有些课有先修课，需要选了先修课才能选该门课，请问最多能获得多少学分？

【题目描述】

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

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

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

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

【输入格式】

输入文件的第一行包括两个正整数M、N（中间用一个空格隔开）其中M表示待选课程总数（1≤M≤1000)，N表示学员可以选的课程总数（1≤N≤M)。

以下M行每行代表一门课，课号依次为1，2，…，M。每行有两个数（用一个空格隔开），第一个数为这门课的先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。

【输出格式】

输出文件第一行只有一个数，即实际所选课程的学分总数。以下N行每行有一个数，表示学员所选课程的课号。

【输入样例】

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

【输出格式】

13

解题思路

选课关系是一棵树，定义状态，会变的是课程编号（子树根）以及选课数量，那么我们就定义f[i][j]表示以i为根的子树选j门课的最大学分。

先考虑简单的情况，如果这是一颗二叉树，整棵树选m门课，那么根结点a必须要选，左右子树共选m-1门课，可以用卡特兰数进行地推，枚举左子树lc选i(0到m-1)门课，那么右子树rc选j=m-1-i门课，f[a][m] = max(f[lc][i] + f[rc][j] + 课程a的学分)。然而这并不是二叉树，一个根结点可能有k个儿子，也就是m-1门课分到k个子树，每个子树选多少门课呢？暴力搜索的话是NP难度的。

一个巧妙的做法，就是将多叉树转成二叉树，转成左儿子右兄弟的结构：如根结点只有1个儿子，那就放在lc位置；如果有两个儿子，那么1个放在lc位置，另外一个放在lc的rc位置；如果有多个儿子，那么1个放在lc位置，1个放在lc的rc位置，后面陆续放到rc的rc位置……

这样就可以枚举左右子树选多少门课了，需要注意的是，选左子树的话，根必选，否则根只是可选，因为选右子树，右子树是根的兄弟，兄弟不选也没关系。因此，转移关系是这样的：以a为根的子树选m门课，不选a的话，f[a][m] = f[rc][m]，即m门课都在右子树选完；选a的话，左子树可以选i=0~m-1门课，右子树选j=m-i门课。

当然，这道题还可以在树上做分组背包，即一个容量为m的背包，最多能装多少学分呢？根结点的子树各自看成一个物品，要么装/选，要么不装/选。需要注意的是，对于一个子树，他可以选0到m-1门课，也就是说这个物品占用的空间可以不一样；但是，如果用了选a门课的子树，就不能同时选b门课的同一棵子树，也就是说这个背包的不同状态只能选一种。因此，应该先枚举分组，再枚举容量，最后枚举物品的各种状态，就能保证同一个容量，不会同时选了不同状态的物品。f[a][i] = f[b][j] + f[a][i-j]，儿子更新父亲，a的容量为i，b占用j容量，那么a可以先装i-j的容量，再加上b装了b的容量的学分。

剪枝：枚举容量的时候，一个子树a如果只有k个结点，那么子树a最多选k门课，容量最大为k，超过k的可以不枚举。

程序实现

DFS后续遍历，树上做分组背包，并根据子树结点数缩小枚举范围实现剪枝，时间复杂度是$O(n^2)$，因为深搜每个结点a，循环次数为子树内任选两点的方案数，整个搜索的时间复杂度就是任意两点的方案数。

逆BFS序分组背包，儿子更新父亲：

左儿子右兄弟，枚举左右子树选课数量：