構文解析木#1 R(Beta)編（paizaランク C 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
与えられた根付き木を帰りがけ順（ポストオーダー）で訪問した順番で、ノードに書かれた数値を出力してください。
帰りがけ順（ポストオーダー）について
帰りがけ順（ポストオーダー）とは、以下の順番で木のノードを訪問する方法です。
- 左の子ノードを訪問する。
- 右の子ノードを訪問する。
- 最後に親ノードを訪問する。
- 入力される値
-
1行目に、ノードの総数 n とノードの番号の最大値 m が空白区切りで与えられます。
2~n+1行目に、ノードの番号 ai(1 ≦ i ≦ n)、ノードの要素 bi(1 ≦ i ≦ n) が空白区切りで与えられます。n m
a1 b1
a2 b2
.
.
.
an bn
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
合計で n 行の出力をしてください。
与えられた木構造を 1 番のノードから帰りがけ順で探索し、その時に通ったノードの要素を順番に 1 行ずつ出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
入力例5 8
1 8
2 38
3 5
4 4
8 25
入力例の木は下図のようになります。
出力例25
4
38
5
8
- 条件
-
すべてのテストケースにおいて、木構造は以下の条件をみたします。
・ 1 ≦ n ≦ m ≦ 106
・ ノード番号 1 以外のノードは必ず親を持つ
・ ai の親ノード番号は ⌊ai / 2⌋
・ 1 ≦ ai ≦ m
・ 1 ≦ bi ≦ 109
- 入力例1
-
5 8
1 8
2 38
3 5
4 4
8 25
- 出力例1
-
25
4
38
5
8
