HDOJ树形DP专题之The more, The Better

这题要用左二子，右兄弟的存储结构来存树（附加一个结点0，将森林连成树），然后就是在二叉树上DP。

View Code

 1 #include <stdio.h>
 2 #include <memory.h>
 3 #define MAX(a,b) ((a)>(b)?(a):(b))
 4 #define N 205
 5 int son[N],bro[N],w[N],n,m;
 6 int c[N][N];
 7 void Insert(int u,int fa,int x)
 8 {
 9   w[u]=x;
10   if(son[fa]==-1) son[fa]=u;
11   else  bro[u]=bro[son[fa]],bro[son[fa]]=u;
12 }
13 int dp(int r,int k)
14 {
15   int i,ret;
16   if(r==-1 || !k)  return 0;
17   if(c[r][k]!=-1) return c[r][k];
18   ret=dp(bro[r],k);
19   for(i=0;i<k;i++) ret=MAX(ret,w[r]+dp(son[r],i)+dp(bro[r],k-1-i));
20   return c[r][k]=ret;
21 }
22 int main()
23 {
24   int i,fa,x;
25   while(~scanf("%d%d",&n,&m)&&n)
26   {
27     memset(son,-1,sizeof(son));
28     memset(bro,-1,sizeof(bro));
29     for(i=1;i<=n;i++)
30     {
31       scanf("%d%d",&fa,&x);
32       Insert(i,fa,x);
33     }
34     w[0]=0;
35     memset(c,-1,sizeof(c));
36     printf("%d\n",dp(0,m+1));
37   }
38   return 0;
39 }