洛谷1122 最大子树和

大水题，题意就跟题目名一样，决策就是对于节点 $x$ 是否取当前搜到的儿子 $y$ ，显然要当前子树和要大于0我们才会取，然后dfs即可。

方程式：

$$f[x]+=max(f[y],0)$$

struct Edge{
    int next,to;
} edge[32005];
int s[16005],n,m,a,b,c,cnt,head[16005],w[16005],ans;

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x,int f)
{
    w[x]=s[x];
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==f) continue;
        dfs(y,x);
        if (w[y]>0) w[x]+=w[y];
    }
    ans=max(ans,w[x]);
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i]=read();
    for (int i=1;i<n;i++)
    {
        a=read(); b=read();
        add(a,b);
        add(b,a);
    }
    dfs(1,0);
    printf("%d",ans);
    return 0;
}