无

无

无

无

无

无

无

无

无

Codeforces Round #655 EF

无

无

Codeforces Round #657 (Div. 2) E. Inverse Genealogy

题意：如果一个节点的左右子树节点数相差一倍或以上，则称这个节点是不平衡的。给定n, k,尝试构造包含n个节点、k个不平衡节点的二叉树。

可以发现n个节点最多包含（n-3）/2个不平衡节点，且n一定是奇数。如果所有节点都是平衡的，那么这颗树一定是满二叉树，即n+1为2的幂。反过来，如果n+1是2的幂那么一定无法构造出1个不平衡节点的二叉树。

另外，也存在一些特殊的情况如n=9,k=2无法构造。

如果采用递归向下构造，将k分割到两个子树中，很容易出现构造失败的情况，难以确定k合适的值。对于k=1的情况下可以比较容易的构造出解或判定无解。比较难想到的是可以从根部向上构造，这样可以确保新加入的根节点是不平衡的，即增加2n个节点，n个不平衡节点。

结合后两种方法，再在无解的时候（即无法构造k=1的子树）和尝试做一些调整，避开2的幂就可以过了。n<13的情况下可以直接递归向下构造子树，在k=1、k=2的情况下特判。

Comment：这道题赛前没有人通过，做的过程中也遇到了不少坑。实际上可以打表验算一下/使用暴力方法对拍验证思路。

Tag：二叉树、构造