记录编号	200167	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.496 s
提交时间	2015-10-28 08:40:23	内存使用	3.45 MiB

// KZ's
#include <cstdio>
#include <vector>
using namespace std;
int v[100003]={0};
vector <int> mp[100003],ls;
bool ud[100003]={0};
long long f[100003][2]={0};
int main() {
	freopen("profitz.in","r",stdin);
	freopen("profitz.out","w",stdout);
	int n,a,b;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&v[i]);
	for (int i=1;i<n;i++) {
		scanf("%d%d",&a,&b);
		mp[a].push_back(b);
		mp[b].push_back(a);
	}
	ud[1]=true;
	ls.push_back(1);
	for (int i=0;i<ls.size();i++) {
		int u=ls[i];
		for (int j=0;j<mp[u].size();j++)
			if (!ud[mp[u][j]]) {
				ls.push_back(mp[u][j]);
				ud[mp[u][j]]=true;
			}
			else
				mp[u][j]=0;
	}
	for (int i=ls.size()-1;i>0;i--) {
		int uu=ls[i];
		f[uu][1]=v[uu];
		f[uu][0]=0;
		for (int j=0;j<mp[uu].size();j++) {
			f[uu][1]+=f[mp[uu][j]][0];
			f[uu][0]+=max(f[mp[uu][j]][1],f[mp[uu][j]][0]);
		}
	}
	f[1][1]=v[1];
	for (int j=0;j<mp[1].size();j++) {
		f[1][1]+=f[mp[1][j]][0];
		f[1][0]+=max(f[mp[1][j]][1],f[mp[1][j]][0]);
	}
	printf("%lld",f[1][1]>f[1][0]?f[1][1]:f[1][0]);
	return 0;
}
// UBWH