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

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=100000+10;
int f[maxn][2]={0};
int v[maxn];
int head[maxn]={0};
int fa[maxn];
struct Edge{
	int t,next;
	Edge(){
		next=0;
	}
}E[maxn<<1];
int n;
int edge=1;
inline int max(int x,int y){
	return x>y?x:y;
}
inline void addedge(int x,int y){
	E[edge].t=y,E[edge].next=head[x],head[x]=edge++;
	E[edge].t=x,E[edge].next=head[y],head[y]=edge++;
}
inline int dp(int x,int flag){
	if(flag){
		if(f[x][1])
			return f[x][1];
		else {
			for(int i=head[x];i;i=E[i].next){
				int u=E[i].t;
				if(u!=fa[x])
					f[x][1]+=dp(u,0);
			}
			f[x][1]+=v[x];
			return f[x][1];
		}
	}
	else {
		if(f[x][0])
			return f[x][0];
		else {
			for(int i=head[x];i;i=E[i].next){
				int u=E[i].t;
				if(u!=fa[x])
					f[x][0]+=max(dp(u,0),dp(u,1));
			}
			return f[x][0];
		}
	}
}
inline void dfs(int x,int p){
	fa[x]=p;
	for(int i=head[x];i;i=E[i].next)
		if(p!=E[i].t){
			dfs(E[i].t,x);
		}
}
inline void read(int &x){
	x=0;
	bool flag=0;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')flag=1;c=getchar();}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
	if(flag)
		x=-x;
}
int main(){
	freopen("profitz.in","r",stdin);
	freopen("profitz.out","w",stdout);
	read(n);
	for(int i=1;i<=n;i++)
		read(v[i]);
	int x,y;
	for(int i=1;i<n;i++){
		read(x),read(y);
		addedge(x,y);
	}
	dfs(1,0);
	printf("%d\n",max(dp(1,0),dp(1,1)));
return 0;
}