NOMURA プログラミングコンテスト 2020 C - Folia (600)
木の上から構築していくのは下から構築していきたい
下から何の制限も無くやるのも大変そうなので上限を決めたい
$ n = 0 の時、$ a_0 \gt 1 にはできない
$ n \ne 0の時、$ a_0 \gt 0にはできない
深さiの地点で、葉にならない点の数の上限$ f_iは葉の数を$ a_iとして$ f_i + a_i = f_{i-1} \times 2より$ f_i = 2f_{i-1} - a_i
これを用いて下からできるだけたくさんの点を揃える
深さiに置くことができる最大の点の数$ c_i = min(f_i, c_{i+1}) + a_i
$ c_{i+1} \gt 2f_iの場合は、枝を作りきれないため駄目
$ \sum_{i=0}^n c_iが答え