[HDU 1561] The more, The Better

The more, The Better
Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5506    Accepted Submission(s): 3274 
Problem Description
ACboyは戦略ゲームが大好きで、1つの地図の上で、Nつの城があって、すべての城はすべて一定の宝物があって、毎回ゲームの中でACboyはMつの城を攻略して中の宝物を得ることを許可します.しかし、地理的な理由で、直接攻略できない城もあります.これらの城を攻略するには、まず他の特定の城を攻略しなければなりません.できるだけ多くの宝物を手に入れるにはどのM城を攻略すべきか、ACboyに計算してもらえますか?
 
Input
各試験例は、まず、2つの整数、N、M.(1<=M<=N<=200)を含む.次のN行では、各行に2つの整数が含まれ、a,b.i行目では、aはi番目の城を攻略するにはまずa番目の城を攻略しなければならないことを表し、a=0であればi番目の城を直接攻略することができることを表す.bはi番目の城の宝物の数を表し、b>=0である.N=0でM=0入力が終了します.
 
Output
各試験例について、ACboyがM個の城を攻略して得た最も多くの宝物の数を表す整数を出力する.
 
Sample Input
3 2 0 1 0 2 0 3 7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2 0 0
 
Sample Output
5 13
 
前の2つの問題と同じ、==

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;



#define N 210

struct Edge

{

    int next,to;

}edge[N*N/2];

int head[N<<1],tot;



int m,n;

int val[N];

int dp[N][N];         //dp[i][j]      i    j            



void init()

{

    tot=0;

    memset(head,-1,sizeof(head));

    memset(dp,0,sizeof(dp));

}

void add(int x,int y)

{

    edge[tot].to=y;

    edge[tot].next=head[x];

    head[x]=tot++;

}

void dfs(int u)

{

    dp[u][1]=val[u];

    for(int i=head[u];i!=-1;i=edge[i].next)

    {

        int v=edge[i].to;

        dfs(v);

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

        {

            for(int k=0;k<j;k++)

            {

                dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);

            }

        }

    }

}

int main()

{

    while(scanf("%d%d",&n,&m), n||m)

    {

        init();

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

        {

            int x;

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

            add(x,i);

        }

        m++;                      //     0,      

        dfs(0);

        cout<<dp[0][m]<<endl;

    }

    return 0;

}