HDU 1520 Anniversary Party

題目在這裡：http://acm.hdu.edu.cn/showproblem.php?pid=1520

題解，這是我的備忘錄，沒有任何註釋。

 1 #include <iostream>
 2 #include <vector>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 
 8 /*
 9 dp[i][1] = max(dp[i parent][0] + score[i])
10 dp[i][0] = max(dp[i parent][1], dp[i parent][0])
11 
12 
13 if i 去：則對於其每一個孩子節點j而言，j是不能去的
14     dp[i][1] = sum(dp[j][0]) + score[i];
15 else i 不去：則對於其每一個孩子節點j而言，j可以去可以不去，選擇快樂值較大的方案
16     dp[i][0] = sum(max(dp[j][0], dp[j][1]));
17 */
18 
19 const int MAX_N = 6000;
20 int score[MAX_N + 1];
21 std::vector< std::vector<int> > graph(MAX_N + 1, std::vector<int>(0, 0));
22 int parent[MAX_N + 1];
23 
24 int n;
25 int dp[MAX_N + 1][2];
26 
27 void treeDP(int node)
28 {
29     dp[node][1] = score[node];
30     dp[node][0] = 0;
31 
32     for (int i = 0; i < graph[node].size(); ++i)
33         treeDP(graph[node][i]);
34 
35     for (int i = 0; i < graph[node].size(); ++i)
36     {
37         int child = graph[node][i];
38 
39         dp[node][1] += dp[child][0];
40         dp[node][0] += max(dp[child][0], dp[child][1]);
41     }
42 }
43 
44 int main(int argc, char const *argv[])
45 {
46     while (cin >> n)
47     {
48         memset(score, 0, sizeof(int) * (MAX_N + 1));
49         memset(parent, 0, sizeof(int) * (MAX_N + 1));
50         memset(dp, 0, sizeof(int) * (MAX_N + 1) * 2);
51         for (int i = 1; i <= n; ++i)
52         {
53             cin >> score[i];
54             graph[i].clear();
55         }
56 
57         int l, k;
58         while (true)
59         {
60             cin >> l >> k;
61 
62             if (l == 0 && k == 0)
63                 break;
64             else
65             {    parent[l] = k;
66                 graph[k].push_back(l);
67             }
68         }
69 
70         // find root node
71         int root = 1;
72         while (parent[root] != 0)
73             root = parent[root];
74 
75         treeDP(root);
76 
77         cout << max(dp[root][0], dp[root][1]) << endl;
78     }
79     return 0;
80 }