记录编号	333314	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	Janis	是否通过	通过
代码语言	C++	运行时间	1.132 s
提交时间	2016-10-30 15:29:10	内存使用	18.31 MiB

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

const int maxn = 100000 + 10;
int G[maxn][51], value[maxn], dp[maxn][2], waynum[maxn];
bool vis[maxn][51];
int n;

void Init(){
	scanf("%d",&n);
	for(int i = 1; i <= n; i++)scanf("%d",&value[i]);
	for(int i = 1; i <= n-1; i++){
		int x,y;
		scanf("%d%d",&x,&y);
		G[x][waynum[x]++] = y;
		G[y][waynum[y]++] = x;
	}
}
void DP(int pos){
	int temp(0), temp2(0);
	for(int i = 0; i < waynum[pos]; i++){
		if(!vis[pos][i]){
			for(int j = 0; j < waynum[G[pos][i]]; j++){
				if(G[G[pos][i]][j] == pos){
					vis[G[pos][i]][j] = 1;
					break;
				}
			}
			DP(G[pos][i]);
			temp += max(dp[G[pos][i]][1],dp[G[pos][i]][0]);
			temp2 += dp[G[pos][i]][0];
		}
		dp[pos][0] = temp;
		dp[pos][1] = temp2 + value[pos];
	}
}
int main(){
	#ifndef DEBUG
		string FileName="profitz";
		freopen((FileName+".in").c_str(),"r",stdin);
		freopen((FileName+".out").c_str(),"w",stdout);
	#endif
	Init();
	DP(1);
	printf("%d",max(dp[1][0],dp[1][1]));
}