学步园

题意：

有n座城堡，里边藏有价值val[i]的宝物，现在要去攻打这些城堡，总共能攻打m座城堡；有些城堡有前置条件，即需要攻击某个城堡a，必须已经攻占另个城堡b，求最大能获得价值。

题解：

树形dp。

一开始的图不是一颗树，我们需要将之变成一棵树，设虚拟城堡0，所以没有前置条件的城堡都需要先攻打城堡0，才能攻打。那么就能画出一颗以0为根的树。之后就是树形dp了，dp[i][j]表示i结点，剩余兵力为j（还能攻打j个城堡）的时候，能获得的最大宝物。dp[i][j]=max(dp[i][j],do[i][j-k]+dp[u][k])，其中u为i的子结点。那么对于所有的i的子结点，要使得dp[i][j]最大，就能转换成01背包问题了。

注意：由于增加了一个虚拟结点0，所以能攻打的城堡数m需要+1，即用于攻打城堡0，获得的价值val[0]=0。

代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cctype>
using namespace std;

const int maxn=202;
int dp[maxn][maxn],val[maxn];
vector<int>e[maxn];
int n;
void dfs(int i,int pre,int m)
{
    for(int j=1;j<=m;j++)dp[i][j]=val[i];
    for(int j=0;j<e[i].size();j++)
    {
        int u=e[i][j];
        if(u!=pre)
        {
            dfs(u,i,m);
            for(int k=m;k>=1;k--)
            {
                for(int p=0;p<k;p++)
                dp[i][k]=max(dp[i][k],dp[i][k-p]+dp[u][p]);
            }
        }
    }
}
int main()
{
    int m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0)break;
        int i,j,k,a,b;
        for(i=0;i<=n;i++)e[i].clear();
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&a,&val[i]);
            e[a].push_back(i);
        }
        dfs(0,-1,m+1);
        printf("%d\n",dp[0][m+1]);
    }
    return 0;
}