HUD P1561

The more, The Better
Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2939    Accepted Submission(s): 1740
Problem Description
ACboy 는 하나의 전략 게임 을 좋아 합 니 다.한 지도 에 N 개의 성 이 있 고 모든 성 에는 일정한 보물 이 있 습 니 다.매번 게임 에서 ACboy 는 M 개의 성 을 정복 하고 그 안의 보물 을 얻 을 수 있 습 니 다.그러나 지리 적 위치 때문에 어떤 성 들 은 직접 정복 할 수 없 기 때문에 이 성 들 을 정복 하려 면 반드시 다른 특정한 성 을 먼저 정복 해 야 한다.당신 은 ACboy 가 가능 한 한 많은 보물 을 얻 으 려 면 어떤 M 성 을 정복 해 야 하 는 지 계산 해 줄 수 있 습 니까?
 
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 개의 성 을 공격 하여 얻 은 가장 많은 보물 의 수량 을 나타 낸다.
 
노 골 적 인 워 터 트 리 DP,설명 완료.

#include
#include
#include

#define maxn 210
#define Clear(a,b) memset(a,b,sizeof(a))

using namespace std;

int dp[maxn][maxn],val[maxn];
int m;

vector  links[maxn];

int Max(int a,int b)
{
    if (a > b) return a;
    return b;
}

int dfs(int k)
{
    int len = links[k].size(),i,j,c,son;
    
    for(i = 1;i <= m;i++) dp[k][i] = val[k];
    
    if (len == 0) {
/*
           printf("%d:",k);
           for(i = 1;i <= m;i++) printf(" %d",dp[k][i]);
           printf("
"); 
*/
       return 0;
       }
    for(i = 0;i < len;i++) dfs(links[k][i]);
    
    for(i = 0;i < len;i++) {
          son = links[k][i];
          for(c = m;c >= 1;c--)
            for(j = 1;j <= c;j++)
              if (c - j >= 1) 
                dp[k][c] = Max(dp[k][c],dp[k][c-j] + dp[son][j]);
          }
/*
    printf("%d:",k);
    for(i = 1;i <= m;i++) printf(" %d",dp[k][i]);
    printf("
"); 
*/
    return 0; 
}

int work()
{
    int n,i,fa;
    
    scanf("%d%d",&n,&m);
    if (n == 0 && m == 0) return 0;
    
    Clear(dp,0);
    Clear(val,0);
    for(i = 0;i <= n;i++) links[i].clear();
    
    for(i =  1;i <= n;i++) {
          scanf("%d%d",&fa,&val[i]);
          links[fa].push_back(i);
          }
    m++;
    dfs(0);
    printf("%d
",dp[0][m]);
    return 1;
}

int main()
{
    while(work());
    return 0;
}