题目链接：http://poj.org/problem?id=2342
题目大意：在一个公司中，每个职员有一个快乐值ai，现在要开一个party，邀请了一个员工就不可能邀请其直属上司，同理邀请了一个人就不可以邀请其的直属员工，
问如何使得这个快乐值达到最大。
题解：对每个结点dp[i][0]表示不邀请这个员工，其子树达到的最大快乐值，dp[i][1]表示邀请i员工其子树达到的最大值。
dp[i][0]=(i的全部员工的max(dp[u][1],dp[u][0)相加，也就是其子员工来或不来的最大快乐值。
dp[i][1]=(i的全部员工的dp[u][0相加，也就是其子员工都不能不来的最大快乐值。
从大boss开始dp，最终结果就是max(dp[root][0],dp[root][1])
代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 6060;
int n, happy[maxn], dp[maxn][2], p[maxn];
vector<int> sons[maxn];
bool vis[maxn];
void dfs(int u) {
if (vis[u]) return;
vis[u] = true;
dp[u][1] = happy[u], dp[u][0] = 0;
for (int i = 0; i < sons[u].size(); i ++) {
int v = sons[u][i];
if (v == p[u]) continue;
dfs(v);
dp[u][1] += dp[v][0];
dp[u][0] += max(dp[v][1], dp[v][0]);
}
}
void test() {
for (int i = 1; i <= n; i ++) {
cout << "dp[" << i << "] = " << dp[i][1] << " , " << dp[i][0] << endl;
}
}
int main() {
while (cin >> n) {
if (!n) break;
fill(p+1, p+1+n, -1);
fill(vis+1, vis+1+n, false);
for (int i = 1; i <= n; i ++) cin >> happy[i];
int a, b;
for (int i = 1; i < n; i ++) {
cin >> a >> b;
p[a] = b;
sons[b].push_back(a);
}
int root = 1;
while (p[root] != -1) root = p[root];
dfs(root);
cout << max(dp[root][1] , dp[root][0]) << endl;
// test();
}
return 0;
}