记录编号	240897	评测结果	AAAAAAAAAA
题目名称	修剪花卉	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.024 s
提交时间	2016-03-24 08:06:44	内存使用	0.64 MiB

//KZNS
#include <fstream>
#include <utility>
#include <vector>
using namespace std;
//
ifstream fin ("makeup.in");
ofstream fout ("makeup.out");
typedef pair<int, int> pr;
//
int N;//16000
int v[16003] = {0};
vector<int> gp[16003];
int mz[16003] = {0};
bool ud[16003] = {0};
int ED = 0;
//
void rin() {
	fin >> N;
	for (int i = 1; i <= N; i++)
		fin >> v[i];
	int a, b;
	for (int i = 1; i < N; i++) {
		fin >> a >> b;
		gp[a].push_back(b);
		gp[b].push_back(a);
	}
}
void dtr(int x) {
	ud[x] = true;
	mz[x] = v[x];
	for (int i = 0; i < gp[x].size(); i++) {
		if (!ud[gp[x][i]]) {
			dtr(gp[x][i]);
			mz[x] = max(mz[x], mz[x] + mz[gp[x][i]]);
		}
	}
	ED = max(ED, mz[x]);
}
//
int main() {
	rin();
	dtr(1);
	fout << ED;
	return 0;
}
//UBWH