记录编号	73107	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	raywzy	是否通过	通过
代码语言	C++	运行时间	0.396 s
提交时间	2013-10-20 10:04:56	内存使用	2.60 MiB

#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin("profitz.in");
ofstream fout("profitz.out");
vector<int> adj[100001];
int a[100001];
int N;
int F[100001][2];
void dfs(int D,int fa)
{
	F[D][1]=a[D];F[D][0]=0;
	for(unsigned int i=0;i<adj[D].size();i++)
	{
		if(adj[D][i]==fa) continue;
		dfs(adj[D][i],D);
		F[D][0]+=max(F[adj[D][i]][0],F[adj[D][i]][1]);
		F[D][1]+=F[adj[D][i]][0];
	}
}
int main()
{
	fin>>N;
	int i,A,B;
	for(i=1;i<=N;i++)
		fin>>a[i];
	for(i=1;i<N;i++)
	{
		fin>>A>>B;
		adj[A].push_back(B);
		adj[B].push_back(A);
	}
	dfs(1,0);
	fout<<max(F[1][0],F[1][1])<<endl;
	return 0;
}