这道题确实很有意思，Category写个图论我想了半天网络流，最后还是从暴力入手，搜索变记忆化搜索来解决。

1. 首先对于暴力的情况，我们从根节点开始层次遍历，每个点有选和不选两种状态，根据父节点的状态更新获得的最大值，对于6000个节点的树，我猜dfs要死。
2. 对上面这种情况，我们重复考虑了很多次相同的状况，而且我们发现，当父节点b对应的所有节点a_i对应的两个值-选带来收益a1i，不选带来收益a2i确定之后，他的父节点b所带来的收益也就唯一确定了，如果选了b，那么收益就是b的值，否则的话，我们只需要一次遍历a这一层，从每个a1i,a2i中选最大的加到获得的值中即可，而不需要再考虑a以下的层。

换句话说，从下到上进行遍历，我们避免了相同状态的多次遍历，得解

#define ll long long
#define inf 0x3f3f3f3f
#define MAX 100006
#define vec vector<int>
#define P pair<int,int>
#define MOD 100003

int N, a[MAX], dp[MAX][2], x, y, fa[MAX], r = 0;
vec G[MAX];

void memDfs(int v) {
	if (G[v].size() == 0) {//他没有儿子
		dp[v][0] = 0;//0是不选
		dp[v][1] = a[v];//1是选
		return;
	}
	for (int i = 0; i < G[v].size(); i++) {//便利他的每个儿子
		int u = G[v][i];
		memDfs(u);
		dp[v][0] += max(dp[u][0], dp[u][1]); //不选v，那么他的儿子选/不选两种状态中选最好的
		dp[v][1] += dp[u][0]; //选了v就不能选u
	}
}
int main() {
	while (cin >> N) {
		for (int i = 1; i <= N; i++)cin >> a...