记录编号	359990	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	kxxy	是否通过	通过
代码语言	C++	运行时间	0.386 s
提交时间	2016-12-25 21:52:29	内存使用	5.65 MiB

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int maxn=100010;
int n;
struct T
{
	int to,next,from;
}e[maxn<<1];
int head[maxn];
int f[maxn][2];
int val[maxn];
int x,y,cnt=0;
vector<int>v[maxn];
int vis[maxn]={0};

inline void insert(int x,int y)
{
	cnt++;
	e[cnt].to=y;
	e[cnt].from=x;
	e[cnt].next=head[x];
	head[x]=cnt;
}

inline void make_tree(int root)
{
	vis[root]=1;
	for(int i=head[root];i;i=e[i].next)
	{
		int cd=e[i].to;
		if(!vis[cd])
		{
			v[root].push_back(cd);
			make_tree(cd);
		}
	}
}

inline int dp(int root,int choose)
{
	if(f[root][choose]!=-1)
		return f[root][choose];
	if(choose==0)
	{
		f[root][choose]=0;
		for(int i=0;i<v[root].size();i++)
			f[root][0]+=max(dp(v[root][i],0),dp(v[root][i],1));
		return f[root][0];
	}
	else
	{
		f[root][1]=val[root];
		for(int i=0;i<v[root].size();i++)
			f[root][1]+=dp(v[root][i],0);
		return f[root][1];
	}
}

int main()
{
	freopen("profitz.in","r",stdin);
	freopen("profitz.out","w",stdout);
	memset(head,-1,sizeof(head));
	memset(f,-1,sizeof(f));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&val[i]);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		insert(x,y);
		insert(y,x);
	}
	make_tree(1);
	int ans=max(dp(1,0),dp(1,1));
	printf("%d",ans);
	return 0;
}