公式解説

aac003_e 解説

あるフィボナッチ木の部分木について、その頂点のすべては過去にフィボナッチ木の根だったものです。

つまり、その木がフィボナッチ木の部分木であるということは

• ある頂点を根とする
• それぞれの頂点にレベルを割り当てる
• すべての頂点が 2 つ以下の子を持つ
  • 2 つならばレベルが自分より $1, 2$ ずつ小さい
  • 1 つならばレベルが自分より $1$ か $2$ 小さい

を満たすということです。

また、その時の全体のフィボナッチ木の部分木としてのレベルは根のレベルと一致します。

そこで、根を固定した場合を考え、その時の最小のレベルの求め方を考えます。

これは、ある頂点についてその頂点のレベルを好きな正の整数上げても問題ないことから、簡単な木DPで求めることが出来ます。

具体的には、ある頂点が達成可能な最小のレベルを考えると

• 子が 2 つであるならばそれぞれのレベル $A, B$ について、
  • $A=B$ ならば $A+2$ （片方に $A$ 、もう片方に $A+1$ を割り当てる）
  • そうでないならば $\max(A, B)+1$ （小さい方を増やす）
• 子が 1 つであるならばそのレベルを $A$ として
  • $A+1$
• 子がない場合
  • $0$
• 子が 3 つ以上の場合達成不可能なので、
  • 便宜的に十分大きな値 $\mathrm{f\_inf}$

値が $\mathrm{f\_inf}$ 以上の場合は答えは -1 です。

あとは、全方位木DPでこの問題を解くことが出来ます。

ある頂点から DFS をしながら、その頂点からの方向での DP と逆向きでの DP 結果を持つことですべての頂点を根とした場合の答えを出す方法です。

ライブラリ化されたものも多いです。