AT_arc029_4 [ARC029D] 高橋君と木のおもちゃ

[problemUrl]: https://atcoder.jp/contests/arc029/tasks/arc029_4 高橋君は妹から誕生日プレゼントに木のおもちゃを貰った。 木のおもちゃは $ N $ 個の球と $ N-1 $ 本の節からなる。各球には $ 1 $ から $ N $ まで番号がつけられており、各節には $ 1 $ から $ N-1 $ まで番号が付けられている。 $ N-1 $ 本の節は、異なる $ 2 $ つの球を接続しており、これらはすべて番号の大きい方の球から番号の小さい方の球へと向きが付けられている。また、球 $ 1 $ 以外のどの球からも、その球から番号の小さい別の球へと向きがつけられている節がある。 どの球もちょうど $ 1 $ つの整数を格納することができる。最初、球 $ i\ (1\ ≦\ i≦\ N) $ には整数 $ s_i $ が格納されている。 高橋君は妹と一緒に、手元にある $ M $ 個の整数を使って木のおもちゃでゲームをすることにした。 ゲームの目的は、木のおもちゃのそれぞれの球に格納されている整数の合計ができるだけ大きくなるようにすることにした。 高橋君は $ M $ 回、以下のステップを行う。 1. 手元にある整数を $ 1 $ つ取り出す。$ i\ (1\ ≦\ i\ ≦\ M) $ 回目のステップで取り出す整数は $ t_i $ である。 2. 以下のいずれかの操作を行う。 - 木のおもちゃに対して何もせず、整数 $ t_i $ を捨てる。 - 木のおもちゃを構成する球から $ 1 $ つ選び、整数 $ t_i $ を置く。 球 $ j\ (1\ ≦\ j\ ≦\ N) $ は、整数が置かれたとき、以下の動作を行う。 - $ j\ =\ 1 $ のとき、球 $ 1 $ は元から格納してある整数を捨て、球 $ 1 $ に置かれた整数を格納する。 - $ j\ ≧\ 2 $ のとき、球 $ j $ は元から格納してある整数を、球 $ j $ から出ている節の行き先となる球におき、球 $ j $ に置かれた整数を格納する。 木のおもちゃの変化が止まるまで、高橋君と妹は次のステップに移動することができない。 最終的に木のおもちゃの各球に格納されている整数の合計値として考えられる最大値を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ s_1 $ $ s_2 $ : $ s_N $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ : $ a_{N-1} $ $ b_{N-1} $ $ M $ $ t_1 $ $ t_2 $ : $ t_M $ - $ 1 $ 行目には、妹から貰った木のおもちゃを構成する球の個数を表す整数 $ N\ (2\ ≦\ N\ ≦\ 5,000) $ が与えられる。 - $ 2 $ 行目から $ N $ 行には、球に最初から格納されている整数に関する情報が与えられる。これら $ N $ 行のうち上から $ i\ (1\ ≦\ i\ ≦\ N) $ 行目には整数 $ s_i\ (1\ ≦\ s_i\ ≦\ 1,000,000,000) $ が与えられる。これは、球 $ i $ には最初に整数 $ s_i $ が格納されていることを表す。 - $ N+2 $ 行目から $ N-1 $ 行には、節に関する情報が与えられる。これら $ N-1 $ 行のうち上から $ i\ (1\ ≦\ i\ ≦\ N-1) $ 行目には整数 $ a_i,\ b_i\ (1\ ≦\ a_i\ ＜\ b_i\ ≦\ N) $ が空白区切りで与えられる。これは、球 $ b_i $ から出て、球 $ a_i $ に入る節があることを表す。 - $ 2N+1 $ 行目には、手元にある整数の個数を表す整数 $ M\ (1\ ≦\ M\ ≦\ 5,000) $ が与えられる。 - $ 2N+2 $ 行目から $ M $ 行には、手元にある整数に関する情報が与えられる。これら $ M $ 行のうち上から $ i\ (1\ ≦\ i\ ≦\ M) $ 行目には整数 $ t_i\ (1\ ≦\ t_i\ ≦\ 1,000,000,000) $ が与えられる。これは、$ i $ 回目のステップで整数 $ t_i $ を取り出すことを表す。

最終的に木のおもちゃの各球に格納されている整数の合計値として考えられる最大値を $ 1 $ 行に出力せよ。出力の末尾にも改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 7 $ かつ $ M\ ≦\ 8 $ を満たすデータセット $ 1 $ に正解した場合は、$ 10 $ 点が与えられる。 - $ N\ ≦\ 16 $ を満たすデータセット $ 2 $ に正解した場合は、上記とは別に $ 20 $ 点が与えられる。 - 追加制約のないデータセット $ 3 $ に正解した場合は、上記とは別に $ 70 $ 点が与えられる。 ### Sample Explanation 1 以下の手順で操作を行います。 1. 整数 $ 2 $ を取り出す。木のおもちゃには何もしない。 2. 整数 $ 8 $ を取り出す。木のおもちゃの球 $ 4 $ に置く。 3. 整数 $ 1 $ を取り出す。木のおもちゃには何もしない。 4. 整数 $ 3 $ を取り出す。木のおもちゃには何もしない。 5. 整数 $ 6 $ を取り出す。木のおもちゃの球 $ 6 $ に置く。 6. 整数 $ 3 $ を取り出す。木のおもちゃには何もしない。 7. 整数 $ 7 $ を取り出す。木のおもちゃの球 $ 2 $ に置く。 8. 整数 $ 5 $ を取り出す。木のおもちゃの球 $ 1 $ に置く。 - 最初、木のおもちゃは下図のようになっています。以降数枚の図では、節を矢印で、球の番号を枠の添字で、球に格納されている整数は枠の内部に書かれた整数で表現されています。 !\[\](/img/arc/029/4-1.png) - ステップ $ 2 $ (整数 $ 8 $ を球 $ 4 $ に置く動作) の直後、木のおもちゃは下図のようになっています。 !\[\](/img/arc/029/4-2.png) - ステップ $ 5 $ (整数 $ 6 $ を球 $ 6 $ に置く動作) の直後、木のおもちゃは下図のようになっています。 !\[\](/img/arc/029/4-3.png) - ステップ $ 7 $ (整数 $ 7 $ を球 $ 2 $ に置く動作) の直後、木のおもちゃは下図のようになっています。 !\[\](/img/arc/029/4-4.png) - ステップ $ 8 $ (整数 $ 5 $ を球 $ 1 $ に置く動作) の直後、木のおもちゃは下図のようになっています。 !\[\](/img/arc/029/4-5.png) 最終的には、各球に格納されている整数の合計値は $ 5\ +\ 7\ +\ 5\ +\ 8\ +\ 5\ +\ 6\ +\ 4\ =\ 40 $ となり、これが考えられる最大値です。