我们将数组 $$$[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$$$。