← 返回题目列表

Codeforces · 1303/G

G. 前缀和的总和

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

我们将数组 $$$[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$$$路径上出现的所有顶点,按照它们出现在路径上的顺序写下这些顶点上写的所有数字,并计算结果序列的前缀和之和。

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

输入

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

输出

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

示例

输入 #1

4
4 2
3 2
4 1
1 3 3 7

输出 #1

36

注意

第一个示例中的最佳路径是从顶点 $$$3$$$ 到顶点 $$$1$$$。它给出序列$$$[3, 3, 7, 1]$$$,前缀和的总和是$$$36$$$。