KMO

转化为树

$K$ 元前缀码的码长满足克拉夫特不等式 $\sum K^{-b_i}\leq1$，反之亦然。将长度排序，逐层把未使用的位置扩展成 $K$ 个子位置，再放置当前层所需的叶子，即可得到对应的树。

因此，问题等价于构造一棵每个内部结点至多有 $K$ 个孩子的树，使叶子权值与深度乘积之和最小。权值为 $0$ 的输入元素也是实际叶子，不能删除。

哈夫曼合并

$N=1$ 时输出 $0$。否则，每个内部结点恰有 $K$ 个孩子的树，其叶子数模 $K-1$ 余 $1$。补充

$$d=(K-1-(N-1)\bmod(K-1))\bmod(K-1)$$

个权值为零的虚拟叶子。该操作不改变最优值：去掉最优树中的单子结点，并将未满的内部结点合并整理到最深处，只保留一个未满结点。把叶子向根移动不会增加非负权值的总代价。补满剩余位置恰好需要 $d$ 个虚拟叶子。

通过交换较浅的轻叶子和较深的重叶子，可知存在一个最优解，使最小的 $K$ 个权值对应的叶子位于最深层且拥有同一父结点。将它们缩成一个权值等于总和的叶子，原代价等于缩点后的代价加上这个总和。不断执行此操作即为 $K$ 元哈夫曼算法。

实现时不必建立虚拟叶子。第一次合并

$$r=2+(N-2)\bmod(K-1)$$

个实际结点，之后每次合并 $K$ 个结点即可。$K>N$ 时有 $r=N$；当 $N-1$ 能被 $$ 整除时，第一次也必须合并 个。

用最小堆选取结点，记录新结点为所取结点的父结点。父结点编号总是较大，因此按编号逆序计算深度，无需递归。按原输入顺序输出叶子深度。

内部结点至多有 $N-1$ 个且每个至少有两个孩子，所以深度至多为 $N-1$。时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。合并权值不超过 ；令所有深度等于 可得可行解，所以最优代价不超过 。有符号 位整数足够，无需直接计算 。

子任务 1 可将权值降序排序，再枚举取值为 $0$ 至 $N-1$ 的非递减深度序列，共 $\binom{2N-1}{N}$ 个。交换论证保证其中存在最优解。每个序列用 检查，总复杂度为 。子任务 2 使用二元哈夫曼算法，每次合并最小的两个权值，复杂度为 。

检查克拉夫特不等式时，从深度零的一个空位开始，扣除本层叶子数，再将剩余空位乘以 $K$。需要的叶子数超过空位数则不合法。空位数可截断至 $N+1$，避免大整数，因为总共只有 $N$ 个叶子。检查总代价时，以最优值作为剩余预算，在乘法前先用除法判断是否超出预算，避免错误输出造成溢出。

Solution written by GPT6