Description
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？
Input
第一行有两个整数N,M用空格隔开。(1<=N<=200,1<=M<=150)
接下来的N行,第I+1行包含两个整数ki和si, ki表示第I门课的直接先修课，si表示第I门课的学分。若ki=0表示没有直接先修课（1<=ki<=N, 1<=si<=20）。
Output
只有一行，选M门课程的最大得分。
Sample Input
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
Sample Output
13
分析：
由题意可知树形DP可以解决，每个课程可有选修和不选修两种到达，满足无后效性。
F[i][j]表示以i为根(主修)选j个到达i的选修课程的最大得分。
s[i]表示选i门课程的最大分数总和。
状态方程：s[m]=max(F[root][k]+s[j]){0<=k<=m && 0<=j<=m && k+j<=m};
【参考程序】：
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int F[500][500],a[500][500];
int num[500],s[500],w[500];
int n,m;
void tree_dp(int v)
{
for (int i=1;i<=num[v];i++) tree_dp(a[v][i]);
memset(s,0,sizeof(s));
for (int i=1;i<=num[v];i++)
for (int j=m;j>=0;j--)
for (int k=0;k<=m;k++)
if (j+k<=m)
if (F[a[v][i]][k]+s[j]>s[j+k])
s[j+k]=F[a[v][i]][k]+s[j];
if (v==0)
{
printf("%d\n",s[m]); exit(0);
}
else
for (int i=1;i<=m;i++) F[v][i]=s[i-1]+w[v];
}
int main()
{
//freopen("choose.in","r",stdin);
//freopen("choose.out","w",stdout);
scanf("%d%d",&n,&m);
memset(num,0,sizeof(num));
int wh;
for (int i=1;i<=n;i++)
{
scanf("%d%d",&wh,&w[i]);
num[wh]++;
a[wh][num[wh]]=i;
}
tree_dp(0);
return 0;
}