记录编号	240931	评测结果	AAAAAAAAAA
题目名称	修剪花卉	最终得分	100
用户昵称	前鬼后鬼的守护	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2016-03-24 08:41:11	内存使用	0.85 MiB

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<iostream>
#include<algorithm>
#define FILE "makeup"
namespace IO{
	char buf[1<<15],*fs,*ft;
	inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int read(){
		int x=0,rev=0,ch=getc();
		while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=getc();}
		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getc();}
		return rev?-x:x;
	}
}using namespace IO;
const int MAXN(16000),D(10);
namespace tree{
	int n,root;
	int par[MAXN+D];
	int f[MAXN+D];
	struct edge{
		int y,next;
		static int tot;
	}e[MAXN*2+D];
	int head[MAXN+D],edge::tot;
	inline void connect(int x,int y){
		int& k=edge::tot;
		e[++k].next=head[x];e[head[x]=k].y=y;
		e[++k].next=head[y];e[head[y]=k].y=x;
	}
}using namespace tree;
void init(){
	root=1;
	n=read();
	for(int i=1;i<=n;i++)
		f[i]=read();
	for(int i=1;i<n;i++)
		connect(read(),read());
}
namespace Stack{
	int stack[MAXN+D],top;
	bool oped[MAXN+D];
}using namespace Stack;
void work(){
	int ans=1<<31;
	oped[stack[top=1]=root]=false;
	while(top){
		int x=stack[top];
		if(oped[x]){
			if(f[x]>ans)
				ans=f[x];
			if(f[x]>0)
				f[par[x]]+=f[x];
			top--;
		}
		else{
			oped[x]=true;
			for(int i=head[x],y;i;i=e[i].next)
				if((y=e[i].y)!=par[x])
					par[y]=x,oped[stack[++top]=y]=false;
		}
	}
	printf("%d\n",ans);
}
int main(){
	freopen("makeup.in","r",stdin);
	freopen("makeup.out","w",stdout);
	init();
	work();
	return 0;
}