Problem Background

There are too many people and too many things roaring between us
Too much noise, weak signals, even the wind can interfere
But you don't want to always walk in the dark underground passage
Want to feel the breeze, want freedom, want to hold hands and go together to see the sea, wander around the world
——"Code"

Continuing from the previous episode, each army has received supplies. However, preparations for battle are not yet fully adequate. JF only has an army that forms a corps. Only then can a formidable combat force be formed, which can achieve victory in the warlord chaos.

Problem Description

Given that JF has $n$ armies, they are connected by $n-1$ edges. The 1st army is the root. Each army has its own "code" of black or white, for mutual communication, as well as its combat strength and morale values. Initially, the morale value of an army is equal to its combat strength. Starting from the army with the deepest depth, for the current army $u$, among the armies directly connected to it and with a depth deeper than $u$, if there is an army $v$ with the same code as $u$, $u$ can contact $v$, and then $u$'s morale value must be completely increased by the combat strength of all points in $v$'s subtree that have the same color as $v$. (It can be understood that when $u$'s morale is updated, the morale of $u$'s subtree is also updated.)

Now, you can modify the codes of these armies arbitrarily. You are to find the maximum sum of the morale values of all armies.

Input Format

The first line contains an integer $n$, as described.

The second line to the $n$-th line each contain two numbers, indicating an edge between $u$ and $v$.

The $(n+1)$-th line contains $n$ numbers, the $i$-th of which represents the initial combat strength $w_i$ of the $i$-th army.

Output Format

A single line containing an integer, representing the maximum sum of the morale values.

Sample Input and Output

Input Sample #1

4
1 2 
1 3 
2 4 
6 -2 4 -7 

Output Sample #1

5

Input Sample #2

10
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
4 10
-3 9 4 -3 -2 5 -1 -3 -9 7

Output Sample #2

42

Input Sample #3

20
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
4 10
6 11
6 12
7 13
7 14
7 15
7 16
8 17
9 18
11 19
15 20
1 2 -1 -4 9 -3 -5 8 9 -10 -13 15 11 -6 17 -1 -19 20 -5 -9

Output Sample #3

266

Input Sample #4

6
1 2
1 3
1 4
2 5
2 6
-1 5 -3 -4 -5 -7

Output Sample #4

-10

Notes/Hints

Sample Explanation #1

We change the codes of armies $1, 3, 4$ to black and the code of army $2$ to white. Thus, the final morale values of armies $1, 2, 3, 4$ become $10, -2, 4, -7$, with a total sum of $5$. It can be proven that no scheme exists with a greater sum of final morale values.

Sample Explanation #2

We use $1$ to represent a black code and $2$ to represent a white code. Then the code colors of the $n$ armies are as follows: 1 1 1 1 2 1 2 2 2 1. This results in a total morale sum of $42$. It can be proven that no scheme exists with a greater sum of morale values.

Data Range and Constraints

For $100\%$ of the data, $1 \le n \le 300$, $-1000 \le w_i \le 1000$.

见题面 Input 部分

见题面 Output 部分