题目背景

33DAI 最近做洛谷的 CSP-J 第一轮模拟赛时看到了下面这道题目。

假设有一组字符 {g,h,i,j,k,l}，它们对应的频率分别为 $8\%,14\%,17\%,20\%,23\%,18\%$。
请问以下哪个选项是字符 g,h,i,j,k,l 分别对应的一组哈夫曼编码？（ ）

• A. g: 1100, h: 1101, i: 111, l: 10, k: 00, j: 01
• B. g: 0000, h: 001, i: 010, l: 011, k: 10, j: 11
• C. g: 111, h: 110, i: 101, l: 100, k: 01, j: 00
• D. g: 110, h: 111, i: 101, l: 100, k: 0, j: 01

33DAI 发现直接哈夫曼树上构建的话，怎么都得不到某个选项。然后才学到了原来哈夫曼编码只需要保证长度没问题，且任意一个编码都不是其他编码的前缀即可。感谢洛谷带来的小知识。

题目描述

有 $n$ 个单词，编号从 $1\sim n$。第 $i$ 个单词的出现的次数为 $a_i$。

33DAI 对这些单词进行了二进制编码，第 $i$ 个单词编码后的二进制数用一个字符串 $s_i$ 表示。

请你判断 33DAI 的编码是不是这个出现次数下合法的哈夫曼编码。

• 如果是，输出 Yes，并计算出按照这个编码的文章总长度（二进制位数）。
• 否则，输出 No，并给出一组满足要求的哈夫曼编码。

注意：本题中只要保证了在该二进制编码下，文章总长度能达到最短；且任意一个编码都不是其他编码的前缀；就认为是一个合法的哈夫曼编码。

输入格式

第一行是 $n$。

第二行为空格隔开的 $a_1\sim a_n$

接下来 $n$ 行，第 $i$ 行为 $s_i$

输出格式

按题目要求输出：

• 如果输入的是哈夫曼编码，输出两行：
  • 第一行为 Yes
  • 第二行为这个编码下的文章总长度
• 如果输入的不是哈夫曼编码，输出 $n+1$ 行：
  • 第一行为 No
  • 接下来 $n$ 行第 $i$ 行为第 $i$ 个单词对应的哈夫曼编码。
  • 如果有多种方案，输出任意一种即可。

6
8 14 17 20 23 18 
111
110
101
00
01
100

Yes
257

6
8 14 17 20 23 18 
0000
001
010
11
10
011

No
111
110
101
00
01
100

1
99
0

Yes
99

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 60$，$1\le a_i\le 1000$，$1\le |s_i|\le 100$。保证 $s_i$ 仅有字符 0,1 构成，$|s_i|$ 表示字符串 $s_i$ 的长度。

• 子任务 1（10 分）：保证 $n=1$。
• 子任务 2（20 分）：保证输入的编码是一套哈夫曼编码。
• 子任务 3（30 分）：保证输入的编码任意一个都不是其他的编码的前缀。
• 子任务 4（40 分）：没有特殊限制。

---

扩展阅读

以防你不知道怎么求出一种哈夫曼编码，下面是 OIWiki 中关于哈夫曼编码相关的介绍。

树的带权路径长度

设二叉树具有 $n$ 个带权叶结点，从根结点到各叶结点的路径长度与相应叶节点权值的乘积之和称为 树的带权路径长度（Weighted Path Length of Tree，WPL）。

设 $w_i$ 为二叉树第 $i$ 个叶结点的权值，$l_i$ 为从根结点到第 $i$ 个叶结点的路径长度，则 WPL 计算公式如下：

$$WPL=\sum_{i=1}^nw_il_i$$

如上图所示，其 WPL 计算过程与结果如下：

$$WPL=2*2+3*2+4*2+7*2=4+6+8+14=32$$

结构

对于给定一组具有确定权值的叶结点，可以构造出不同的二叉树，其中，WPL 最小的二叉树 称为 霍夫曼树（Huffman Tree）。

对于霍夫曼树来说，其叶结点权值越小，离根越远，叶结点权值越大，离根越近，此外其仅有叶结点的度为 $0$，其他结点度均为 $2$。

霍夫曼算法

霍夫曼算法用于构造一棵霍夫曼树，算法步骤如下：

1. 初始化：由给定的 $n$ 个权值构造 $n$ 棵只有一个根节点的二叉树，得到一个二叉树集合 $F$。
2. 选取与合并：从二叉树集合 $F$ 中选取根节点权值 最小的两棵 二叉树分别作为左右子树构造一棵新的二叉树，这棵新二叉树的根节点的权值为其左、右子树根结点的权值和。
3. 删除与加入：从 $F$ 中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到 $F$ 中。
4. 重复 2、3 步，当集合中只剩下一棵二叉树时，这棵二叉树就是霍夫曼树。

霍夫曼编码

在进行程序设计时，通常给每一个字符标记一个单独的代码来表示一组字符，即 编码。

在进行二进制编码时，假设所有的代码都等长，那么表示 $n$ 个不同的字符需要 $\left \lceil \log_2 n \right \rceil$ 位，称为 等长编码。

如果每个字符的 使用频率相等，那么等长编码无疑是空间效率最高的编码方法，而如果字符出现的频率不同，则可以让频率高的字符采用尽可能短的编码，频率低的字符采用尽可能长的编码，来构造出一种 不等长编码，从而获得更好的空间效率。

在设计不等长编码时，要考虑解码的唯一性，如果一组编码中任一编码都不是其他任何一个编码的前缀，那么称这组编码为 前缀编码，其保证了编码被解码时的唯一性。

霍夫曼树可用于构造 最短的前缀编码，即 霍夫曼编码（Huffman Code），其构造步骤如下：

1. 设需要编码的字符集为：$d_1,d_2,\dots,d_n$，他们在字符串中出现的频率为：$w_1,w_2,\dots,w_n$。
2. 以 $d_1,d_2,\dots,d_n$ 作为叶结点，$w_1,w_2,\dots,w_n$ 作为叶结点的权值，构造一棵霍夫曼树。
3. 规定哈夫曼编码树的左分支代表 $0$，右分支代表 $1$，则从根结点到每个叶结点所经过的路径组成的 $0$、$1$ 序列即为该叶结点对应字符的编码。