记录编号	240949	评测结果	AAAAAAAAAA
题目名称	修剪花卉	最终得分	100
用户昵称	ZXCVBNM_1	是否通过	通过
代码语言	C++	运行时间	0.019 s
提交时间	2016-03-24 09:41:49	内存使用	0.86 MiB

#include<bits/stdc++.h>
using namespace std;
#define MAXN 16010
#define INF 2147483647
struct node
{
    int begin,end,next;
}edge[MAXN*2];
int cnt,Head[MAXN],f[MAXN],w[MAXN];
void addedge(int bb,int ee)
{
    edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].next=Head[bb];Head[bb]=cnt;
}
void addedge1(int bb,int ee)
{
    addedge(bb,ee);addedge(ee,bb);
}
void Tdp(int u,int fa)
{
    int i,v;
    f[u]=w[u];
    for(i=Head[u];i!=-1;i=edge[i].next)
    {
        v=edge[i].end;
        if(v==fa)continue;
        Tdp(v,u);
        if(f[v]>0)f[u]+=f[v];
    }
}
int main()
{
    freopen("makeup.in","r",stdin);
    freopen("makeup.out","w",stdout);
    int n,i,bb,ee,MAX;
    scanf("%d",&n);
    memset(f,0,sizeof(f));
    for(i=1;i<=n;i++)scanf("%d",&w[i]),f[i]=INF;
    memset(Head,-1,sizeof(Head));cnt=1;
    for(i=1;i<n;i++)
    {
        scanf("%d %d",&bb,&ee);addedge1(bb,ee);
    }
    Tdp(1,0);
    MAX=-1;
    for(i=1;i<=n;i++)MAX=max(MAX,f[i]);
    printf("%d",MAX);
    fclose(stdin);
    fclose(stdout);
    return 0;
}