← 返回题目列表

Codeforces · 1092/F

F. 成本最大的树

中文机器翻译题面 查看原题

给你一棵完全由 $$$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$$$。