HDOJ树形DP专题之Anniversary party

没有上司的晚会，经典的树形DP题。
View Code
 1 #include <stdio.h>
 2 #include <memory.h>
 3 #define MAX(a,b) ((a)>(b)?(a):(b))
 4 #define N 6000
 5 int a[N],p[N],d[N],c[N],vis[N],sums[N],sumgs[N],dmax,n;
 6 int fd(int k)
 7 {
 8   if(!vis[k]) return d[k]=0;
 9   if(d[k])  return d[k];
10   return d[k]=fd(p[k])+1;
11 }
12 int main()
13 {
14   int i,j,u,v,ans;
15   while(~scanf("%d",&n))
16   {
17     for(i=0;i<n;i++)  scanf("%d",&a[i]);
18     memset(vis,0,sizeof(vis));
19     memset(d,0,sizeof(d));
20     while(scanf("%d%d",&u,&v))
21     {
22       if(u==0 && v==0)  break;
23       u--,v--;
24       p[u]=v;
25       vis[u]=1;
26     }
27     dmax=0;
28     for(i=0;i<n;i++)  dmax=MAX(dmax,fd(i));
29     memset(sums,0,sizeof(sums));
30     memset(sumgs,0,sizeof(sumgs));
31     for(i=dmax;i>=0;i--)
32     {
33       for(j=0;j<n;j++)if(d[j]==i)
34       {
35         c[j]=MAX(sums[j],MAX(sumgs[j],sumgs[j]+a[j]));
36         if(i>0) sums[p[j]]+=c[j];
37         if(i>1) sumgs[p[p[j]]]+=c[j];
38       }
39     }
40     ans=0;
41     for(i=0;i<n;i++)if(!vis[i])  ans+=c[i];
42     printf("%d\n",ans);
43   }
44   return 0;
45 }