CF1237E

houzhiyuan · 2022-03-17 15:25:27 · 题解

标签：构造。

神仙题。

手玩一下小数据，可以发现深度小于等于 3 的只有树大小为 1,2,4,5 四种情况，并且方案数都是 1。

显然，由于是平衡树，那么 n 显然是根一直向右走到的点，可以发现必然与根节点奇偶性相同，所以右子树大小是偶数。

可以发现，一棵满足条件的树，它的左右子树也都必然满足条件。

所以可以从深度小的向深度大的递推。

设 f_i 表示深度为 i 的满足条件的平衡树的最小大小。

用归纳法证明只有大小为 f_i,f_i+1 的树可以满足条件。

首先对 i=1,2 显然成立。

假设对于 i 成立，那么深度为 i+1 的树必然是一个根再加上两个深度为 i 的树。

深度为 i 的树只有 f_i,f_i+1 两种。

设左右两子树大小为 L,R，那么需要满足 L+1 和 L+R+1 奇偶性相同。

所以 R 必然是偶数，L 可以取 f_i 和 f_i+1。

这样证明了上面的结论，也证明了方案数只可能是 0,1。

递推式也很简单：

code。