对于一棵 $n + 1$ 个结点的「平衡树」，枚举其根结点的子树个数 $d$ 和子树大小 $s$。

- 首先要将 $2, 3, \ldots, n + 1$ 这 $n$ 个编号无序地分给 $d$ 个互不区分的（稍后会根据每个子树中的最小结点编号加以区分），大小均为 $s$ 的子树，方案数为 $\dfrac{n!}{d! \cdot (s!)^k}$。
- 接下来，每棵（互相区分的）子树均有 $a_s$ 种不同的结构（$a_s$ 为大小等于 $s$ 的本质不同的「平衡树」的数量），方案数为 $a_s^k$。

因此我们得到了递推式：

$$a_{n + 1} = \sum _{d \cdot s = n} \dfrac{n!}{d! \cdot (s!)^k} \cdot a_s^k$$

根据初始状态 $a_1 = 1$，枚举 $s = 1, 2, \ldots, n - 1$ 和 $d = 1, 2, \ldots, \left\lfloor\dfrac{n - 1}{s}\right\rfloor$ 逐个更新答案即可。

最终的时间复杂度为 $O(n \log n)$，空间复杂度为 $O(n)$。