记录编号	199817	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	明天	是否通过	通过
代码语言	C++	运行时间	0.300 s
提交时间	2015-10-27 16:30:38	内存使用	4.22 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

struct node
{
	int x,next;
};

const int maxn=100000+1;
int n,ans;
int a[maxn],h[maxn];//a权值
node table[maxn*2];
int left1[maxn],right1[maxn];
int len;
int f[maxn];
bool v[maxn];
int root;

void add1(int i,int j);
void bfs(int root);
int dp(int x);
int main()
{
	freopen("profitz.in","r",stdin);
	freopen("profitz.out","w",stdout);
	
	scanf("%d",&n);
	for (int i=1; i<=n; i++)
	{
		scanf("%d",&a[i]);
	}
	for (int k=1; k<n; k++)
	{
		int i,j;
		scanf("%d%d",&i,&j);
		add1(i,j); add1(j,i);
	}
	bfs(1);

	v[1]=true;
	ans=dp(1);
	
	printf("%d",ans);
	return 0;
}
void add1(int i,int j)
{
	len++;
	table[len].x=j; table[len].next=h[i];
	h[i]=len;
}
void add2(int i,int j)
{
	if (left1[i]==0) left1[i]=j;
	else
	{
		right1[j]=left1[i];
		left1[i]=j;
	}
}
int q[maxn];
int front,tail;
void bfs(int root)
{
	memset(v,0,sizeof(v));
	front=0; tail=1;
	q[tail]=root; v[root]=true;
	while (front!=tail)
	{
		int x;
		front++;
		x=q[front];
		int p=h[x];
		while (p!=0)
		{
			int y;
			y=table[p].x;
			if (!v[y])
			{
				tail++;
				q[tail]=y;
				v[y]=true;
				add2(x,y);
			}
			p=table[p].next;
		}
	}
	memset(v,0,sizeof(v));
}
int dp(int x)
{
	if (x==0) return 0;
	if (f[x]>0) return f[x];
	//不选
	int temp=0;
	int p=left1[x];
	while (p!=0)
	{
		if (!v[p])
		{
			v[p]=true;
			temp+=dp(p);
			v[p]=false;
		}
		p=right1[p];
	}
	if (temp>f[x]) f[x]=temp;
	
	//选
	temp=a[x];
	p=left1[x];
	while (p!=0)
	{
		int q;
		q=left1[p];
		while (q!=0)
		{
			if (!v[q])
			{
				v[q]=true;
				temp+=dp(q);
				v[q]=false;
			}
			q=right1[q];
		}
		p=right1[p];
	}
	 if (temp>f[x]) f[x]=temp;
	
	 return f[x];
}