根付き木の根の変更
(paizaランク B 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
根付き木の根を他の頂点に変更した時、根付き木の親子関係は変化します。
根付き木の頂点・辺についての情報と、新たな根となる頂点の番号と K 個の頂点 v_1 ... v_K が与えられるので、各頂点について親の頂点を出力してください。
- 入力される値
-
N R
a_1 b_1
...
a_{N-1} b_{N-1}
K r
v_1
...
v_K
・1 行目には、根付き木の頂点の数 N, 根付き木の根の頂点番号 R が与えられます。
・続く N-1 行では、根付き木の各辺の両端の頂点 a_i , b_i が与えられます。ただし、a_i が b_i の親であることが保証されています。(1 ≦ i ≦ N-1)
・N+1 行目では与えられる頂点の数 K と、新しい根となる頂点の番号 r が与えられます。
・続く K 行では、親の頂点を求めたい頂点の番号 v_i が与えられます。(1 ≦ i ≦ K)
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
・i 行目に v_i の全ての親の頂点番号を昇順に半角スペース区切りで出力してください。(1 ≦ i ≦ K)
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N ≦ 100
・ 1 ≦ R ≦ N
・ 1 ≦ a_i , b_i ≦ N (1 ≦ i ≦ N-1)
・ 1 ≦ K ≦ 100
・ 1 ≦ r ≦ N
・ 1 ≦ v_i ≦ N (1 ≦ i ≦ K)
- 入力例1
-
5 3
3 2
3 4
3 5
2 1
4 2
1
3
4
5
- 出力例1
-
2
2
3
3
- 入力例2
-
6 1
1 2
2 3
3 4
4 5
5 6
2 6
5
2
- 出力例2
-
6
3
