Dungeon 2

Time Limit : 1 sec, Memory Limit : 262144 KB

ダンジョン2

 

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

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

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

入力

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

$N$
$p_1$
$p_2$
$...$
$p_N$
$s_1$ $t_1$
$s_2$ $t_2$
$...$
$s_{N-1}$ $t_{N-1}$

1行目に部屋の数$N$ ($1 \leq N \leq 100,000$)が与えられる。続く$N$行に、$i$番目の部屋の得点$p_i$ ($-100 \leq p_i \leq 100$)が整数で与えられる。続く$N-1$行に、2つの部屋を直接つなぐ道の情報が与えられる。$s_i$と$t_i$ ($1 \leq s_ i < t_i \leq 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 \rightarrow 5 \rightarrow 3 \rightarrow 4 \rightarrow 3\rightarrow 2\rightarrow 1$とたどれば得点が最大になる。

入力例2

4
5
0
1
1
1 2
2 3
2 4

出力例2

5

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