记录编号	72020	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	饺子	是否通过	通过
代码语言	C++	运行时间	0.668 s
提交时间	2013-10-14 22:32:12	内存使用	8.58 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cstdlib>
#include<ctime>
using namespace std;
const int lim=100011;
int m,root,z;
int d[lim];
struct self{int x,y;}s[lim*2];
int first[lim*2],nxt[lim*2];
 
vector<int>g[lim];
int a,b,c;
int f[lim][2];
bool flag[lim];
 
void maketree(int i)
{
    flag[i]=1;
    for(int e=first[i];e!=-1;e=nxt[e])
    if(!flag[s[e].y])
    {
        g[i].push_back(s[e].y);
        maketree(s[e].y);
    }
}
 
int work(int i,int chosen)
{
    if(f[i][chosen]!=-1)return f[i][chosen];
    if(chosen==0)
    {
        f[i][chosen]=0;
        for(int k=0;k<g[i].size();k++)
        f[i][chosen]+=max(work(g[i][k],0),work(g[i][k],1));
        return f[i][chosen];
    }
    f[i][chosen]=d[i];
    for(int k=0;k<g[i].size();k++)f[i][chosen]+=work(g[i][k],0);
    return f[i][chosen];
}
        
        
int main()
{
    srand(time(NULL));
    freopen("profitz.in","r",stdin);freopen("profitz.out","w",stdout);
    memset(first,-1,sizeof(first));memset(nxt,-1,sizeof(nxt));memset(f,-1,sizeof(f));
    scanf("%d",&m);
    for(a=1;a<=m;a++)scanf("%d",&d[a]);
    for(a=1;a<m;a++)
    {
        scanf("%d%d",&s[a].x,&s[a].y);
        s[a+m].x=s[a].y;s[a+m].y=s[a].x;
        nxt[a]=first[s[a].x];first[s[a].x]=a;
        nxt[a+m]=first[s[a].y];first[s[a].y]=a+m;
    }
    
    root=rand()%m+1;
    maketree(root);
 
    
    z=max(work(root,0),work(root,1));
    cout<<z<<'\n';
    return 0;
}