记录编号	383814	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.162 s
提交时间	2017-03-16 16:10:31	内存使用	2.21 MiB

/*kZime*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#define MAXN 100233
using namespace std;
inline int read() {
	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;
}
/*-----------------------------------------------------------------------------*/
 
stack <int> abfs;
 
struct node{
	int fa;
	vector<int> ch;
}nd[MAXN];
int w[MAXN], n, f[MAXN][2];
 
 
void f_ab() {
	queue<int> bfs;
	bfs.push(1);
	while(!bfs.empty()) {
		int x = bfs.front();
		bfs.pop();
		abfs.push(x);
		for(int i = 0; i < nd[x].ch.size(); i++) {
			if(nd[x].fa == nd[x].ch[i]) continue;
			nd[nd[x].ch[i]].fa = x;
			bfs.push(nd[x].ch[i]);
		}
	}
}
 
int AC() {
#ifndef MYLAB
	freopen("profitz.in", "r", stdin);
	freopen("profitz.out", "w", stdout);
#else
	freopen("in.txt", "r", stdin);
#endif
	n = read();
	
	for(int i = 1; i <= n; i++) {
		w[i] = read();
		f[i][1] = w[i];
	}
	
	for(int i = 1; i < n; i++) {
		int x = read();
		int y = read();
		nd[x].ch.push_back(y);
		nd[y].ch.push_back(x);
	}
 
	f_ab();
 
	while(!abfs.empty()) {
		int x = abfs.top();
		abfs.pop();
		for(int i = 0; i < nd[x].ch.size(); i++) {
			if(nd[x].ch[i] == nd[x].fa)continue;
			f[x][1] += f[nd[x].ch[i]][0];
			f[x][0] += max(f[nd[x].ch[i]][1], f[nd[x].ch[i]][0]);
		}
	}
	printf("%d", max(f[1][0], f[1][1]));
 
	return 0;
}
int HA = AC();
int main(){;}