记录编号	389859	评测结果	AAAAAAAAAAA
题目名称	190.[Ural 1039] 周年纪念聚会	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2017-04-01 08:42:38	内存使用	0.52 MiB

/*kZime*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <algorithm>

using namespace std;
/*-----------------------------------------------------------------------------*/
inline void File_Read() {
#ifndef MYLAB
	freopen("aniv.in", "r", stdin);
	freopen("aniv.out", "w", stdout);
#else
//	freopen("in.txt", "r", stdin);
#endif
}

inline int get_num() {
	int k = 0, f = 1; char c = getchar();
	for(; !isdigit(c); c = getchar())if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k * f;
}

struct edge {
	int fr, to, ne;
	edge(){;}
	edge(int fr_, int to_, int ne_) {
		fr = fr_;
		to = to_;
		ne = ne_;
	}
}e[12333];

int cnt, head[6233], dp[6233][2], n;

inline void add(int to, int fr) {
	e[++cnt] = edge(fr, to, head[fr]), head[fr] = cnt;
	e[++cnt] = edge(to, fr, head[to]), head[to] = cnt;
}

void dfs(int now, int fa) {
	for(int i = head[now]; i; i = e[i].ne) {
		int to = e[i].to;
		if(to == fa) continue;
		dfs(to, now);
		dp[now][1] += dp[to][0];
		dp[now][0] += max(dp[to][1], dp[to][0]);
	}
}

int main() {
	File_Read();
	while(scanf("%d", &n)) {
		if(!n) return 0;
		memset(dp, 0, sizeof(dp));
		for(int i = 1; i <= n; i++) {
			dp[i][1] = get_num();
		}
		for(int i = 1; i < n; i++) {
			add(get_num(), get_num());
		}
		dfs(1, 0);
		printf("%d\n", max(dp[1][1], dp[1][0]));
	}
	
	return 0;
}