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

#include<cstdio>

#define maxn 100010

using namespace std;

int n,w[maxn],f[maxn][2],tot,b[maxn];
bool vis[maxn];

struct at{
	int x,y,last;
}a[maxn<<1];

int MAX(int a,int b){ return a>b?a:b; }

void add(int x,int y)
{
	tot++;
	a[tot].x=x;
	a[tot].y=y;
	a[tot].last=b[x];
	b[x]=tot;
	return;
}

void dfs(int x)
{
	vis[x]=1;
	f[x][1]=w[x];
	for(int i=b[x];i;i=a[i].last){
		int v=a[i].y;
		if(!vis[v]){
			dfs(v);
			f[x][1]+=f[v][0];
			f[x][0]+=MAX(f[v][0],f[v][1]);
		}
	}
	return;
}

int main()
{
	freopen("profitz.in","r",stdin);
	freopen("profitz.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&w[i]);
	}
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	dfs(1);
	printf("%d",MAX(f[1][0],f[1][1]));
	return 0;
}