numbers on tree - #612 div2 d
#貪欲 #dfs
sample2, 問題文の図で考える.
を 1 ~ n で, 異なるものにできることを言う.
まず, 親が 0 の 0 番が 根 (root)
= 1
= 2 とすれば, その子孫には自分より小さいのが 1 つで 1, あとは 3, 4, 5
0 の子の 1 に行く
= 3
2 は 0 で使ったから使えず, 1, 3, 4, 5 で, 下に 3 つあるようなのは 5
子は 2 つあるが, 2 (図で言うと左) に行く
= 1
1, 3, 4 が残ってて, 下に 1 つあるようなのは 3
子の 3 に行く
= 0
1, 4 が残ってて, 下にないのは 1
1 に戻り, 子の 4 に行く
= 0
残りの 4 にする
注意
NO なケースがある
それは, (頂点 i の部分木のサイズ) < のとき
ケース
6
0 0
1 3
2 0
2 0
1 0
5 0
NO