P8916 [DMOI-R2] Cipher.

> 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](https://www.bilibili.com/video/BV1p24y1f7zM)"* 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.

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

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 one integer in one line, representing the maximum sum of morale values.

#### 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. | Test Point ID | $n \le$ | Special Condition | | :----------: | :----------: | :----------: | | $1\sim2$ | $20$ | None | | $3 \sim 6$ | $50$ | None | | $7 \sim 10$ | $300$ | $v=u+1$ | | $11\sim12$ | $300$ | $1 \le w_i \le 1000$ | | $13\sim14$ | $300$ | $u=1$ | | $15 \sim 20$ | $300$ | None | For $100\%$ of the testdata, $1 \le n \le 300$, $-1000 \le w_i \le 1000$. Translated by ChatGPT 5