记录编号	282038	评测结果	AAAAAAAAAA
题目名称	613.火车站饭店	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.121 s
提交时间	2016-07-13 06:08:54	内存使用	3.59 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
namespace mine{
	inline int getint(){
		static int __c,__x;
		static bool __neg;
		__x=0;
		__neg=false;
		do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
		if(__c=='-'){
			__neg=true;
			__c=getchar();
		}
		for(;__c>='0'&&__c<='9';__c=getchar())__x=__x*10+(__c^48);
		if(__neg)return -__x;
		return __x;
	}
	inline long long getll(){
		static long long __x;
		static char __c;
		static bool __neg;
		__x=0;
		__neg=false;
		do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
		if(__c=='-'){
			__neg=true;
			__c=getchar();
		}
		for(;__c>='0'&&__c<='9';__c=getchar())__x=__x*10+(__c^48);
		if(__neg)return -__x;
		return __x;
	}
	inline unsigned long long getull(){
		static unsigned long long __x;
		static char __c;
		__x=0;
		do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
		for(;__c>='0'&&__c<='9';__c=getchar())__x=__x*10+(__c^48);
		return __x;
	}
	inline void putint(int __x){
		static int __a[40],__i,__j;
		static bool __neg;
		__neg=__x<0;
		if(__neg)__x=-__x;
		__i=0;
		do{
			__a[__i++]=__x%10+48;
			__x/=10;
		}while(__x);
		if(__neg)putchar('-');
		for(__j=__i-1;__j^-1;__j--)putchar(__a[__j]);
	}
	inline void putll(long long __x){
		static int __a[40],__i,__j;
		static bool __neg;
		__neg=__x<0;
		if(__neg)__x=-__x;
		__i=0;
		do{
			__a[__i++]=__x%10+48;
			__x/=10;
		}while(__x);
		if(__neg)putchar('-');
		for(__j=__i-1;__j^-1;__j--)putchar(__a[__j]);
	}
	inline void putull(unsigned long long __x){
		static int __a[40],__i,__j;
		__i=0;
		do{
			__a[__i++]=__x%10+48;
			__x/=10;
		}while(__x);
		for(__j=__i-1;__j^-1;__j--)putchar(__a[__j]);
	}
}
using namespace mine;
const int maxn=100100;
template<typename T>
struct queue{
	T a[maxn];
	int head,tail;
public:
	inline queue(){
		head=tail=0;
	}
	inline void clear(){
		queue();
	}
	inline int size(){
		return head>tail?tail-head+maxn:tail-head;
	}
	inline bool empty(){
		return size()==0;
	}
	inline void push(const T &n){
		a[tail++]=n;
		if(tail==maxn)tail=0;
	}
	inline T pop(){
		T n=a[head++];
		if(head==maxn)head=0;
		return n;
	}
	inline T &front(){
		return a[head];
	}
	inline T &back(){
		return a[tail-1];
	}
};
void insert(int,int);
void bfs();
int a[maxn],prt[maxn],b[maxn];
struct edge{
	int to;
	edge *prev;
	edge():to(0),prev(NULL){}
}ee[maxn<<1];
int len=0;
edge *last[maxn]={NULL};
int n,f[maxn][2],x,y;
int heap[maxn];
inline int MAIN(){
#define MINE
#ifdef MINE
	freopen("profitz.in","r",stdin);
	freopen("profitz.out","w",stdout);
#endif
	n=getint();
	for(int i=1;i<=n;i++)a[i]=getint();
	for(int i=1;i<n;i++){
		x=getint();
		y=getint();
		insert(x,y);
		insert(y,x);
	}
	bfs();
	while(n--){
		x=b[n+1];
		f[x][1]+=a[x];
		f[prt[x]][0]+=max(f[x][0],f[x][1]);
		f[prt[x]][1]+=f[x][0];
	}
	putint(max(f[1][0],f[1][1]));
	return 0;
}
inline void insert(int x,int y){
	ee[len].to=y;
	ee[len].prev=last[x];
	last[x]=&ee[len++];
}
inline void bfs(){
	b[0]=0;
	queue<int>q;
	q.push(1);
	int y;
	while(!q.empty()){
		int &x=q.front();
		b[++b[0]]=x;
		for(edge *e=last[x];e;e=e->prev){
			y=e->to;
			if(y==prt[x])continue;
			prt[y]=x;
			q.push(y);
		}
		q.pop();
	}
}
int hzoier=MAIN();
int main(){;}
/*
6
100 100 10 10 100 100
1 3
4 5
2 3
4 6
3 4
Answer:
400
*/