思路

令节点总数为 $n=a+b+c$。每条边恰好对应一个子节点，所有节点的子节点数之和为 $2a+b$；树恰有 $n-1$ 条边，因此必须满足

也就是 $c=a+1$。这个条件也充分：先构造含 $a$ 个二叉节点的树，再插入 $b$ 个单子节点即可。若不满足，直接输出 $-1$。

为了最小化高度，应先把二叉节点尽量放在较浅的位置，尽早产生更多可用位置；随后把单子节点依次放在最浅的可用位置。

做法

维护一个队列，保存还未确定子节点数量的位置的深度。最初只有深度为 $0$ 的根。

先处理 $a$ 个二叉节点。每次取出队首深度 $d$，并向队尾加入两个深度为 $d+1$ 的位置。这样得到最平衡的二叉结构，队列中剩下的 $c$ 个位置将成为叶子。

再处理 $b$ 个单子节点。每次取出队首深度 $d$，并向队尾加入一个深度为 $d+1$ 的位置，相当于在当前最浅的叶子下延长一条边。

队列中的深度始终非递减，因此最后队尾的深度就是答案。

正确性证明

将任意合法树中的所有单子节点压缩，得到一个每个非叶节点恰有两个子节点的二叉结构，它仍有 $c$ 个叶子。记其叶子深度之和为 $E$。

如果存在深度为 $d$ 的浅叶子和深度为 $D\ge d+2$ 的最深叶子，最深叶子的兄弟也一定是叶子。把最深的一对兄弟叶子合并为其父节点，再把浅叶子扩展成两个叶子，叶子总数保持不变，高度不会增加，叶子深度之和的变化为 $d-D+1<0$。反复交换后，各叶子的深度最多相差 $1$。

设 $h=\lceil\log_2 c\rceil$，$s=2^h-c$。最平衡的二叉结构有 $s$ 个深度为 $h-1$ 的叶子，其余叶子深度为 $h$，因此最小的叶子深度之和为

当 $c=1$ 时，$h=s=0$，结构只有根，上式仍成立。

若最终高度不超过 $H$，全部叶子深度之和最多为 $cH$。每插入一个单子节点，它下面至少有一个叶子，因此叶子深度总和至少增加 $1$，必要条件为 $b\le cH-E_{\min}$，同时必须有 $H\ge h$。

反过来，在最平衡的二叉结构中，每个叶子路径都可以单独延长，容量总和恰好为 $cH-E_{\min}$。只要上述条件满足，就能把 $b$ 个单子节点分配到这些路径上，构成高度不超过 $H$ 的树。

队列算法先构造这样的最平衡二叉结构，再始终延长最浅的叶子。它先用至多 $s$ 个单子节点填平浅叶子，之后每完整分配 $c$ 个单子节点，高度才增加一层。因此恰好达到上述必要条件给出的最小高度，算法正确。

等价地，答案可写为

部分分做法

子任务 1 可以枚举前序遍历中每个节点的子节点数量，用栈保存待生成位置的深度，直接枚举所有可能的树形并取最小高度。

子任务 2 设 $f_{x,y}$ 为含 $x$ 个二叉节点、$y$ 个单子节点的最小高度。若根为单子节点，转移自 $f_{x,y-1}+1$；若根为二叉节点，枚举左右子树分得的二叉节点数与单子节点数，取两棵子树高度较大值再加 $1$。初始状态为 $f_{0,0}=0$。

子任务 3 压缩全部单子节点，设 $g_k$ 为含 $k$ 个叶子的二叉结构的最小叶子深度总和。枚举左子树的叶子数可得

同时记录达到该最小值时的最小高度。利用前面的叶子路径容量结论，即可用 $\max(h_k,\lceil(b+g_k)/k\rceil)$ 得到答案，从而消除动态规划中与 $b$ 有关的维度。

复杂度

队列算法的时间复杂度为 $O(a+b)$，空间复杂度为 $O(c)$。所有测试的节点总数不超过 $300000$，因此总工作量满足限制。等价的闭式公式可以在 $O(\log c)$ 时间、$O(1)$ 空间内计算。

树形枚举的时间为指数级；子树动态规划需要 $O((a+1)^2(b+1)^2)$ 时间与 $O((a+1)(b+1))$ 空间；叶子深度动态规划需要 $O(c^2)$ 时间与 $O(c)$ 空间。

高度本身不超过 $100000$，但如果用二分法检查叶子容量，搜索上界处的乘积 $Hc$ 可能超过 32 位整数，应使用 64 位整数。