題目在這裡：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 }
