学校实行学分制。每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。学校开设了N（N<300）门的选修课程，每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。

　　在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如《Frontpage》必须在选修了《Windows操作基础》之后才能选修。我们称《Windows操作基础》是《Frontpage》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。每门课都有一个课号，依次为1，2，3，…。 例如:

【详见图片】
表中1是2的先修课，2是3、4的先修课。如果要选3，那么1和2都一定已被选修过。 　　你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。

输入文件的第一行包括两个整数N、M（中间用一个空格隔开）其中1≤N≤300,1≤M≤N。 
以下N行每行代表一门课。课号依次为1，2，…，N。每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。

输出文件只有一个数,实际所选课程的学分总数。

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

13

各个测试点1s

#define N 320

#include<iostream>

using namespace std;

#include<cstdio>

#include<cstring>

struct Edge{

    int v,last;

}edge[N*N];

int head[N],w[N];

int f[N][N];

int n,m,t=;

void add_edge(int u,int v)

{

    t++;

    edge[t].v=v;

    edge[t].last=head[u];

    head[u]=t;

}

void input()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;++i)

    {

        int x;

        scanf("%d%d",&x,&w[i]);

        add_edge(x,i);

    }

}

void dfs(int k)

{//注意虚点0与实点的区别，虚点树的根没有值，最多可以在子树上取到m个点，而对于实点树，他的根节点必须取，因此子树上最多可以取到m-1个点*/

    int flag=;/*纪录实点虚点的*/

    if(k==) flag=;

    for(int i=;i<=m;++i)

      f[k][i]=w[k];/*先取根节点*/

    for(int l=head[k];l;l=edge[l].last)

    {

         dfs(edge[l].v);/*用子树上形成的背包来向上更新*/

         for(int j=m;j>=flag;--j)

           for(int p=;p<=j-flag;++p)

           {

               f[k][j]=max(f[k][j],f[k][j-p]+f[edge[l].v][p]);

           }

    }

}

int main()

{

    input();

    dfs();

    printf("%d\n",f[][m]);

    return ;

}

#include<iostream>

using namespace std;

#include<cstdio>

#include<cstring>

#define N 321

struct Node{

    int lch,rch,sum;

}node[N]={};

int n,x,m,w[N]={};

int f[N][N]={};

int count[N]={};

void add(int u,int v)

{/*一般树转为二叉树，“左孩子右兄弟”原则，v是u的孩子，如果v不能做u的左孩子，那就做u左孩子的兄弟，或者u左孩子兄弟的兄弟*/

    if(node[u].lch==)

    {

        node[u].lch=v;

    }

    else{

        int i=node[u].lch;

        while(node[i].rch) i=node[i].rch;

        node[i].rch=v;

    }

}

int read()

{

    char s;int x=;

    s=getchar();

    while(s<''||s>'') s=getchar();

    while(''<=s&&s<='')

    {

        x=x*+s-'';

        s=getchar();

    }

    return x;

}

void input()

{

    n=read();m=read();

    for(int i=;i<=n;++i)

    {

        x=read();w[i]=read();

        add(x,i);

    }

}

void dfs(int k)

{

    if(node[k].lch) dfs(node[k].lch);/*先处理好孩子*/

    if(node[k].rch) dfs(node[k].rch);

    count[k]=count[node[k].lch]+count[node[k].rch]+;

    f[k][]=w[k];/*以防这是叶子节点*/

    for(int i=;i<=count[node[k].rch];++i)

    {

        f[k][i]=max(f[k][i],f[node[k].rch][i]);/*当前这个点取i个，可以从不包括k只取他的右孩子，也可以包括k取他的右孩子，包含在下面的方程中，这两个方程包含了总共的三种情况*/

        for(int j=;j<=count[node[k].lch];++j)/*或者是左右孩子一起取，那么就要取到当前k节点了*/

          f[k][i+j+]=max(f[k][i+j+],f[node[k].rch][i]+w[k]+f[node[k].lch][j]);

    }

}

int main()

{

    input();

    dfs(node[].lch);

    cout<<f[node[].lch][m]<<endl;/*注意深搜的时候，从0的左孩子开始搜，因为count[node[0].lch]==m，所以不能cout<<count[0][m].而且从0处开始时，dfs中的一些语句都没有意义*/

    /*dfs(0);

    cout<<f[0][m+1]<<endl;*/

    return ;

}