记录编号	72326	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.718 s
提交时间	2013-10-16 18:47:31	内存使用	4.90 MiB

#include<fstream>
#include<vector>
#include<cmath>
using namespace std;
ifstream fi("profitz.in");
ofstream fo("profitz.out");
int N,benefit[100001];
vector <int> p[100001];
bool boo[100001]={false};
/*
pair <int,int> operator +( pair <int,int> x, pair <int,int> y)
{
	return make_pair(x.first+y.first,x.second+y.second);
}*/
pair <int,int> dfs(int x)//.first为用该点,而.second为不用该点
{
	boo[x]=true;
	//if(p[x].size()==1)return(make_pair(benefit[x],0));
	pair <int,int> tmp,ans;
	ans.first=benefit[x];
	ans.second=0;
	for(int i=0;i<p[x].size();i++)
	if(!boo[p[x][i]])
	{
		tmp=dfs(p[x][i]);
		ans=make_pair(ans.first+tmp.second,ans.second+max(tmp.first,tmp.second));
	}
	return ans;
}
int main()
{
	int i,j,k;
	fi>>N;
	for(i=1;i<=N;i++)fi>>benefit[i];
	for(i=1;i<=N-1;i++)
	{
		fi>>j>>k;
		p[j].push_back(k);
		p[k].push_back(j);
	}
	pair <int,int> tmp;
	tmp=dfs(1);
	fo<<max(tmp.first,tmp.second)<<endl;
	return 0;
}