记录编号	287292	评测结果	AAAAAAAAAA
题目名称	[POJ 2342] 猴腮雷	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2016-08-01 17:38:43	内存使用	0.69 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=10010;
void insert(int,int);
void bfs();
int a[maxn],prt[maxn],b[maxn];
struct edge{
	int to;
	edge *prev;
	edge():to(0),prev(NULL){}
}ee[maxn<<1];
int len=0;
edge *last[maxn]={NULL};
int n,f[maxn][2],x,y;
int main(){
#define MINE
#ifdef MINE
	freopen("monk.in","r",stdin);
	freopen("monk.out","w",stdout);
#endif
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		insert(x,y);
		insert(y,x);
	}
	bfs();
	while(n--){
		x=b[n+1];
		f[x][1]+=a[x];
		f[prt[x]][0]+=max(f[x][0],f[x][1]);
		f[prt[x]][1]+=f[x][0];
	}
	printf("%d",max(f[1][0],f[1][1]));
	return 0;
}
void insert(int x,int y){
	ee[len].to=y;
	ee[len].prev=last[x];
	last[x]=&ee[len++];
}
void bfs(){
	b[0]=0;
	queue<int>q;
	q.push(1);
	int y;
	while(!q.empty()){
		int &x=q.front();
		b[++b[0]]=x;
		for(edge *e=last[x];e;e=e->prev){
			y=e->to;
			if(y==prt[x])continue;
			prt[y]=x;
			q.push(y);
		}
		q.pop();
	}
}
/*
6
100 100 10 10 100 100
1 3
4 5
2 3
4 6
3 4
Answer:
400
*/