グループ企業 1 Erlang(Beta)編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
グループ企業 G は N 個の会社が所属しており、親会社(会社 0 )と N - 1 個の子会社(会社 1, 会社 2, ...)を含みます。これらの会社間には親子関係が合計で N - 1 個存在し、会社 C_i の子会社は会社 D_i です。各会社の収益は以下の条件にしたがって計算されます。
- 会社 0 以外のすべての会社はただ一つの親会社を持ちます。
- 子会社が存在しない会社の収益は 1 です。
- 子会社が存在する会社の収益は、直属のすべての子会社の収益の和 +1 です。
Q 回のクエリが与えられます。 i 回目のクエリでは会社 q_i の収益を答えてください。
- 入力される値
-
N Q
C_1 D_1
...
C_(N-1) D_(N-1)
q_1
q_2
...
q_Q
・ 1 行目に、グループ企業に所属している会社の数 N とクエリの数 Q が与えられます。
・ 2 行目から N 行目にかけて、 2 つの会社 C_i と D_i の親子関係が与えられます。会社 C_i の子会社は会社 D_i です。
・ N + 1 行目から Q 行にかけて、クエリ q_i が与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
Q 回のクエリが与えられます。 i 回目のクエリでは会社 q_i の収益を答えてください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 2 ≦ N ≦ 10,000
・ 1 ≦ Q ≦ 10,000
・ 0 ≦ C_i ≦ N - 1
・ 1 ≦ D_i ≦ N - 1
・ 0 ≦ q_i ≦ N - 1
・ 会社 0 以外のすべての会社はただ一つの親会社を持つ
・ 会社の親子関係に矛盾が生じるような入力は与えられない
- 入力例1
-
7 7
0 1
0 2
1 4
2 3
2 5
3 6
0
1
2
3
4
5
6
- 出力例1
-
7
2
4
2
1
1
1
