记录编号	33037	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	0.439 s
提交时间	2011-11-09 13:26:31	内存使用	21.01 MiB

#include<iostream>
#include<fstream>
#include<cstdlib>
#include<cmath>

using namespace std;

const int oo=0x7fffffff;

int n,sum[100001],sumx[100001],sumy[100001],Map[100001][51];
bool f[100001];

int dp(int fl,int v)
{
	int i,j,k;
	if(sumx[fl]&&v==1)
		return sumx[fl];
	if(sumy[k]&&v==0)
		return sumy[fl];
	sumx[fl]=sum[fl];
	for(i=1;i<=Map[fl][0];i++)
		if(!f[Map[fl][i]])
		{
			f[Map[fl][i]]=true;
			j=dp(Map[fl][i],1);
			k=dp(Map[fl][i],0);
			sumx[fl]+=k;
			sumy[fl]+=max(k,j);
		}
	if(v==1)
		return sumx[fl];
	else
		return sumy[fl];
}

int main()
{
	int i,x,y;
	ifstream fin("profitz.in");
	ofstream fout("profitz.out");
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>sum[i];
	for(i=1;i<n;i++)
	{
		fin>>x>>y;
		Map[x][0]++;
		Map[y][0]++;
		Map[x][Map[x][0]]=y;
		Map[y][Map[y][0]]=x;
	}
	f[1]=true;
	fout<<max(dp(1,1),dp(1,0))<<endl;
	fin.close();
	fout.close();
	return 0;
}