hdu 1520：http://acm.hdu.edu.cn/showproblem.php?pid=1520

每个节点有权值，子节点和父节点不能同时选，问最后能选的最大价值是多少？

f[u][0]：表示当前节点没选。那么f[u][0] += sum{max(f[v][0], f[v][1]) : v是u的子节点};

f[u][1]；表示当前节点选了。那么f[u][1] += sum{f[v][0] : v是u的子节点};

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int maxn = 6666;

int f[maxn][2], n, p, q, val, root;
bool vis[maxn];
vector<int> son[maxn];

void dfs(int u) {
	for (int i = 0; i < son[u].size(); i++) {
		int v = son[u][i];
		dfs(v);
		f[u][0] += max(f[v][1], f[v][0]);
		f[u][1] += f[v][0];
	}
}

void work() {
	memset(f, 0, sizeof(f));
	for (int i = 1; i <= n; i++) {
		scanf("%d", &val);
		f[i][1] = val;
		f[i][0] = 0;
		son[i].clear();
	}
	memset(vis, false, sizeof(vis));
	while (scanf("%d %d", &p, &q)) {
		if (p == 0 && q == 0)
			break;
		son[q].push_back(p);
		vis[p] = true;
	}
	for (int i = 1; i <= n; i++) {
		if (vis[i] == false) {
			root = i; break;
		}
	}
	dfs(root);
	printf("%d\n", max(f[root][0], f[root][1]));
}

int main() {
	while (~scanf("%d", &n)) {
		work();
	}
	return 0;
}