Rooted Distances (Re-rooting DP)

Given a tree and a weight a[v] for each vertex. The beauty of vertex v is the sum of dist(u,v)×a[u] over all vertices u. Output the maximum beauty over all vertices.

This site uses a standard input/output protocol.

输入格式

The first line contains n; the second line contains n weights; the next n−1 lines give the edges u v (1-based). Constraints added by this site: 1≤n≤100000, 0≤a[i]≤10^9.

输出格式

Output the maximum beauty.

样例 1

输入：

2
3 4
1 2

输出：

4

样例 2

输入：

3
1 2 3
1 2
2 3

输出：

8

样例 3

输入：

4
0 0 7 1
1 2
2 3
2 4

输出：

16