ヒープの判定 Ruby編（paizaランク C 相当）

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

問題

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

特殊な根付き木の 1 つとしてヒープがあります。
ヒープには次のような特徴があります。

・親要素の値は子要素よりも常に大きいか等しい(または常に小さいか等しい)

親要素の値が子要素よりも常に大きいか等しいヒープを最大ヒープ、常に小さいか等しいヒープを最小ヒープといいます。
この問題では最大ヒープを扱います。
一番上の頂点を根とした場合、上の根付き木は最大ヒープですが、下の根付き木は水色の部分が最大ヒープの条件を満たしていないため、最大ヒープではありません。

根付き木の頂点の値・辺についての情報が与えられるので、この根付き木が最大ヒープであるかどうかを判定してください。

入力される値

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

・1 行目には、根付き木の頂点の数 N, 根付き木の根の頂点番号 R が与えられます。
・続く N-1 行では、根付き木の各辺の両端の頂点の値 a_i , b_i が与えられます。ただし、a_i を値として持つ頂点が b_i を値として持つ頂点の親であることが保証されています。(1 ≦ i ≦ N-1)

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

期待する出力: ・与えられた根付き木が最大ヒープになっているのであれば "YES" を、そうでなければ "NO" を 1 行で出力してください。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・1 ≦ N ≦ 100
・1 ≦ R ≦ N
・1 ≦ a_i , b_i ≦ 100,000 (1 ≦ i ≦ N-1)
・与えられる木の中に同じ値が 2 つ以上含まれていないことが保証されている。

入力例1: 5 10
10 11
10 9
9 3
3 2

出力例1: NO

入力例2: 10 91753
91753 76540
76540 31536
31536 14625
31536 22346
91753 36347
22346 5911
91753 26082
76540 70927
36347 32065

出力例2: YES

問題一覧へ戻る