记录编号	33451	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	zhangyl	是否通过	通过
代码语言	C++	运行时间	0.844 s
提交时间	2011-11-10 18:36:29	内存使用	20.48 MiB

#include<iostream>
#include<fstream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;

ifstream fin("profitz.in");
ofstream fout("profitz.out");

int n;
int g[100002],f[100002];
int num[100002],map[100002][50];

int max(int a,int b) {return a>b?a:b;}

void read1()
{
	fin>>n;
	for (int i=1;i<=n;i++)
	{
		fin>>num[i];
		g[i]=num[i];
	}
	for (int i=1;i<n;i++)
	{
		int x,y;
		fin>>x>>y;
		map[x][++map[x][0]]=y;
		map[y][++map[y][0]]=x;
	}
	
}

void dp(int son,int father)
{
	if (map[son][0]==1 && map[son][1]==father)
	{
		f[son]=0;
		g[son]=num[son];
		return;
	}
	for (int i=1;i<=map[son][0];i++)
	{
		if (map[son][i]!=father){
		dp(map[son][i],son);
		}
	}
	for (int i=1;i<=map[son][0];i++)
	{
		if (map[son][i]!=father)
	    {
		
		f[son]+=max(g[map[son][i]],f[map[son][i]]);
		g[son]+=f[map[son][i]];
	    }
	}
}

int main()
{

	read1();
	dp(1,0);
	fout<<max(f[1],g[1]);
	return 0;
	
}