Ｂ君は、昨年発売され人気だったゲーム「ダンジョン」の続編「ダンジョン２」で遊んでいる。ゲームは、$N$個の部屋とそれらを直接つなぐ$N-1$本の道からなるマップ上で行われる。道はどちらの部屋からでも行き来することができる。また、どの部屋からでも、いくつかの道をたどって他のどの部屋にも到達できる。各部屋には点数が書かれている。
Ｂ君はキャラクターのトラトラ君を動かして、高得点の獲得を目指す。部屋に初めて到達したときだけ、その部屋に書かれた点数が加算される。スタート地点とゴール地点の点数も加算される。ただし、道を通るたびに得点が１減点される。トラトラ君のスタート地点としてどの部屋を選んでも良いし、スタート地点も含め、どの部屋でゴールしても良い。
マップの情報が与えられたとき、Ｂ君が得ることができる合計点の最大値を出力するプログラムを作成せよ。
入力は以下の形式で与えられる。
$N$
$p_1$
$p_2$
$...$
$p_N$
$s_1$ $t_1$
$s_2$ $t_2$
$...$
$s_{N-1}$ $t_{N-1}$
１行目に部屋の数$N$ ($1 \leq N \leq 100,000$)が与えられる。続く$N$行に、$i$番目の部屋の得点$p_i$ ($-100 \leq p_i \leq 100$)が整数で与えられる。続く$N-1$行に、２つの部屋を直接つなぐ道の情報が与えられる。$s_i$と$t_i$ ($1 \leq s_i < t_i \leq N$)は$i$番目の道がつなぐ２つの部屋の番号である。ただし、どの２つの部屋についても、それらを直接つなぐ道は１本以下とする。
Ｂ君が得ることができる合計点の最大値を１行に出力する。
7 6 1 -1 4 3 3 1 1 2 2 3 3 4 3 5 5 6 5 7
10
例えば、部屋番号$６ \rightarrow ５ \rightarrow ３ \rightarrow ４ \rightarrow ３\rightarrow ２\rightarrow １$とたどれば得点が最大になる。
4 5 0 1 1 1 2 2 3 2 4
5
部屋番号１をスタート地点かつゴール地点とすれば、得点が最大になる。