CF1379E Inverse Genealogy 题解

容易发现 $n$ 为偶数的时候一定无解。而 $n$ 为奇数时，特判 $n=1$，最多可以构造 $\frac{n-3}2$ 个不平衡点，构造方案就直接构造一条链然后给每个点再插一个儿子得到一个毛毛虫树即可。即：$i,i+1$ 点的子女结点为 $i-2$ 结点。

因此考虑在 $k$ 取在上界以内的时候先构造一个 $2k+3$ 个点有 $k$ 个不平衡点的树，然后把最底下的一个有 $3$ 个结点的子树扩建成一个完全二叉树。此时最多会新增一个不平衡点。这个时候把编号为 $1,3$ 两个点的部分扔掉（此时减少了一个不平衡点）然后把这两个点放在一个不会改变不平衡点数量的地方即可。

corner case 是 $n=9,k=2$。此时不存在合法解，$k<2$ 的特殊情况需要单独处理。