记录编号	34218	评测结果	AAAAAAAAAA
题目名称	613.火车站饭店	最终得分	100
用户昵称	权限狗	是否通过	通过
代码语言	C++	运行时间	0.856 s
提交时间	2011-12-05 09:48:23	内存使用	2.27 MiB

#include <fstream>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
ifstream fin("profitz.in");
ofstream fout("profitz.out");
int Data[100001],N,f[100001],g[100001];
bool bo[100001];
class Node
{
public:
	int Name;
	Node *Next;
};
int Max(int o1,int o2)
{
	return (o1>o2?o1:o2);
}
Node *TS[100001],*Last[100001];
void Init()
{
int S,E;
	fin>>N;
	for(int i=1;i<=N;i++)
	{
		fin>>Data[i];
		TS[i]=new Node;Last[i]=new Node;
		Last[i]=TS[i];
	}
	for(int i=1;i<N;i++)
	{
		fin>>S>>E;
		Node *Tmp=new Node;
		Tmp->Name=E;
		Tmp->Next=NULL;
		Last[S]->Next=Tmp;
		Last[S]=Last[S]->Next;
		Tmp=new Node;
		Tmp->Name=S;
		Tmp->Next=NULL;
		Last[E]->Next=Tmp;
		Last[E]=Last[E]->Next;
	}
}

int dp(int pos)
{
int Sum;
	Sum=0;
	bo[pos]=true;
	for(Node *NEXT=TS[pos]->Next ; NEXT!=NULL ; NEXT=NEXT->Next)
		if(bo[NEXT->Name]==false)
		{
			int OOO;
			OOO=dp(NEXT->Name);
			g[pos]+=Max(OOO,g[NEXT->Name]);
			f [pos]+=g[NEXT->Name];
		}
	f[pos]+=Data[pos];
	return f[pos];
}

int main()
{
	Init();
	
	dp(1);
	fout<<(f[1]>g[1]?f[1]:g[1])<<endl;
	fin.close();
	fout.close();
	return 0;
}