题目描述
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？
输入输出格式
输入格式：
第一行有两个整数N,M用空格隔开。(1<=N<=300,1<=M<=300)
接下来的N行,第I+1行包含两个整数ki和si, ki表示第I门课的直接先修课，si表示第I门课的学分。若ki=0表示没有直接先修课（1<=ki<=N, 1<=si<=20）。
输出格式：
只有一行，选M门课程的最大得分。
输入输出样例
输入样例#1：
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
输出样例#1：
13
此题因为求最大的学分，一定使用树形动态规划，否则超时！（或者说是树形依赖背包）
对于每一个节点来说，它的存在与否都是关系到他下边的学分的，题目要求最后是留下几个课程，那么如果不要这个点的左子树的话，他右子树的就可以留k-1条边，因为要抛去这个点和右子树点的边，那么现在就有两个状态，要左子树或要右子树，还有一个状态就是两边都要，那么分给左子树的边为i，分给右子树的边为k-2-i，for i=1 to k-2 do。从这里找一个最大值和上两个状态比求出最大就是这个点的最优值。
这道题还应该注意建树，因为右不一定是左的孩子。
状态转移方程f[x][j]=max(f[x][j],f[x][j-k]+f[s][k-1]+jz[x][i]);
#includde<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> jz[200],b[200];
int q,n,f[200][200]={};
int work(int x,int y)
{
int son=0;
for(int i=0;i<b[x].size();i++)
{
int s=b[x][i];//课程u的儿子结点
if(s==y) continue;
son+=(work(s,x)+1);//数搜到的结点（多加一个点）
for(int j=min(son,q);j>0;j--)//j代表保留的课程数
for(int k=min(j,q);k>0;k--)
f[x][j]=max(f[x][j],f[x][j-k]+f[s][k-1]+jz[x][i]);//程序核心：状态转移方程
}
return son;
}
int main()
{
int i,j,k,l;
cin>>n>>q;
for(i=1;i<=n;i++)
{
cin>>k>>l;
b[i].push_back(k);
b[k].push_back(i);//构造边
jz[i].push_back(l);
jz[k].push_back(l);//存价值
}
work(0,0);
cout<<f[0][q]<<endl;
return 0;
}ps：此题和”二分苹果树“基本是一个题目，只要改改边界条件即可。