【HDOJ】1561 The more, The Better

树状DP。

 /* 1561 */

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #include <vector>

 using namespace std;

 #define MAXN 205

 vector<int> tb[MAXN];

 int dp[MAXN][MAXN];

 int a[MAXN];

 int n, m;

 int max(int a, int b) {

     return a>b ? a:b;

 }

 void init() {

     int i, j, k;

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

         tb[i].clear();

     memset(dp, , sizeof(dp));

 }

 void dfs(int u, int t) {

     int i, j, k, tmp;

     int v;

     if (t <= )

         return ;

     for (i=; i<tb[u].size(); ++i) {

         v = tb[u][i];

         dfs(v, t-);

         for (j=t; j>=; --j) {

             for (k=; k<=j; ++k) {

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

             }

         }

     }

     if (u) {

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

             dp[u][i] = dp[u][i-] + a[u];

     }

 }

 int main() {

     int i, j, k;

     #ifndef ONLINE_JUDGE

         freopen("data.in", "r", stdin);

     #endif

     a[] = ;

     while (scanf("%d %d", &n, &m)!=EOF && (n||m)) {

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

             scanf("%d %d", &j, &a[i]);

             tb[j].push_back(i);

         }

         dfs(, m);

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

         init();

     }

     return ;

 }