Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

G. Sum of Prefix Sums

time limit per test

6 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputWe 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.

Input

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$$$).

Output

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

Example

Input

4 4 2 3 2 4 1 1 3 3 7

Output

36

Note

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$$$.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/29/2020 16:15:26 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|