有一点难度的树形dp，只不过数据量不是很大，应该不会出现超内存和超时的问题
dp[i][j]表示以i为根的树中选j个城堡，注意此时父节点i必须要选取了
f[i][j]用于临时储存状态，有点像条件背包，树形dp的题想想基本都差不多，和背包都很像，其实做多了dp，也会发现，dp也都一个样
View Code
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #include<vector>
5 #define city 205
6 using namespace std;
7 vector<int> tree[city];
8 int dp[city][city];
9 int f[city][city];
10 int used[city];
11 int value[city];
12 int max(int a,int b)
13 {
14 return a>b?a:b;
15 }
16 int n,m;
17 void init()
18 {
19 int i;
20 for(i=0;i<205;i++)
21 tree[i].clear();
22 }
23 void dfs(int x)
24 {
25 used[x]=1;
26 int i,j,k;
27 dp[x][0]=0;
28 f[x][0]=0;
29 int t=tree[x].size();
30 for(i=0;i<t;i++)
31 {
32 int temp=tree[x][i];
33 if(!used[temp])
34 dfs(temp);
35 for(j=m;j>=0;j--)
36 {
37 for(k=0;k<=m;k++)
38 if(dp[temp][k]!=-1&&f[x][j-k]!=-1&&j>=k)
39 f[x][j]=max(f[x][j],f[x][j-k]+dp[temp][k]);
40 }
41 }
42 for(j=1;j<=m+1;j++)
43 if(f[x][j-1]!=-1)//判断状态是否可达
44 dp[x][j]=f[x][j-1]+value[x];
45 }
46
47 int main()
48 {
49 int i;
50 int a,b;
51 while(scanf("%d%d",&n,&m)&&(m||n))
52 {
53 memset(dp,-1,sizeof(dp));
54 memset(used,0,sizeof(used));
55 memset(f,-1,sizeof(f));
56 init();
57 for(i=1;i<=n;i++)
58 {
59 scanf("%d%d",&a,&b);
60 tree[a].push_back(i);
61 value[i]=b;
62 }
63 value[0]=0;
64 dfs(0);
65 printf("%d\n",dp[0][m+1]);
66 }
67 return 0;
68 }