记录编号	349593	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	Bravo ChaoS	是否通过	通过
代码语言	C++	运行时间	0.178 s
提交时间	2016-11-15 08:13:55	内存使用	2.99 MiB

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

class input
{
public:
    input& operator >> (int& x)
    {
        char c=' ';x=0;bool flag(false);
        for(;c<'0' || c>'9';c=getchar()) if(c=='-') flag=1;
        for(;c>='0' && c<='9';c=getchar()) x=x*10+c-'0';
        if(flag) x=-x;
        return *this;
    }
}in;

struct Edge
{
    int to,nxt;
    Edge(){}
};

const int maxn=100010;

int n,cnt(0),gs[maxn],s[maxn],head[maxn];
Edge edge[maxn<<1];

void AddEdge(int from,int to)
{
    edge[++cnt].to=to;
    edge[cnt].nxt=head[from];head[from]=cnt;
}

void dfs(int x,int f)
{
    for(int i=head[x],u;i!=-1;i=edge[i].nxt) if(edge[i].to!=f)
    {
        u=edge[i].to;
        dfs(u,x);
        gs[x]+=s[u];
        s[x]+=max(gs[u],s[u]);
    }
}

int main()
{
    freopen("profitz.in","r",stdin);
    freopen("profitz.out","w",stdout);
    
    in>>n;
    for(int i=1;i<=n;++i) in>>gs[i],head[i]=-1;
    for(int i(1),u,v;i<n;++i)
    {
        in>>u>>v;
        AddEdge(u,v); AddEdge(v,u);
    }
    
    dfs(1,0);
    cout<<max(gs[1],s[1])<<endl;
    
    fclose(stdin); fclose(stdout);
    return 0;
}