Construct the Binary Tree - #624 e div3
#tree
一番浅い leaf とは, 5 のこと (root を除く)
上の図で, leaf で, 一番浅いのから上に上げる理由は, もともと chain で, 下の方が詰まりやすいから
一番右の図で, 4 を上げたら 2 の子が 3 つになる
親の親に移動するのではない
深さが 2 小さい頂点に移動する
親の親に移動するので WA になるケース
1
10 19
sample 2 で, 図のようになって終了し, NO となってしまう
bad がいる理由
v を選ぶ時点では, 移動先を考慮しない
よって, v に移動先がないかもしれない
v に移動先がないのは, 親が 0 であるだけでない
sample 2 の上図で, 7 には移動先がない
一度移動先がなければ, 今後移動先はない
v の祖先の子ができるだけだから
計算量
d の条件
最大で, chain のとき
最小で, 根に近い頂点から子がちょうど 2 つあるような木
最小の方で, N = 5000 のとき 51822
d ≤ 5000 より, NO
だいたい N < 700 くらいである必要がある
while (cur > d) が 10^5 くらい
その中で O(N = 700)
あとは, 最小の方の求め方
頂点 1 では何も足さず, 頂点 2, 3 で 1 を足す
4 ~ 7 で 2 を足し, 8 ~ 15 で 3 を足す...
1, 4, 8, ... で足す数が 1 増える
if (!(i & (i - 1))) ++cd;
