1304: 子树权重（tree）
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：11
解决：1
题目描述
给定一棵 n 个节点的树，每个节点有一个权重 wi。定义一棵子树的权重为该子树中所有节点权重之和。请你计算这棵树中所有子树（包括整棵树）的权重的最大值。
输入
第一行一个整数 n(1≤n≤10^5）。
第二行
n 个整数
w1,w2,...,wn（10^3≤wi≤10^3）。
接下来 n−1 行，每行两个整数 u,v。
u,v，表示一条边。
样例输入 复制
5
-1 2 3 -2 4
1 2
1 3
2 4
2 5样例输出 复制
6