记录编号	460442	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	Regnig Etalsnart	是否通过	通过
代码语言	C++	运行时间	0.258 s
提交时间	2017-10-17 07:50:12	内存使用	1.82 MiB

#include<cstdio>
#include<vector>
using namespace std;
const int maxn=100001; 
int n,f[maxn][2],vis[maxn],ans,i;
vector<int>G[maxn];
int max(int a,int b){return a>b?a:b;}
void dfs(int now)
{
	vis[now]=1;
	for(int j=0;j<G[now].size();j++)
	{
		int to=G[now][j];
		if(!vis[to])
		{
			dfs(to);
			f[now][0]+=max(f[to][0],f[to][1]);
			f[now][1]+=f[to][0];
		}
	}
	return;
}
int Main()
{
	freopen("profitz.in","r",stdin);freopen("profitz.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&f[i][1]);
	for(i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(1);
	ans=max(f[1][0],f[1][1]);
	printf("%d\n",ans);
	return 0;
}
int main(){;}
int syy=Main();