记录编号	199944	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.411 s
提交时间	2015-10-27 19:34:04	内存使用	2.70 MiB

#include <fstream>
#include <vector>
#include <algorithm>
#define N 100010
using namespace std;
int n;
vector<int > G[N];
bool l[N]={0};
int v[N]={0};
int f[N][2]={0};
int INF=(1<<30);
ifstream in("profitz.in");
ofstream out("profitz.out");
void DFS(int u)
{
	int i,v;
	l[u]=1;
	for(i=0;i<G[u].size();i++)
	{
		v=G[u][i];
		if(!l[v])
		{
			DFS(v);
		    f[u][1]+=f[v][0];
		    f[u][0]+=max(f[v][0],f[v][1]);
		}
	}
}
void read()
{
	int i,a,b;
	in>>n;
	for(i=1;i<=n;i++)in>>v[i];
	for(i=1;i<n;i++)
	{
		in>>a>>b;
		//out<<a<<' '<<b<<endl;
		G[a].push_back(b);
		G[b].push_back(a);
	}
}
void work()
{
	int i,ans;
	for(i=1;i<=n;i++)
	{
		f[i][0]=0;
		f[i][1]=v[i];
	}
	DFS(1);
	ans=max(f[1][0],f[1][1]);
	out<<ans<<endl;
}
int main()
{
	read();
	work();
	return 0;
}