CF1491E Fib-tree

有一个结论就是，如果一个树是斐波那契树，那么每次随便找合法的边切得到的两半一定都是斐波那契树。我们考虑数学归纳法证明：
假设这个结论对$\leq k$阶的斐波那契数成立，然后考虑$k+1$阶的分割方案。我们发现因为最多只有两条合法的边可以分割。我们随便拿一条出来将$F_{k+1}$树分为$F_{k}$和$F_{k-1}$的两半，我们发现如果我们接着切合法的另一条边，就会将那个$F_{k}$的一半分成$F_{k-1}$和$F_{k-2}$。

因为我们已经对$k$阶之前的情况假设了结论成立，所以我们钦定立马切另一条边，一定不劣。这样就分成了两块$F_{k-1}$和一块$F_{k-2}$。我们发现如果先切另一条边，分出来的还是这三块，所以先切哪条边对于$k+1$阶斐波那契树不重要。证毕。