CF1303G.Sum of Prefix Sums

We define the sum of prefix sums of an array $[s_1, s_2, \dots, s_k]$ as $s_1 + (s_1 + s_2) + (s_1 + s_2 + s_3) + \dots + (s_1 + s_2 + \dots + s_k)$.

You are given a tree consisting of $n$ vertices. Each vertex $i$ has an integer $a_i$ written on it. We define the value of the simple path from vertex $u$ to vertex $v$ as follows: consider all vertices appearing on the path from $u$ to $v$, write down all the numbers written on these vertices in the order they appear on the path, and compute the sum of prefix sums of the resulting sequence.

Your task is to calculate the maximum value over all paths in the tree.

我们定义数组 $[s_1, s_2, \dots, s_k]$ 的前缀和之和为

$$s_1 + (s_1 + s_2) + (s_1 + s_2 + s_3) + \dots + (s_1 + s_2 + \dots + s_k).$$

给你一棵包含 $n$ 个顶点的树。每个顶点 $i$ 上写有一个整数 $a_i$。我们定义从顶点 $u$ 到顶点 $v$ 的简单路径的值如下：考虑从 $u$ 到 $v$ 的路径上出现的所有顶点，按它们在路径上出现的顺序写下这些顶点上的所有数字，然后计算所得序列的前缀和之和。

你的任务是计算树中所有路径的最大值。

The first line contains one integer $n$ ($2 \le n \le 150000$) — the number of vertices in the tree.

Then $n - 1$ lines follow, representing the edges of the tree. Each line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), denoting an edge between vertices $u_i$ and $v_i$. It is guaranteed that these edges form a tree.

The last line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 10^6$).

第一行包含一个整数 $n$（$2 \le n \le 150000$）——树中顶点的数量。

接下来是 $n - 1$ 行，表示树的边。每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$），表示顶点 $u_i$ 与 $v_i$ 之间存在一条边。保证这些边构成一棵树。

最后一行包含 $n$ 个整数 $a_1$、$a_2$、…、$a_n$（$1 \le a_i \le 10^6$）。

Print one integer — the maximum value over all paths in the tree.

输出一个整数——树中所有路径的最大值。

The best path in the first example is from vertex $3$ to vertex $1$. It gives the sequence $[3, 3, 7, 1]$, and the sum of prefix sums is $36$.

第一个样例中的最优路径是从顶点 $3$ 到顶点 $1$。该路径给出的序列为 $[3, 3, 7, 1]$，其前缀和之和为 $36$。