记录编号	48818	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.415 s
提交时间	2012-11-06 16:57:03	内存使用	2.59 MiB

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN=100010;
int F[MAXN][2];
int profit[MAXN],N;
vector<int> map[MAXN];
inline int Max(int a,int b){return a>b?a:b;}
inline void init()
{
	scanf("%d\n",&N);
	for(int i=1;i<=N;i++)
		scanf("%d\n",&profit[i]);
	int x,y;
	for(int i=1;i<=N-1;i++)
	{
		scanf("%d %d\n",&x,&y);
		map[x].push_back(y);
		map[y].push_back(x);
	}
}

void dfs(int k,int f)
{
	F[k][1]=profit[k],F[k][0]=0;int nxt;
	for(unsigned int i=0;i<map[k].size();i++)
	{
		if(map[k][i]==f) continue;
		nxt=map[k][i];dfs(nxt,k);
		F[k][1]+=F[nxt][0];
		F[k][0]+=Max(F[nxt][0],F[nxt][1]);
	}
}

int main()
{
	freopen("profitz.in","r",stdin);
	freopen("profitz.out","w",stdout);
	init(); dfs(1,0);
	printf("%d\n",Max(F[1][0],F[1][1]));
	return 0;
}