给你一棵完全由 $$$n$$$ 个顶点组成的树。树是一个具有 $$$n-1$$$ 边的无向连通图。该树的每个顶点 $$$v$$$ 都分配有一个值 $$$a_v$$$。
设 $$$dist(x, y)$$$ 为顶点 $$$x$$$ 和 $$$y$$$ 之间的距离。顶点之间的距离是它们之间的简单路径上的边数。
让我们将树的成本定义为以下值:首先,让我们修复树的某些顶点。让它成为$$$v$$$。那么树的成本就是$$$\sum\limits_{i = 1}^{n} dist(i, v) \cdot a_i$$$。
如果你可以任意选择$$$v$$$,你的任务是计算树的最大可能成本。
输入
第一行包含一个整数 $$$n$$$,即树中的顶点数 ($$$1 \le n \le 2 \cdot 10^5$$$)。
输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$),其中 $$$a_i$$$ 是顶点 $$$i$$$ 的值。
接下来的 $$$n - 1$$$ 行描述了树的一条边。边 $$$i$$$ 由两个整数 $$$u_i$$$ 和 $$$v_i$$$ 表示,即它连接的顶点的标签($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$)。
保证给定的边形成一棵树。
输出
打印一个整数 - 如果您可以选择任何顶点作为 $$$v$$$,则树的最大可能成本。
示例
输入 #1
8 9 4 1 7 10 1 6 5 1 2 2 3 1 4 1 5 5 6 5 7 5 8
输出 #1
121
输入 #2
1 1337
输出 #2
0
注意
第一个例子对应的图片:
你可以选择顶点 $$$3$$$ 作为根,那么答案将是 $$$2 \cdot 9 + 1 \cdot 4 + 0 \cdot 1 + 3 \cdot 7 + 3 \cdot 10 + 4 \cdot 1 + 4 \cdot 6 + 4 \cdot 5 = 18 + 4 + 0 + 21 + 30 + 4 + 24 + 20 = 121$$$。
在第二个示例中,树仅包含一个顶点,因此答案始终为 $$$0$$$。