F. LOCK S
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

"Another cycle past U, then. What a shocker."

After guiding Saturday's group to the underground where the truth was kept, Dawn was brought to somewhere unknown by the Worldkeeper, also known as Tsuki. There is no doubt that the duel of LOCK S is about to begin.

The battlefield takes the shape of a rooted tree with $$$n$$$ nodes, numbered $$$1$$$ to $$$n$$$, with $$$1$$$ being the root of the tree. Each node has a terrain vantage point, with the $$$i$$$-th node having a terrain vantage point of $$$v_i$$$. Dawn and Tsuki will fight here, taking turns occupying each node in the tree until they finally meet up and start fighting. Since Dawn is far more skilled at synchronizing with Layer 1 than Tsuki is after practicing with the LOCK P, V, and U, she will be the first to act in this node battle, followed by Tsuki, then Dawn's turn......, and so on.

Both Dawn and Tsuki start off outside the field. At the start of one's turn, she will choose a node that is not occupied by anyone that meets her action condition, move to that node, and occupy the node she moves to. When it is one person's turn to move but she does not have a node that meets the aforementioned conditions, she will choose to immediately meet the other one to begin the duel. The action conditions for both players are shown below:

  • Dawn: Due to Dawn's proficiency in synchronizing with Layer 1, she can choose any node $$$v$$$ and move to it, independent of which node she is currently at.
  • Tsuki: When Tsuki is outside the field, she can only move to node $$$1$$$. After that, she can only choose one of the sons of the node she is in, and that son has the largest terrain vantage point of all the unoccupied sons. Specifically, if there is more than one son that satisfies the condition, she chooses the one with the smallest number.

Dawn believes that as long as the sum of the terrain vantage point of the nodes she occupies, minus the sum of the terrain vantage point of the nodes Tsuki occupies, is maxed out at the time of the duel, she will survive LOCK S and perform a miracle. However, she doesn't know how to calculate this value, so she has to put all her hopes on you who are in Layer 4. Please help her calculate this maximum difference.

Input

The first line contains a positive integer $$$n$$$, indicating the number of nodes in the tree at the battle site. It is guaranteed that $$$1\le n\le 2\times10^5$$$.

The second line contains $$$n$$$ positive integers $$$v_i$$$ indicating the terrain favorability of each node. It is guaranteed that $$$1\le v_i\le10^9$$$.

Each of the next $$$n-1$$$ lines contains two positive integers $$$x_i,y_i$$$, denoting a tree edge. The input graph is guaranteed to be a tree.

Output

A non-negative integer in a single line indicating the answer.

Examples
Input
8
2 4 2 1 3 1 1 3
1 2
2 3
2 4
1 5
5 6
5 7
1 8
Output
4
Input
5
8 2 7 10 4
1 2
1 3
1 4
1 5
Output
8
Note

Tsuki: What?!HUH?!How?!You're not...?!

Dawn: I don't understand it myself, but don't you realize the chance we've been given?!

Tsuki: Impossible! A miracle cannot save us, no matter how hard you hope!

Tsuki: It's been 8266 cycles and you still cling to this foolish hope?!

Dawn: Look around you, Tsuki. Eternity doesn't matter when you have an impossible chance given to you!

Dawn: Time and time again, we've looped this story and finally, a split second of a path lies before us!

Dawn: Are you going to waste the one escape rope you've ever been thrown since the moment you were born?

Dawn: Because I'm sure as hell not!