CF1092F Tree with Maximum Cost

给定一棵恰好有 $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 \times 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 2 \times 10^5$），其中 $a_i$ 表示第 $i$ 个顶点的权值。 接下来的 $n-1$ 行，每行描述一条树的边。第 $i$ 条边由两个整数 $u_i$ 和 $v_i$ 表示，表示该边连接顶点 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$）。 保证给定的边构成一棵树。

输出一个整数，表示可以任意选择 $v$ 时，树的最大可能代价。

第一个样例对应的树结构如下图所示： 你可以选择顶点 $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$。 由 ChatGPT 4.1 翻译