CF1092F.Tree with Maximum Cost

You are given a tree consisting exactly of $n$ vertices. Tree is a connected undirected graph with $n-1$ edges. Each vertex $v$ of this tree has a value $a_v$ assigned to it.

Let $dist(x, y)$ be the distance between the vertices $x$ and $y$. The distance between the vertices is the number of edges on the simple path between them.

Let's define the cost of the tree as the following value: firstly, let's fix some vertex of the tree. Let it be $v$. Then the cost of the tree is $\sum\limits_{i = 1}^{n} dist(i, v) \cdot a_i$.

Your task is to calculate the maximum possible cost of the tree if you can choose $v$ arbitrarily.

给你一棵恰好包含 $n$ 个顶点的树。树是一种具有 $n-1$ 条边的连通无向图。该树的每个顶点 $v$ 都被赋予一个值 $a_v$。

令 $dist(x, y)$ 表示顶点 $x$ 与 $y$ 之间的距离。顶点间的距离定义为它们之间简单路径上的边数。

我们定义这棵树的代价如下：首先，选定树中的某个顶点，记为 $v$；则该树的代价为 $\sum\limits_{i = 1}^{n} dist(i, v) \cdot a_i$。

你的任务是：在可以任意选择顶点 $v$ 的前提下，计算该树可能达到的最大代价。

The first line contains one integer $n$, the number of vertices in the tree ($1 \le n \le 2 \cdot 10^5$).

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$), where $a_i$ is the value of the vertex $i$.

Each of the next $n - 1$ lines describes an edge of the tree. Edge $i$ is denoted by two integers $u_i$ and $v_i$, the labels of vertices it connects ($1 \le u_i, v_i \le n$, $u_i \ne v_i$).

It is guaranteed that the given edges form a tree.

第一行包含一个整数 $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$）。

保证所给的边构成一棵树。

Print one integer — the maximum possible cost of the tree if you can choose any vertex as $v$.

输出一个整数——如果你可以任选一个顶点作为 $v$，则树可能的最大代价。

Picture corresponding to the first example:

You can choose the vertex $3$ as a root, then the answer will be $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$.

In the second example tree consists only of one vertex so the answer is always $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$。