hdu 1520 树形dp入门

和poj 1463基本一样。
 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 using namespace std;
 6 
 7 const int N = 6001;
 8 int head[N];
 9 int rating[N];
10 bool flag[N];
11 int dp[N][2];
12 int e, n;
13 
14 void init()
15 {
16     e = 0;
17     memset( flag, true, sizeof(flag) );
18     memset( head, -1, sizeof(head) );
19 }
20 
21 struct Edge
22 {
23     int v, next;
24 } edge[N];
25 
26 void addEdge( int u, int v )
27 {
28     edge[e].v = v;
29     edge[e].next = head[u];
30     head[u] = e++;
31 }
32 
33 void dfs( int u )
34 {
35     dp[u][0] = 0;
36     dp[u][1] = rating[u];
37     for ( int i = head[u]; i != -1; i = edge[i].next )
38     {
39         int v = edge[i].v;
40         dfs(v);
41         dp[u][0] += max( dp[v][0], dp[v][1] );
42         dp[u][1] += dp[v][0];
43     }
44 }
45 
46 int main ()
47 {
48     while ( scanf("%d", &n) != EOF )
49     {
50         for ( int i = 1; i <= n; i++ )
51         {
52             scanf("%d", rating + i);
53         }
54         init();
55         int v, u;
56         while ( scanf("%d%d", &v, &u) != EOF )
57         {
58             if ( v == 0 && u == 0 ) break;
59             addEdge( u, v );
60             flag[v] = false;
61         }
62         int root;
63         for ( int i = 1; i <= n; i++ )
64         {
65             if ( flag[i] )
66             {
67                 root = i;
68                 break;
69             }
70         }
71         dfs(root);
72         int ans = max( dp[root][0], dp[root][1] );
73         printf("%d
", ans);
74     }
75     return 0;
76 }