B. Back to the Fruit Forest
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the Tunari Park, there is a magical tree with fruits that grow at each node, including the root. Every night, each fruit produces one milliliter of magical juice and the fruit moves one node closer to the root. The fruit is harvested exactly after it has produced magical juice at the root of the tree. The root is node 1. A tree is a connected graph that contains no cycles.

Mr. Pozo, Armando's teacher, is a master of mystical arts. Pozo has such great mastery over magical trees that he can choose which node will be the root.

The goal is to determine the maximum amount of milliliters of magical juice that can be obtained by choosing the optimal node as the root. Mr. Pozo already knows the answer, but if you manage to find the answer, he will reward you with "Api con Pastel" (a delicious bolivian breakfast).

Input

An integer $$$n$$$ representing the number of nodes, $$$2 \leq n \leq 10^5$$$. Then, $$$n-1$$$ pairs of numbers $$$a_i, b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$) representing the connections between the nodes. It is guaranteed that there is a simple path between each pair of nodes. Then, $$$n$$$ numbers $$$f_i$$$ ($$$1 \leq f_i \leq 10^5$$$) representing the number of fruits at each node.

Output

An integer representing the maximum amount of milliliters of magical juice that can be obtained by choosing the optimal node as the root.

Examples
Input
2
1 2
1 2
Output
5
Input
2
1 2
2 1
Output
5
Input
4
1 2
1 3
3 4
2 3 2 1
Output
23