子の頂点
(paizaランク C 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
このチャプターでは、グラフ理論における二分木を扱います。
二分木とは、根付き木の一種で、各頂点が持つ子の数が高々 2 であるようなもののことです。
子が高々 2 つであるため、子は「左の子」「右の子」と区別することが多いです。
例として、A は B と C の親、 B は A の左の子、 C は A の右の子であるような関係を図に起こすと下のようになります。
二分木の頂点や辺を子の左右の区別がわかる形式で管理するには、普通の木と同様に隣接行列や隣接リストで管理するだけでは足りません。各頂点について構造体を用意したり、頂点自体に左右の特性づけを行うなど、管理方法を工夫する必要があります。
二分木の頂点・辺についての情報と K 個の頂点と左右の組が与えられるので、与えられた各頂点の指定された子の頂点番号を出力してください。
- 入力される値
-
N K R
a_1 b_1 LR_1
...
a_{N-1} b_{N-1} LR_{N-1}
v_1 lr_1
...
v_K lr_K
・1 行目には、根付き木の頂点の数 N, 与えられる頂点の数 K, 二分木の根の頂点番号 R が与えられます。
・続く N-1 行では、根付き木の各辺の両端の頂点 a_i , b_i と左右の関係 LR_i が与えられます。ただし、LR_i が L のとき、b_i が a_i の左の子であることを、R のとき、b_i が a_i の右の子であることを表しています。(1 ≦ i ≦ N-1)
・続く K 行では、子の頂点を求めたい頂点の番号 v_i と調べたい子の左右 lr_i が与えられます。(1 ≦ i ≦ K)
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
・合計で K 行出力してください。
・i 行目では、lr_i が 'L' のとき v_i の左の子の頂点番号を、'R' のとき v_i の右の子の頂点番号を出力してください。(1 ≦ i ≦ K)
・指定された位置に子が存在しない場合は改行のみ出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ N ≦ 100
・1 ≦ K ≦ 100
・1 ≦ R ≦ N
・1 ≦ a_i , b_i ≦ N (1 ≦ i ≦ N-1)
・LR_i は 'L' または 'R'(1 ≦ i ≦ N-1)
・1 ≦ v_i ≦ N (1 ≦ i ≦ K)
・lr_i は 'L' または 'R'(1 ≦ i ≦ K)
- 入力例1
-
10 3 8
3 10 L
7 3 L
3 1 R
5 7 L
1 2 L
6 5 L
8 6 L
6 4 R
4 9 L
3 L
3 L
8 R
- 出力例1
-
10
10
- 入力例2
-
20 6 15
20 18 L
7 20 L
1 7 L
12 1 L
9 12 L
12 14 R
13 9 L
14 10 L
8 13 L
10 11 L
15 8 L
11 6 L
6 4 L
6 3 R
4 19 L
19 2 L
19 16 R
16 17 L
16 5 R
16 R
13 L
12 L
20 L
12 L
19 R
- 出力例2
-
5
9
1
18
1
16
