数位动规。

必须承认本题出得不好（我太菜了），因为「子树有序」这条件实在不优雅。

将 $n$ 节点、子树有序的有根树转化为长度为 $2(n-1)$ 的括号序列，问题便相当显豁了。

会了吧？

—

——

———

————

———

——

—

设状态 $s_{i,j}$ 代表括号序列的前 $i$ 位、左括号比右括号多 $j$ 个的情况数。当 $j\gt0$ 时，$s_{i,j}$ 可以转移到 $s_{i+1,j-1}$；当 $j\lt k-1$ 时，$s_{i,j}$ 可以转移到 $s_{i+1,j+1}$。

初始条件为 $s_{0,0}=1$，答案为 $s_{2(n-1),0}$，效率为 $\Theta(nk)$，现有数据已经无恙；矩阵优化可至 $\Theta(k^3\log n)$，我未来可能会补充下 $n$ 较大的数据。

由于是大水题，代码非常好写，就不放标程了。

——故国神游，多情应笑我，早生华发。