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

#include<cstdio>
#include<iostream>
using namespace std;
int head[100005],tot,n;
int f[100005][3],w[100005];
bool vis[100005];
struct node{
	int x,y,next;
}jie[300000];
void add(int x,int y){
	jie[++tot].y=y; jie[tot].next=head[x]; head[x]=tot;
}
void dfs(int x){
   vis[x]=1;
   f[x][1]=w[x]; f[x][0]=0;
   for(int i=head[x];i;i=jie[i].next){
		int lin=jie[i].y;
		if(!vis[lin]){
          dfs(lin);
		  f[x][1]+=f[lin][0];
		  f[x][0]+=max(f[lin][0],f[lin][1]);
		}
   }
}
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][1],f[1][0]));
	//getchar();getchar();
	return 0;
}