$N$ 頂点の木 $T=(V,E)$ があります。各頂点には整数が一つ書かれており、負の値もあり得ることに注意してください。次の条件を満たす $T$ の二つの部分グラフ $T_a=(V_a,E_a)$ と $T_b=(V_b,E_b)$ を求めます。

• $V_a\ne\varnothing,\quad V_b\ne\varnothing$

• $T_a$ と $T_b$ はそれぞれ連結です。

• $V_a\cap V_b=\varnothing$

• $V_a$ の頂点と $V_b$ の頂点を結ぶ辺は $E$ に存在しません。

• $V_a$ の頂点に書かれた整数の和と $V_b$ の頂点に書かれた整数の和を足した値を最大にします。

次の図の例を考えます。 $T=(\{0,1,2,3,4,5,6\},\{(0,1),(0,2),(2,3),(2,4),(4,6),(5,6)\})$.

頂点の上の数は頂点番号、内部の数は頂点の値です。条件を満たす $T_a,T_b$ の選び方は複数あり得ます。$V_a=\{0,2,3\}$、$V_b=\{5,6\}$ とすると、合計は $\{3+(-1)+4\}+\{5+3\}=14$ となり最大です。他の選び方もありますが、$14$ を超える値にはできません。

次の関数を実装してください。

long long findSum( int N, int C[], int Node1[], int Node2[] );

この関数はちょうど一度呼び出されます。入力は引数として渡され、戻り値が問題の答えです。$N$ は頂点数で、頂点は $0$ から $N-1$ まで番号が付きます。$0\le i\le N-1$ に対して C[i] は頂点 $i$ の整数です。$0\le i\le N-2$ に対して、頂点 Node1[i] と Node2[i] は辺で結ばれています。

実装の詳細

tree.cpp という名前のファイルをちょうど一つ提出し、次の関数を実装してください。

long long findSum( int N, int C[], int Node1[], int Node2[] );

関数は上の説明のとおり動作しなければなりません。内部で使う他の関数を定義しても構いません。提出するコードは入出力や他のファイルへのアクセスを行ってはいけません。

サンプル採点プログラム

配布される採点プログラムは、次の形式で入力を読みます。

• 1 行目： $N$

• 2 行目：$N$ 個の整数 $C_0,C_1,\ldots,C_{N-1}$。順に各頂点の値を表します。

• 続く $N-1$ 行：二つの整数 $a,b$。頂点 $a$ と $b$ を結ぶ辺を表します。

入力行の最後の数字を表す文字の後に空白や他の文字があると、採点プログラムが正しく動作しない可能性があるので注意してください。

採点プログラムは、あなたの findSum() 関数の戻り値を出力します。

制約

• $-10^9\le C_i\le10^9$

• $3\le N\le500,000$

小課題

1. (7 点) $N\le20$

2. (19 点) $N\le5000$

3. (74 点) 追加の制約はありません。

入出力例

入力 1

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

出力 1

14