记录编号	250955	评测结果	AAAAAAAAAA
题目名称	游戏内测	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	2.465 s
提交时间	2016-04-16 15:59:14	内存使用	15.57 MiB

//KZNS
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
//
ifstream fin ("gamebeta.in");
ofstream fout ("gamebeta.out");
const int Nmax = 500003;
typedef long long LL;
typedef pair<LL, LL> pr;
//
int N;
vector<int> gp[Nmax];
int T[Nmax];
LL vd[Nmax][2] = {0};
//
inline bool cmd(pr a, pr b) {
	if (a.second == b.second)
		return a.first > b.first;
	else
		return a.second > b.second;
}
void fir() {
	fin >> N;
	for (int i = 1; i <= N; i++)
		fin >> T[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 DFS(int x) {
	vd[x][0] = 2;
	vector<pr> ls;
	for (int i = 0; i < gp[x].size(); i++) {
		if (!vd[gp[x][i]][0]) {
			DFS(gp[x][i]);
			ls.push_back(make_pair(vd[gp[x][i]][0], vd[gp[x][i]][1]));
		}
	}
	sort(ls.begin(), ls.end(), cmd);
	int adt = T[x];
	for (int i = 0; i < ls.size(); i++) {
		vd[x][0] += ls[i].first;
		adt = max(adt - ls[i].first, ls[i].second);
	}
	vd[x][1] = max(adt - 1, 0);
}
//
int main() {
	int __size__ = 20 << 20;
	char *__p__ = (char*)malloc(__size__) + __size__;
	__asm__("movl %0, %%esp\n" :: "r"(__p__));
	fir();
	int x = 1;
	vd[x][0] = 1;
	vector<pr> ls;
	for (int i = 0; i < gp[x].size(); i++) {
		if (!vd[gp[x][i]][0]) {
			DFS(gp[x][i]);
			ls.push_back(make_pair(vd[gp[x][i]][0], vd[gp[x][i]][1]));
		}
	}
	sort(ls.begin(), ls.end(), cmd);
	int adt = 0;
	for (int i = 0; i < ls.size(); i++) {
		vd[x][0] += ls[i].first;
		adt = max(adt - ls[i].first, ls[i].second);
	}
	vd[x][0]--;
	vd[x][1] = max(adt, T[x]);
	fout << vd[1][0]+vd[1][1];
	return 0;
}
//UBWH