Background

Too many people and too many things roar between us.
Too much noise and the signal is weak, even the wind can interfere.
But you do not want to keep walking in a dark underground passage.
You want to feel the wind and be free, to hold hands and go see the sea, and wander around the world.
—— "Cipher"

Continuing from the previous story, every army has received supplies. However, to go to the battlefield, the preparation is still not sufficient. Only if JF’s armies form a group army can they produce strong fighting power, and only then can they win in the warlord chaos.

Problem Description

It is known that JF has $n$ armies, which are connected by $n-1$ edges. Army $1$ is the root. Each army has its own black-or-white "cipher" for communication, as well as its combat power value and morale value. Initially, an army’s morale value equals its combat power value.

We start changing morale values from the deepest army (largest depth). For the current army $u$, among the armies directly connected to $u$ that have a greater depth than $u$, if there exists an army $v$ whose cipher is the same as $u$’s, then $u$ can contact $v$. Then $u$’s morale value must add in full the sum of combat power values of the nodes in the subtree of $v$ whose cipher color is the same as $v$’s. (You can understand this as: when the morale update of $u$ is finished, the morale of $u$’s subtree has also been fully updated.)

Now, you may modify the ciphers of these armies arbitrarily. You need to find the maximum possible value of the sum of morale values of all armies.

Input Format

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

Lines $2$ to $n$ each contain two integers, representing an edge between $u$ and $v$.

Line $n+1$ contains $n$ integers. The $i$-th integer represents the initial combat power value $w_i$ of the $i$-th army.

Output Format

Output one integer in one line, representing the maximum sum of morale values.

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

5

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

42

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

266

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

-10

Hint

Sample Explanation #1.

We change the ciphers of armies $1,3,4$ to black, and change the cipher of army $2$ to white. Then the final morale values of armies $1,2,3,4$ become $10,-2,4,-7$, and the total sum is $5$. It can be proven that there is no plan that yields a larger final sum of morale values.

Sample Explanation #2.

We use $1$ to represent the black cipher and $2$ to represent the white cipher. Then the cipher colors of the $n$ armies are as follows: 1 1 1 1 2 1 2 2 2 1. The sum of morale values of the entire army is $42$. It can be proven that there is no plan that yields a larger sum of morale values.

Constraints and Notes.

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

Translated by ChatGPT 5