题目内容

现有一棵$n$个节点构成的哈夫曼树，哈夫曼树的定义如下: 1.每个节点要么没有父节点连接(此时该节点被称为根节点$^1$)、要么被$1$个父节点连接(此时该节点被称为父节点的子节点$^2$); 2.每个节点连接的子节点$^2$数量要么为$0$(此时该节点被称为“叶子节点$^3$”)、要么小于等于$2$;

3.如果存在子节点$^2$，节点权值为左右子节点$^2$的权值之和，且左子节点$^2$权值小于等于右子节点$^2$;

4.哈夫曼树的所有节点权值之和尽可能小，即权值越小的叶子节点$^3$在树中的位置越靠下;

5.同一层节点的权值从左到右依次增大。

如下为一棵哈夫曼树:

​                               5

​                             /    \

​                            2      3

​                                 /   \

​                                1      2

某个节点的哈夫曼编码是指在从哈夫曼树的“根节点”开始、到某个节点的路径，其中左边权的权值为$0$，右边权的权值为$1$。按路径顺序读取的边权值即为某个节点的哈夫曼编码，如上述哈夫曼树中，从左到右三个“叶子节点”的哈夫曼编码分别为$[0,10,11]$。

小红现在得到一棵哈夫曼树的每个“叶子节点”的哈夫曼编码以及“叶子节点”的权值集合(顺序随机给出)，小红希望你能将该哈夫曼树恢复出来。

补充说明

函数的第一个参数输入一个长度为$n(2≤n≤2×10^5)$的$vector$<$string$>类$leaf_1,leaf_2,...,leaf_n,leaf_i$是"$01$"组成的字符串，代表叶子节点的哈夫曼编码$leaf$，保证其为最小哈夫曼编码。

函数的第二个参数输入一个长度为$n(2≤n≤2×10^5)$的$vector$类$value_1,value_2,...,value_n(l≤value_i≤10^4)$代表“叶子节点”的权值集合$value$。

注:该题为核心模式，不需要自己处理输入输出，代码中的类名、方法名、参数名已经指定，请勿修改，直接书写函数返回方法规定的值即可。

示例1

输入

["0","10","11"],[2,1,2]

输出

{5,2,3,#,#,1,2}

说明

恢复的哈夫曼树结构如题意所示

示例2

输入

["0","10","110","111"],[3,1,1,2]

输出

{7,3,4,#,#,2,2,#,#,1,1}

说明

首先可以根据["0","10","110","111"]恢复出树的形态：

​                    ?

​                 /     \

​               ?         ?

​                       /    \

​                      ?      ?

然后将节点权值按照同一层左节点小于等于右节点，同时保证整棵树权值尽可能小，得到叶子节点的权值:

​                    ?

​                 /     \

​                3        ?

​                       /    \

​                      2       ?

​                            /    \

​                           1      1

如果一个节点有两个孩子，那么这个节点的权值等于两个孩子节点权值之和。

​                    7

​                 /     \

​                3        4

​                       /    \

​                      2      2

​                           /   \

​                          1     1