Problem Statement

Chawanmushi-kun and Kiri-kun love cream puffs, so the two of them are going to play the Cream Puff Game.
The Cream Puff Game is played on a tree. The tree has $N$ vertices and $N-1$ edges. The vertices are numbered from $1$ to $N$, and the $i\ (1\le i \le N-1)$-th edge connects vertex $u_i$ and vertex $v_i$. On vertex $i\ (1\le i\le N)$, there are $A_i$ cream puffs.
Starting with Chawanmushi-kun, they alternately perform the following operation until all vertices have been chosen.

• Choose one not-yet-chosen vertex adjacent to an already chosen vertex (however, on Chawanmushi-kun's first turn, he chooses vertex 1)
• Eat all the cream puffs placed on the chosen vertex

Input

$N$
$A_1\ A_2\ \cdots A_N$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_{N-1}\ v_{N-1}$

All inputs are integers.
$1\le N \le 1000$
$1\le A_i\le 10^9\ (1\le i\le N)$
$1\le u_i,\ v_i\le N\ (1\le i\le N-1)$
$u_i\neq v_i\ (1\le i\le N-1)$
The given graph is guaranteed to be a tree.

Output

Output an integer representing the answer on one line.
Print a newline at the end.

Sample

4
60 20 50 40
1 2
1 3
3 4

30

4
60 20 50 100
1 2
1 3
3 4

-10