题目描述 Description
学校实行学分制。每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。学校开设了N（N<300）门的选修课程，每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。
在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如《Frontpage》必须在选修了《Windows操作基础》之后才能选修。我们称《Windows操作基础》是《Frontpage》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。每门课都有一个课号，依次为1，2，3，…。 例如:
表中1是2的先修课，2是3、4的先修课。如果要选3，那么1和2都一定已被选修过。
你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。
输入描述 Input Description
输入文件的第一行包括两个整数N、M（中间用一个空格隔开）其中1≤N≤300,1≤M≤N。
以下N行每行代表一门课。课号依次为1，2，…，N。每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。
输出描述 Output Description
输出文件只有一个数,实际所选课程的学分总数。
样例输入 Sample Input
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
样例输出 Sample Output
13
分析：
描述：
有些课程可以直接选修，有些课程必须在选了其他的一些课程后（最多一个）才能选修
这个‘最多一个’的限制很奇怪
一对一的关系实际上就是爸爸和儿子的关系
所以整个课表可以抽象成一片森林
为了方便，我们可以建立一个虚拟节点root
把森林变成一棵树
f[i][j]表示以i为根的子树选了j个节点的最大值
树上背包
（什么?背包从来没在树上做过啊，先拿来前辈的代码%%）
f[i][j]对于每一个i有两种情况：
1.i不修，则i的孩子一定不修，所以为0；
2.i修，则i的孩子们可修可不修
（在这里其实可以将其转化为将j-1个对i的孩子们进行资源分配的问题，也属于背包问题）
tip
分析中说要建立一个虚拟根root，
实际上并不用特意的构建，
所有没有先修课的课程，在描述的时候第一个数都是0
这样我们直接把0当做root，连边即可
m++; //以0为根，0也选上了，所以总的选课数要++
g是一个很神奇的数组
在一开始的时候用g数组复制一下当前的f信息，在之后的转移时，直接用g
具体原因实在不清楚
循环顺序很重要，
在第二层循环的时候，l要从大到小
在维护i必修的循环时，l从大到小
保证每一个状态只加了一个v[now]
这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int N=310;
struct node{
int x,y,nxt;
};
node way[N<<1];
int st[N],tot=0,f[N][N],v[N],size[N];
int n,m,g[N];
void add(int u,int w)
{
tot++;
way[tot].x=u;way[tot].y=w;way[tot].nxt=st[u];st[u]=tot;
tot++;
way[tot].x=w;way[tot].y=u;way[tot].nxt=st[w];st[w]=tot;
}
void dfs(int now,int fa)
{
size[now]=1; //计算子树大小
for (int i=st[now];i;i=way[i].nxt)
if (way[i].y!=fa)
dfs(way[i].y,now),
size[now]+=size[way[i].y];
}
void doit(int now,int fa,int k) //从叶子结点开始dp，直接找叶子好烦，干脆递归
{
int i,j,l;
for (i=st[now];i;i=way[i].nxt)
{
if (way[i].y!=fa)
{
doit(way[i].y,now,k);
for (j=0;j<size[now];j++) g[j]=f[now][j]; //重要
for (j=0;j<=size[way[i].y];j++) //儿子可以不修
for (l=size[now]-1;l>=j;l--) //l=size[now]-1 i一定要修，把i的位置留出来了
f[now][l]=max(f[now][l],f[way[i].y][j]+g[l-j]);
}
}
f[now][0]=0; //i不修
for (i=size[now];i>=1;i--)
f[now][i]=f[now][i-1]+v[now]; //i一定要修
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
int u,w;
scanf("%d%d",&u,&w);
add(u,i); //先修课 ,没有先修课的向root连边
v[i]=w;
}
m++; //以0为根，0也选上了，所以总的选课数要++
dfs(0,0);
doit(0,0,m);
printf("%d",f[0][m]);
return 0;
}