题目描述
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$ 个单词对应的哈夫曼编码。
- 如果有多种方案，输出任意一种即可。
样例输入输出
输入#1
复制
6
8 14 17 20 23 18
111
110
101
00
01
100
输入#2
复制
6
8 14 17 20 23 18
0000
001
010
11
10
011
输出#2
复制
No
111
110
101
00
01
100
提示
数据规模与约定
对于 $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$ 序列即为该叶结点对应字符的编码。
