子の頂点
(paizaランク C 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
このチャプターでは、グラフ理論における根付き木を扱います。
根付き木とは、以下の図のような n 個の頂点と、それらを連結する n-1 個の辺と頂点のうち、根と呼ばれる 1 つの特別な頂点からなるグラフのことです。
根付き木では、根である頂点を一番上に固定することで、2 つの頂点間に上下の関係を与えることができます。辺で結ばれた 2 つの頂点 A , B について、より根に近い方の頂点はもう一方の頂点の親といいます。また、根から遠い方の頂点はもう一方の頂点の子といいます。
例として、以下のような頂点 A , B があるとき、 A は B の親、 B は A の子となります。
根付き木の頂点や辺を親子関係がわかる形式で管理するには、普通の木と同様に隣接行列や隣接リストで管理する方法では上手くいきません。
各頂点について構造体を用意し、親子の頂点を記憶したり、辺に接続する 2 つの頂点のどちらが親かがわかるように辺の管理方法を工夫する必要があります。
根付き木の頂点・辺についての情報と K 個の頂点が与えられるので、与えられた各頂点の子の頂点番号を昇順で全て出力してください。
- 入力される値
-
N K R
a_1 b_1
...
a_{N-1} b_{N-1}
v_1
...
v_K
・1 行目には、根付き木の頂点の数 N, 与えられる頂点の数 K, 根付き木の根の頂点番号 R が与えられます。
・続く N-1 行では、根付き木の各辺の両端の頂点 a_i , b_i が与えられます。ただし、a_i が b_i の親になります。(1 ≦ i ≦ N-1)
・続く K 行では、子の頂点を求めたい頂点の番号 v_i が与えられます。(1 ≦ i ≦ K)
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
・K 行出力してください。
・i 行目に v_i の全ての子の頂点番号を昇順に半角スペース区切りで出力してください。(1 ≦ i ≦ K)
・子の頂点が存在しない場合は改行のみを出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N ≦ 100
・ 1 ≦ K ≦ 100
・ 1 ≦ R ≦ N
・ 1 ≦ a_i , b_i ≦ N (1 ≦ i ≦ N-1)
・ 1 ≦ v_i ≦ N (1 ≦ i ≦ K)
- 入力例1
-
4 2 1
1 2
1 3
2 4
1
2
- 出力例1
-
2 3
4
- 入力例2
-
10 3 5
4 10
6 4
4 8
8 3
4 9
3 1
7 6
5 7
4 2
8
7
3
- 出力例2
-
3
6
1
