记录编号	406844	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.206 s
提交时间	2017-05-20 07:39:26	内存使用	1.93 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 1e5 + 10;

inline int in(void){ 
	char tmp = getchar();
	int res = 0;
	while(!isdigit(tmp)) tmp = getchar();
	while(isdigit(tmp))
		res = (res + (res << 2) << 1) + (tmp ^ 48),
		tmp = getchar();
	return res;
}

struct EDGE{ 
	int to;
	EDGE *ne;

	EDGE(){ 
		ne = NULL;
	}

	EDGE(int _to, EDGE* _ne){ 
		to = _to, ne = _ne;
	}
};

inline void add_edge(int fr, int to);
void dfs(int u);

EDGE *head[MAXN];
int N, val[MAXN];
int f[MAXN][2];
bool vis[MAXN];

int main(){ 
#ifndef LOCAL
	freopen("profitz.in", "r", stdin);
	freopen("profitz.out", "w", stdout);
#else
	freopen("test.in", "r", stdin);
#endif
	N = in();
	for(int i = 1; i <= N; ++i) val[i] = in();
	for(int i = 1; i < N; ++i){ 
		int a = in(), b = in();
		add_edge(a, b);
	}

	dfs(1);

	printf("%d\n", max(f[1][1], f[1][0]));
	return 0;
}

inline void add_edge(int fr, int to){ 
	static EDGE *now;
	now = new EDGE(to, head[fr]), head[fr] = now;
	now = new EDGE(fr, head[to]), head[to] = now;
}

void dfs(int u){ 
	int v;
	vis[u] = true;
	for(EDGE *now = head[u]; now; now = now->ne){ 
		if(vis[v = now->to]) continue;
		dfs(v);
		f[u][1] += f[v][0];
		f[u][0] += max(f[v][1], f[v][0]);
	}

	f[u][1] += val[u];
	return ;
}