给定n，m表示n个城堡，我们可以选择攻占m个城堡。要使得价值最大
接下来n行 a b, 第i行的a b，表示攻占第i个城堡的价值为b，但需要先攻占第a个城堡
如果有多个a=0的点，那么就不是一棵树，但是我们可以建立一个根结点0，让根结点指向那些a=0的点， 同时m++，因为更结点必须被占据，占据一个结点需要一个容量
每个结点可以选或者不选，但是如果选，当且仅当父亲结点也被选。
所以是树上面的01背包问题，所以只要在每个结点处枚举当前容量和孩子的容量，算出各个容量的最大值。
状态转移方程见代码
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <algorithm> 5 #include <iostream> 6 #include <queue> 7 #include <stack> 8 #include <vector> 9 #include <map> 10 #include <set> 11 #include <string> 12 #include <math.h> 13 using namespace std; 14 typedef long long LL; 15 const int INF = 1<<30; 16 const int N = 200+10; 17 struct Edge 18 { 19 int v,next; 20 }g[N]; 21 int head[N],e; 22 int val[N]; 23 int dp[N][N];//dp[i][j] 表示对于第i个城堡，有容量j能获得的最大价值 24 int n,m; 25 void init(int n) 26 { 27 for(int i=0; i<=n; ++i) 28 head[i] = -1; 29 e = 0; 30 } 31 void addEdge(int a, int b) 32 { 33 g[e].v = b; 34 g[e].next = head[a]; 35 head[a] = e++; 36 } 37 void dfs(int u, int fa) 38 { 39 for(int i=1; i<=m; ++i) 40 dp[u][i] = val[u]; 41 for(int i=head[u]; i!=-1; i=g[i].next) 42 { 43 int v = g[i].v; 44 if(v==fa) continue; 45 dfs(v,u); 46 for(int j=m; j>=1; --j) 47 for(int k=1; k+j<=m; ++k) 48 dp[u][j+k] = max( dp[u][j+k], dp[u][j]+dp[v][k] ); 49 } 50 } 51 int main() 52 { 53 int i,a,b; 54 while(scanf("%d%d",&n,&m),n) 55 { 56 init(n); 57 bool flag = false; 58 for(i=1; i<=n; ++i) 59 { 60 scanf("%d%d",&a,&val[i]); 61 if(a==0) 62 flag = true; 63 addEdge(i,a); 64 addEdge(a,i); 65 } 66 memset(dp,0,sizeof(dp)); 67 if(flag) 68 { 69 m++; 70 dfs(0,-1); 71 printf("%d ",dp[0][m]); 72 } 73 else 74 { 75 dfs(1,-1); 76 printf("%d ",dp[1][m]); 77 } 78 79 80 } 81 return 0; 82 }