# Averaging

Time Limit : 2 sec, Memory Limit : 524288 KB

# Problem J: Averaging

## Problem

ACdɂ$N$̓$N-1$̋Ae͂ꂼ$1$$N$܂ł̔ԍUĂB $i$Ԗڂ͓̋$u_i$Ɠ$v_i$oɌłA͋pēƓƂs邱ƂłB܂AȊOɓƓs@͂ȂB ǂ̓ǂ̓ւ̋n邱ƂœB邱ƂłB

݁A$i$ɂ$X_i$l̓B e̊ւׂ̕𕪎U邽߂ɃACd͉l̍ɕʂ̓ֈzĂ炤ƂɂB $a$ɏZłl$b$Ɉz邽߂ɂ͓$a$Ɠ$b$̋Ɠ̃RXgBA$a$Ɠ$b$͓̋$a$瓇$b$֍s߂ɓnKv̂鋴̐̍ŏlŒB

ǂ$2$̓Ił̓̐l̍̐Βl$1$ȉɂȂ悤ɍɈzĂ炢B ̂ƂAKvȃRXg̑a̍ŏl߂B

## Input

͈͂ȉ̌łׂĐŗ^B

$N$
$X_1$ $X_2$ ... $X_N$
$u_1$ $v_1$
$u_2$ $v_2$
...
$u_{N-1}$ $v_{N-1}$


$1$sڂɓ̐$N$^B
$2$sڂɂ͊e̓̐l\$N$̐󔒋؂ŗ^B$i$Ԗڂ̐$X_i$͓$i$̓̐l\B
$3$sڂ瑱$N-1$sɂ͊eȂ̔ԍ󔒋؂ŗ^B$2+i$sڂ̓͂ł́A$i$Ԗڂ̋$u_i$Ɠ$v_i$oɌł邱Ƃ\B

## Constraints

͈͂ȉ̏𖞂B

• $2 \le N \le 5000$
• $0 \le X_i \le 10^9$
• $1 \le u_i, v_i \le N$
• ǂ̓ǂ̓ւ̋n邱ƂœB邱Ƃł

RXg̑a̍ŏl1sɏo͂B

## Sample Input 1

5
4 0 4 0 0
1 2
1 3
1 4
2 5


## Sample Output 1

7


$1$̐l$1$lA$2$ցA
$1$̐l$1$lA$5$ցA
$3$̐l$2$lA$4$ֈzƂłǂ$2$̓Ił̓̐l̍̐Βl$1$ȉɂȂB ܂̂Ƃ̃RXg̑a$1+2+2\times2 = 7$łAꂪŏłB

## Sample Input 2

7
0 7 2 5 0 3 0
1 2
1 3
1 4
2 5
3 6
3 7


## Sample Output 2

10