A さんと B さんがゲームをしています。
彼らの目の前にはいくつかの根付き木からなる森があり、各頂点 $u$ には正の整数の重み $A_u$ がついています。
A さんと B さんは交互に操作を行い、A さんが先手です。手番のプレイヤーは、木の根をちょうど $1$ つ選んで削除し、その頂点の重みを獲得します。削除された頂点の子を新たな根として、その部分木は新たな根付き木となります。
すべての頂点が削除されるとゲームは終了し、プレイヤーの得点は削除した頂点の重みの合計となります。
両プレイヤーは自身の得点を最大化することを目標とし、最適な戦略をとります。最終的な A さんの得点を求めてください。
与えられる初期状態は、ちょうど $n$ 個の頂点からなる $1$ つの木であり、頂点には $1$ から $n$ までの番号が付けられており、頂点 $1$ が根です。
入力
$1$ 行目に、頂点数を表す正の整数 $n$ が与えられます。
$2$ 行目に、各頂点の重みを表す $n$ 個の正の整数 $A_1,A_2,\dots,A_n$ が与えられます。
続く $n-1$ 行に初期状態が与えられます。各行には2つの正の整数 $u,v$ が与えられ、木において頂点 $u,v$ を結ぶ辺があることを表します。与えられるグラフが木であることは保証されています。
出力
最終的な A さんの得点を表す整数を $1$ 行に出力してください。
入出力例
入力 1
5
1 5 3 2 4
1 2
1 3
2 4
2 5出力 1
7入力 2
配布ファイルを参照してください。
制約
すべてのデータについて、$1\leq A_i\leq 10^9$。
| 小課題番号 | $n \le $ | 特殊性質 | 点数 |
|---|---|---|---|
| $1$ | $20$ | なし | $20$ |
| $2$ | $1\,000$ | $20$ | |
| $3$ | $2 \times 10^5$ | A | $20$ |
| $4$ | B | $20$ | |
| $5$ | なし | $20$ |
- 特殊性質 A：$p_i$ を $i$ の親とすると、すべての $2\leq i\leq n$ について $A_i\leq A_{p_i}$ が成り立つ。
- 特殊性質 B：すべての $A_i$ は $[1,10^9]$ の整数の中から等確率でランダムに選ばれる。