CF1491E Fib-tree

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

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