题意描述：
在大家的三连助攻下，TT 一举获得了超级多的猫咪，因此决定开一间猫咖，将快乐与大家一同分享。并且在开业的那一天，为了纪念这个日子，TT 在猫咖门口种了一棵苹果树。
一年后，苹果熟了，到了该摘苹果的日子了。
已知树上共有 N 个节点，每个节点对应一个快乐值为 w[i] 的苹果，为了可持续发展，TT 要求摘了某个苹果后，不能摘它父节点处的苹果。
TT 想要令快乐值总和尽可能地大，你们能帮帮他吗？
Input
结点按 1～N 编号。
第一行为 N (1 ≤ N ≤ 6000) ，代表结点个数。
接下来 N 行分别代表每个结点上苹果的快乐值 w[i]（-128 ≤ w[i] ≤ 127)。
接下来 N-1 行，每行两个数 L K，代表 K 是 L 的一个父节点。
输入有多组，以 0 0 结束。
Output
每组数据输出一个整数，代表所选苹果快乐值总和的最大值。
输入样例
7
1
1
1
1
1
1
1
1 3
7 4
2 3
4 5
6 4
3 5
0 0
思路：
树形DP
定状态： dp[i][1] 表示取节点 dp[i][0]不取
从根节点dfs进行状态转移：
dp[i][0] += max（dp[j][0],dp[j][1]）
dp[i][1] += dp[j][0]
代码：
1 #include<iostream> 2 #include<vector> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 vector<int> son[6010]; 8 int w[6010], f[6010][2]; 9 bool is_son[6010], vis[6010]; 10 int n, a, b, father; 11 12 void dfs(int x) 13 { 14 if (vis[x]) return; 15 16 f[x][0] = 0; 17 f[x][1] = w[x]; 18 for (vector<int>::iterator it = son[x].begin(); it != son[x].end(); it++) 19 { 20 dfs(*it); 21 f[x][0] += max(f[*it][0], f[*it][1]); 22 f[x][1] += f[*it][0]; 23 } 24 25 vis[x] = 1; 26 } 27 28 int main() 29 { 30 while (cin >> n) 31 { 32 if (n == 0) break; 33 memset(is_son, 0, sizeof is_son); 34 memset(vis, 0, sizeof vis); 35 memset(f, 0, sizeof f); 36 for (int i = 1; i <= n; i++) 37 cin >> w[i]; 38 39 for (int i = 1; i < n; i++) 40 { 41 cin >> a >> b; 42 son[b].push_back(a); 43 is_son[a] = 1; 44 } 45 46 47 for(int i=1;i<=n;i++) 48 if (!is_son[i]) 49 { 50 father = i; 51 break; 52 } 53 dfs(father); 54 cout << max(f[father][0], f[father][1]) << endl; 55 } 56 57 }