题目描述

给定一棵以 1 为根的无向树，每个节点有权值，权值可以是正数、0、负数。 一棵节点的子树定义：节点自身 + 它所有后代节点。 求所有子树中，子树内所有点权相加的最大值。

输入描述

第一行一个整数 $n$，代表树上节点总数。 第二行 $n$ 个整数，第 $i$ 个数代表编号 $i$ 节点的权值。 接下来 $n-1$ 行，每行两个整数 $u,v$，代表树上双向边 $u \leftrightarrow v$。

输出描述

输出所有子树权值和的最大值。

输入样例

5
-10 -1 5 -2 4
1 2
1 3
3 4
3 5

输出样例

7

样例解释： 1 号整树总和：$-10-1+5-2+4=-4$ 3 号子树总和：$5-2+4=7$ 2 号：$-1$，4 号：$-2$，5 号：$4$

数据范围

$1 \le n \le 1000$ 每个节点权值满足 $-100 \le w \le 100$