记录编号	200196	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	旧梦	是否通过	通过
代码语言	C++	运行时间	0.391 s
提交时间	2015-10-28 12:11:21	内存使用	26.25 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=100000+10;
int n,a[maxn];
int son[maxn],s[maxn][51];
LL opt[maxn][2];
struct edge{
	int to,next;
}G[maxn*5];
int tot=0,h[maxn];

inline LL read(){
	LL x=0;char ch;
	while(!isdigit(ch=getchar()));x=ch-48;
	while(isdigit(ch=getchar()))x=x*10+ch-48;
	return x;
}

void add(int x,int y){
	++tot; G[tot].to=y;
	G[tot].next=h[x]; h[x]=tot;
}

void DFS(int x,int fa){
	for (int i=h[x];i;i=G[i].next){
		if (G[i].to==fa) continue;
		son[x]++; s[x][son[x]]=G[i].to;
		DFS(G[i].to,x);
	}
}

LL tree_dp(int x,int val){
	if (opt[x][val]) return opt[x][val];
	opt[x][val]=val==0?0:a[x];
	if (son[x]==0) return opt[x][val];
	if (val==1){
	   for (int i=1;i<=son[x];++i)
	      opt[x][val]+=tree_dp(s[x][i],0);
	}else{
		for (int i=1;i<=son[x];++i)
		   opt[x][val]+=max(tree_dp(s[x][i],1),tree_dp(s[x][i],0));
	}return opt[x][val];
}

int main(){
	freopen("profitz.in","r",stdin);
	freopen("profitz.out","w",stdout);
	n=read();
	for (int i=1;i<=n;++i) a[i]=read();
	for (int i=1;i<n;++i){
		int x=read(),y=read();
		add(x,y); add(y,x);
	}
	DFS(1,-1);
	LL ans=tree_dp(1,0);
	ans=max(ans,tree_dp(1,1));
	printf("%d",ans);
}