U283467 看着很眼熟但是又很难的哈夫曼树

在考研复习《数据结构》科目时，大家对于哈夫曼树应该都很熟悉了，那么这里我们也来做一些有关哈夫曼树的题目。 我们知道， $2$ 叉哈夫曼树可以表示的场景为：给定 $n$ 个节点，以及每个节点的权值 $a_i(1\le i \le n)$，每次合并其中 $2$ 个节点，假设合并的两个点权值是 $a_i$ 和 $a_j$ ，那么这次合并的代价为 $a_i+a_j$ 。在哈夫曼树中，合并之后的新节点便是这两个节点的父节点，权值为此次合并的代价。 不难得到 $2$ 叉哈夫曼树的根节点的权值，就是这 $n$ 个节点的总和。我们在平时学习的过程中，研究的就是如何让这 $n$ 个节点通过 $n-1$ 次合并之后，最终只剩下 $1$ 个节点这个过程**的代价总和最小。** 同理，我们可以定义 $k$ 叉哈夫曼树的合并过程。 在 $n$ 个节点中，每次我们选择**至多 $k$ 个节点**进行合并为一个新节点，每次合并的代价即为每次合并时选择的节点权值总和，合成的新节点的权值即为这个代价。 我们需要考虑一种合并方案，使得合并的代价总和最小。

在本题中，我们给定 $n$ 个节点，根据上面 $k$ 叉哈夫曼树的问题，求解 $k=2,3,...,n$ 时，合并这些节点所需要的最小代价总和。

每个测试点包括一组数据，共两行。 第一行一个正整数 $n$ ，表示一共有 $n$ 节点。 第二行 $n$ 个自然数 $a_1,...,a_n$ ，表示这些节点的权值。

输出 $n-1$ 个整数，表示 $k=2,3,...,n$ 时，合并这些节点的最小代价总和。

### 样例 1 解释 $k=2$ 时，先合并 $1,2$ ，得到一个权值为 $3$ 的新节点；再合并 $3,3$ ，得到一个权值为 $6$ 的新节点；再合并 $4,6$ ，得到权值为 $10$ 的节点。合并总代价为 $3+6+10=19$。 $k=3$ 时，先合并 $1,2$ ，得到一个权值为 $3$ 的新节点，再合并 $3,3,4$ ，得到权值为 $10$ 的节点。合并总代价为 $3+10=13$ 。可以注意到，第一次合并我们并没有选择可合并的个数上限进行操作。 $k=4$ 时，直接合并 $4$ 个节点即可，代价为 $10$。 ## 数据范围 对于 $30\%$ 的数据有 : $n\le 100$ 。 对于 $60\%$ 的数据有 : $n\le 2\times 10^3$ 。 对于 $100\%$ 的数据有 : $n\le 2\times 10^5, 0\le a_i\le 10^6$ 。