上一篇文章《重编码-Huffman树WPL问题》解释了二叉Huffman树WPL问题，而这道题将二叉拓展到了K叉。

K叉与二叉的区别主要在一下几个地方

• 节点数可能不足以满足K叉Huffman树的结构，需要补充虚拟节点。
• 在弹出节点时不是弹出2个，而是K个。

再就是本体还需要输出最长字符串的最短长度，也就是Huffman编码的最长长度。这里我们用一个pair来维护该节点在Huffman树的深度，也就是所求值。

先给出参考代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long,long long>;

int n,k;
priority_queue<pll,vector<pll>,greater<pll> > q;
ll ans;

int main() {
    ios::sync_with_stdio(false);

    cin >> n >> k;

    ll temp;
    for(int i = 1; i <= n; ++i) {
        cin >> temp;
        q.push({temp,0});
    }

    while((q.size() - 1) % (k - 1)) 
        q.push({0,0});

    while(q.size() >= (unsigned long int) k) {
        ll depth = -1;
        ll sum = 0;
        for(int i = 1; i <= k ; ++i) {
            sum += q.top().first;
            depth = max(depth,q.top().second);
            q.pop();
        }

        q.push({sum,depth + 1});
        ans += sum;
    }

    cout << ans << endl << q.top().second << endl;

    return 0;
}

这里解释几个个关键性的问题：

• 为什么要使节点数满足(q.size() - 1) % (k - 1) = 0？

  为了防止在最后有节点剩余而无法合并，此时的局面不为最优解（此时答案偏小）。这个时候添加词频为0的虚拟节点可以满足K叉Huffman树的结构且不会影响到答案（相当于把节点“挤”到更优位置）。

• 如何证明这个算法是对的？

  其实和二叉Huffman树的道理是一样的，只不过我们在这里拓展成了K叉而已，如果还是无法理解算法过程可以手动模拟一遍。

  （我懒，就不放模拟过程的图了）

• 节点的深度是如何维护的？

  道理很简单，对于一个节点，我们弹出来求了一次和（sum），就相当于把这层深度上的K叉Huffman树节点“砍掉了”。这个时候我们只需要找出这之中最大深度加上1，就可以维护节点最大深度了。