グループ企業 2 Erlang(Beta)編（paizaランク B 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

グループ企業 G は N 社が所属しており、親会社(会社 0 )と N - 1 個の子会社(会社 1, 会社 2, ...)を含みます。これらの会社間には親子関係が合計で N - 1 個存在し、会社 C_i の子会社は会社 D_i です。各会社の収益は以下の条件にしたがって計算されます。

会社 0 以外のすべての会社はただ一つの親会社を持ちます。

会社 i の収益は R_i ですが、少ないと株価が下がりそうで少し不安です。そこで、会社 i の収益は代わりに Max( 会社 i の収益, 会社 i の子会社の収益, 会社 i の子会社の子会社の収益, ...)を公表することにします。つまり、自社の子会社すべての収益の最大値を公表します。

Q 回のクエリが与えられます。以上の条件にしたがうとき、会社 q_i が公表する収益を答えてください。

入力される値

N Q
R_0 R_1 R_2 ... R_(N-1)
C_0 D_0
...
C_(N-2) D_(N-2)
q_0
q_1
...
q_(Q-1)

・ 1 行目に、グループ企業に所属している会社の数 N とクエリの数 Q が与えられます。
・ 2 行目に、各企業の実際の収益 R_i が与えられます。
・ 3 行目から N + 1 行目にかけて、 2 つの会社 C_i と D_i の親子関係が与えられます。会社 C_i の子会社は会社 D_i です。
・ N + 2 行目から Q 行にかけて、クエリ q_i が与えられます。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: Q 回のクエリが与えられます。 i 回目のクエリでは会社 q_i が公表する収益を答えてください。

また、末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・入力はすべて整数
・ 2 ≦ N ≦ 10,000
・ 1 ≦ Q ≦ 10,000
・ 0 ≦ R_i < 10,000
・ 0 ≦ C_i ≦ N - 1
・ 1 ≦ D_i ≦ N - 1
・ 0 ≦ q_i ≦ N - 1
・会社 0 以外のすべての会社はただ一つの親会社を持つ
・会社の親子関係に矛盾が生じるような入力は与えられない

入力例1: 7 7
3 7 6 1 2 5 4
0 1
0 2
1 4
2 3
2 5
3 6
0
1
2
3
4
5
6

出力例1: 7
7
6
4
2
5
4

問題一覧へ戻る