记录编号	199627	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	0.377 s
提交时间	2015-10-27 07:15:08	内存使用	4.60 MiB

#define Max(a,b)((a)>(b)?(a):(b))

#include<vector>
#include<cstdio>

using namespace std;

bool vis[100010];
int ver[100010],n;
int first[100010],tot;
vector<int>son[100010];
int f[100010][2];

struct Edge{
	int v,next;
}edge[200010];

void Add(int u,int v)
{
	edge[++tot].v=v;
	edge[tot].next=first[u];
	first[u]=tot;
}

void Build(int rt)
{
	vis[rt]=true;
	for(int i=first[rt];i;i=edge[i].next){
		if(!vis[edge[i].v]){
			Build(edge[i].v);
			son[rt].push_back(edge[i].v);
		}
	}
}

void Tree_Dp(int rt)
{
	f[rt][1]=ver[rt];
	for(int i=0,r=son[rt].size();i<r;i++){
		Tree_Dp(son[rt][i]);
		f[rt][0]+=Max(f[son[rt][i]][1],f[son[rt][i]][0]);
		f[rt][1]+=f[son[rt][i]][0];
	}
}

int main()
{
	freopen("profitz.in","r",stdin);
	freopen("profitz.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&ver[i]);
	for(int i=1,u,v;i<n;i++){
		scanf("%d%d",&u,&v);
		Add(u,v);Add(v,u);
	}
	Build(1);Tree_Dp(1);
	printf("%d",Max(f[1][0],f[1][1]));
}