010 - ダンジョン2

問題文

B君は、昨年発売され人気だったゲーム「ダンジョン」の続編「ダンジョン2」で遊んでいる。ゲームは、N個の部屋とそれらを直接つなぐN-1本の道からなるマップ上で行われる。道はどちらの部屋からでも行き来することができる。また、どの部屋からでも、いくつかの道をたどって他のどの部屋にも到達できる。各部屋には点数が書かれている。

B君はキャラクターのトラトラ君を動かして、高得点の獲得を目指す。部屋に初めて到達したときだけ、苑部屋に書かれた点数が加算される。スタート地点とゴール地点の点数も加算される。ただし、道を通るたびに得点が1減点される。トラトラ君のスタート地点としてどの部屋を選んでも良いし、スタート地点も含め、どの部屋でゴールしても良い。

課題

マップの情報が与えられたとき、B君が得ることができる合計点の最大値を出力するプログラムを作成せよ。

入力・出力

入力

入力は以下の形式で与えられる。

N
p1
p2
:
pN
s1 t1
s2 t2
:
sN-1 tN-1

1行目に部屋の数N(1≦N≦100,000)が与えられる。続くN行に、i番目の部屋の得点p_i(-100≦p_i≦100)が整数で与えられる。続くN-1行に、2つの部屋を直接つなぐ道の情報が与えられる。s_iとt_i (1≦s_i<t_i≦N)はi番目の道がつなぐ2つの部屋の番号である。ただし、どの2つの部屋についても、それらを直接つなぐ道は1本以下とする。

出力

B君が得ることができる合計点の最大値を1行に出力する。

入出力例

入力例 1

7
6
1
-1
4
3
3
1
1 2
2 3
3 4
3 5
5 6
5 7

出力例 1

10

例えば、部屋番号6 → 5 → 3 → 4 → 3 → 2 → 1 とたどれば得点が最大になる。

入力例 2

4
5
0
1
1
1 2
2 3
2 4

出力例 2

5

部屋番号1をスタート地点かつゴール地点とすれば、得点が最大になる。