D - 高橋君と木のおもちゃ

D - 高橋君と木のおもちゃ解説

実行時間制限: 2 sec / メモリ制限: 256 MB

高橋君は妹から誕生日プレゼントに木のおもちゃを貰った。

木のおもちゃは N 個の球と N-1 本の節からなる。各球には 1 から N まで番号がつけられており、各節には 1 から N-1 まで番号が付けられている。

N-1 本の節は、異なる 2 つの球を接続しており、これらはすべて番号の大きい方の球から番号の小さい方の球へと向きが付けられている。また、球 1 以外のどの球からも、その球から番号の小さい別の球へと向きがつけられている節がある。

どの球もちょうど 1 つの整数を格納することができる。最初、球 i (1 ≦ i≦ N) には整数 s_i が格納されている。

高橋君は妹と一緒に、手元にある M 個の整数を使って木のおもちゃでゲームをすることにした。

ゲームの目的は、木のおもちゃのそれぞれの球に格納されている整数の合計ができるだけ大きくなるようにすることにした。

高橋君は M 回、以下のステップを行う。

球 j (1 ≦ j ≦ N) は、整数が置かれたとき、以下の動作を行う。

木のおもちゃの変化が止まるまで、高橋君と妹は次のステップに移動することができない。

最終的に木のおもちゃの各球に格納されている整数の合計値として考えられる最大値を求めよ。

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

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 行に出力せよ。出力の末尾にも改行を入れること。

以下の手順で操作を行います。

最初、木のおもちゃは下図のようになっています。以降数枚の図では、節を矢印で、球の番号を枠の添字で、球に格納されている整数は枠の内部に書かれた整数で表現されています。

最終的には、各球に格納されている整数の合計値は 5 + 7 + 5 + 8 + 5 + 6 + 4 = 40 となり、これが考えられる最大値です。