HDOJ 1561 - 트리 DP, 일반 가방

방금 문제를 봤는데...나무가 아닌 것 같은데..회로가 있을 수도 있는데..생각해보니까...이건 정말 나무야..성마다 미리 격파해야 하는 성들이 많기 때문에..성 하나에 대해.미리 격파해야 할 성곽을 아버지의 구도로 삼았는데..
dp[k][i]는 k를 따르는 자수로 i개 성곽을 격파하면 얻을 수 있는 최대 수익...가방 문제 일반화...
Program:
 

#include<iostream>

#include<stack>

#include<queue>

#include<stdio.h>

#include<algorithm>

#include<string.h>

#include<cmath>

#define ll long long

#define oo 1000000007

#define MAXN 205

using namespace std;

vector<int> Tree[MAXN];

int n,m,v[MAXN],ans[MAXN],dp[MAXN][MAXN];

bool root[MAXN];

void dfs(int x,int t)

{

      int i,j,k,num;

      if (t>m) return;

      dp[x][1]=v[x]; 

      num=Tree[x].size();

      for (i=0;i<num;i++)

      {

            dfs(Tree[x][i],t+1); 

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

               for (k=1;k<=m-j;k++)

                  dp[x][j+k]=max(dp[x][j+k],dp[x][j]+dp[Tree[x][i]][k]);

      }

      return;

}

int main()

{

      int i,j,k; 

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

      {

             for (i=1;i<=n;i++) Tree[i].clear();

             memset(root,true,sizeof(root));

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

             {

                   int x,c;

                   scanf("%d%d",&x,&c);

                   Tree[x].push_back(i);

                   v[i]=c;

                   if (x) root[i]=false;

             }

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

             memset(ans,0,sizeof(ans));

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

               if (root[i])

               {

                      dfs(i,1);

                      for (j=m;j>=0;j--)

                         for (k=0;k<=m-j;k++)

                             ans[j+k]=max(ans[j+k],ans[j]+dp[i][k]);

               }

            for (i=m;i>=0;i--)

              if (ans[i]) break;

            printf("%d
",ans[i]);

      }

      return 0;

}