题意就不说了，中文题都懂的。这是我的第一道树形DP，还是看了别人的解题报告才做的。
View Code 1 #include2 #include 3 #define MAX(a,b) (a)>(b)?(a):(b) 4 #define N 205 5 struct node { 6 int from,to,next; 7 }edge[N]; 8 int dp[N][N],visit[N],val[N],head[N],n,m,tol; 9 void add(int a,int b)10 {11 edge[tol].from = a;12 edge[tol].to = b;13 edge[tol].next = head[a];14 head[a] = tol++;15 }16 void dfs(int root)17 {18 int i,j,k,u;19 visit[root] = 1;20 for(i = head[root];i != -1;i = edge[i].next)21 {22 u = edge[i].to;23 if(!visit[u])24 {25 dfs(u);26 for(k = m+1;k >= 2; --k)27 for(j = 1;j < k; ++j)28 dp[root][k] = MAX(dp[root][k],dp[root][k-j]+dp[u][j]);29 }30 }31 }32 int main()33 {34 int i,a,b;35 while(~scanf("%d %d",&n,&m) && n && m)36 {37 tol = 0;38 memset(head,-1,sizeof(head));39 memset(visit,0,sizeof(visit));40 memset(dp,0,sizeof(dp));41 for(i = 1;i <= n; ++i)42 {43 scanf("%d %d",&a,&b);44 val[i] = b;45 add(a,i);46 dp[i][1] = b;47 }48 val[0] = 0;49 dfs(0);50 printf("%d\n",dp[0][m+1]);51 }52 return 0;53 }