二分探索木の判定 (paizaランク C 相当)

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

問題

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

このチャプターでは、グラフ理論における二分探索木を扱います。
二分探索木とは、根付き木の一種で、各頂点が持つ子の数が高々 2 であり、かつ、次の条件を満たすもののことを指します。

```
ある頂点の値 V と、その左右の子の値 V_L , V_R について「V_L < V < V_R」が全ての頂点について成り立つ。
```

例として、以下のような根付き木は二分探索木となります。

根付き木の頂点・辺についての情報が与えられるので、この根付き木が二分探索木かどうかを判定してください。

入力される値

N R
a_1 b_1 LR_1
...
a_{N-1} b_{N-1} LR_{N-1}

・1 行目には、根付き木の頂点の数 N, 根付き木の根の頂点の値 R が与えられます。
・続く N-1 行のうち、i 行目では、辺の親の値 a_i と子の値 b_i と、子が左右どちらにあるかを表す LR_i が与えられます。(1 ≦ i ≦ N-1)

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

期待する出力: ・与えられた根付き木が二分探索木である場合には "YES" を、そうでない場合は "NO" を 1 行で出力してください。

条件: すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ N ≦ 100
・1 ≦ R ≦ 100,000
・0 ≦ a_i , b_i ≦ 100,000 (1 ≦ i ≦ N-1)
・LR_i は 'L' または 'R'(1 ≦ i ≦ N-1)
・与えられる根付き木の高さは 20 未満であることが保証されている。
・a_i は「根の頂点の値」または「親の頂点が確定している頂点の値」であることが保証されている。
・与えられる木の中に同じ値が 2 つ以上含まれていないことが保証されている。

入力例1: 3 2
2 3 L
2 1 R

出力例1: NO

入力例2: 5 6
6 3 L
6 8 R
3 1 L
3 5 R

出力例2: YES

問題一覧へ戻る