记录编号	389069	评测结果	AAAAAAAAAA
题目名称	613.火车站饭店	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.091 s
提交时间	2017-03-30 16:08:45	内存使用	2.69 MiB

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

#define is_num(tmp) (tmp<='9' and tmp>='0')

const int MAXN = 1e5+10;

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

struct EDGE{
	int to, ne;
	
	EDGE(){;}
	EDGE(const int& a, const int& b){to = a, ne = b;}
};

const inline void add_edge(const int&, const int&);
void dfs(int);

EDGE edge[MAXN<<1];
int head[MAXN], tot;
int d[MAXN], v[MAXN];
int f[MAXN][2];
bool visit[MAXN];
int N;

void *Main(){
#ifndef LOCAL
	freopen("profitz.in", "r", stdin);
	freopen("profitz.out", "w", stdout);
#endif
	
	N = in();
	for(int i = 1; i <= N; ++i){
		v[i] = in();
	}
	
	for(int i = 1; i < N; ++i){
		add_edge(in(), in());
	}
	
	dfs(1);
	
	printf("%d", max(f[1][0], f[1][1]));
	
	return NULL;
}
void *Main_(Main());
int main(){;}

const inline void add_edge(const int& fr, const int& to){
#ifdef debug
	printf("%d %d\n", fr, to);
#endif
	edge[++tot] = EDGE(to, head[fr]), head[fr] = tot, ++d[fr];
	edge[++tot] = EDGE(fr, head[to]), head[to] = tot, ++d[to];
	return ;
}

void dfs(int now){
	visit[now] = true;
	
	for(int i = head[now], to; i; i = edge[i].ne){
		to = edge[i].to;
		if(!visit[to]){
			dfs(to);
			f[now][1] += f[to][0];
			f[now][0] += max(f[to][1], f[to][0]);
		}
	}
	
	f[now][1] += v[now];
	
	return ;
}