hdu1561 The more, The Better--树形dp

原题链接：​​http://acm.hdu.edu.cn/showproblem.php?pid=1561​​

分析：建一个0点作为树根，把树连起来，dp[ i ][ j ]表示以i点为树根选择j个点的最大值。

注意该题，每选择一个点都要确保它的前提的点都要选。当时在一个地方卡了下，假如是dp[ i ][ 2 ]的话，怎么确保选择两个点是连在一起的呢，因为你每次选择一个点都要先选它的前提，仔细想了想在dp初始值上做了文章，默认dp[ k ][ 1 ]是v[ k ]，这就确保了。读者可以自己试下程序，很好理解。

#define _CRT_SECURE_NO_DEPRECATE 

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<string>
#include<stdio.h>
#define INF 99999999
#define eps 0.0001
using namespace std;

int n, m;
int dp[205][205];
int v[205];
vector<int> vec[205];

void tree_dp(int fat)
{
  dp[fat][1] = v[fat];
  for (int i = 0; i < vec[fat].size(); i++)
  {
    int son = vec[fat][i];
    tree_dp(son);
    for (int j = m + 1; j >= 2; j--)
      for (int k = 1; k < j; k++)
        dp[fat][j] = max(dp[fat][j], dp[fat][k] + dp[son][j - k]);
  }
}

int main()
{
  while (~scanf("%d%d", &n, &m) && (n + m))
  {
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i <= n; i++)
      vec[i].clear();

    int x, y;
    for (int i = 1; i <= n; i++)
    {
      scanf("%d%d", &x, &y);
      vec[x].push_back(i);
      v[i] = y;
    }

    tree_dp(0);
    printf("%d\n", dp[0][m + 1]);
  }
  return 0;
}