下面代码实现了哈夫曼编码，则横线处应填写的代码是（ ）。

class Symbol:
    def __init__(self, ch='', freq=0, code=''):
        self.ch = ch
        self.freq = freq
        self.code = code


class Node:
    def __init__(self, w=0, l=-1, r=-1, sym=-1):
        self.w = w
        self.l = l
        self.r = r
        self.sym = sym


def pop_min_node(nodes, leaf_idx, n, pA, internal_idx, pB):
    if pA[0] < n and (pB[0] >= len(internal_idx) or nodes[leaf_idx[pA[0]]].w <= nodes[internal_idx[pB[0]]].w):
        res = leaf_idx[pA[0]]
        pA[0] += 1
        return res
    else:
        res = internal_idx[pB[0]]
        pB[0] += 1
        return res


def dfs_build_codes(u, nodes, sym_list, path):
    if u == -1:
        return
    if nodes[u].sym != -1:
        sym_list[nodes[u].sym].code = ''.join(path)
        return
    path.append('0')
    dfs_build_codes(nodes[u].l, nodes, sym_list, path)
    path.pop()
    path.append('1')
    dfs_build_codes(nodes[u].r, nodes, sym_list, path)
    path.pop()


def build_huffman_codes(sym_list):
    n = len(sym_list)
    for sym in sym_list:
        sym.code = ''
    if n <= 0:
        return -1
    if n == 1:
        sym_list[0].code = '0'
        return 0

    nodes = []
    leaf_idx = []
    for i in range(n):
        leaf_idx.append(len(nodes))
        nodes.append(Node(sym_list[i].freq, -1, -1, i))
    leaf_idx.sort(key=lambda x: (nodes[x].w, nodes[x].sym))

    internal_idx = []
    pA = [0]
    pB = [0]
    for k in range(1, n):
        x = pop_min_node(nodes, leaf_idx, n, pA, internal_idx, pB)
        y = pop_min_node(nodes, leaf_idx, n, pA, internal_idx, pB)
        z = len(nodes)
        # 补全缺失的构建内部节点代码（原代码空白处）
        nodes.append(Node(w=nodes[x].w + nodes[y].w, l=x, r=y, sym=-1))
        internal_idx.append(z)

    root = internal_idx[-1] if internal_idx else -1
    path = []
    dfs_build_codes(root, nodes, sym_list, path)
    return root


if __name__ == "__main__":
    syms = [
        Symbol('A', 5),
        Symbol('B', 9),
        Symbol('C', 12),
        Symbol('D', 13),
        Symbol('E', 16),
        Symbol('F', 45)
    ]
    root = build_huffman_codes(syms)
    print(f"哈夫曼树根节点下标：{root}")
    for sym in syms:
        print(f"字符 '{sym.ch}' (频率 {sym.freq})：编码 {sym.code}")

nodes.append(Node(nodes[x].w + nodes[y].w, x, y, -1)) 
internal_idx.append(z)

nodes.append(Node(nodes[x].w + nodes[y].w, x, y, 1)) 
internal_idx.append(z)

nodes.append(Node(nodes[x-1].w + nodes[y].w, x, y, 1)) 
internal_idx.append(z)

nodes.append(Node(nodes[x+1].w + nodes[y].w, x, y, 1)) 
internal_idx.append(z)

以下代码中，构造函数被调用的次数是1次。

class Test: 
    init_count = 0 
    def __init__(self): 
        Test.init_count += 1 
        print("T ", end="") 
    def __copy__(self): 
        print("（拷贝构造，不触发__init__）", end="") 
        new_obj = Test.__new__(Test) 
        return new_obj 
if __name__ == "__main__": 
    a = Test() 
    import copy 
    b = copy.copy(a)

在二叉排序树（Binary Search Tree, BST）中，假设节点值互不相同。给定如下搜索函数，以下说法 一定正确的是（ ）。

class Node: 
    def __init__(self, val=0, left=None, right=None): 
        self.val = val 
        self.left = left 
        self.right = right 
def find(root, x): 
    while root: 
        if root.val == x: 
            return True 
        if x < root.val: 
            root = root.left 
        else: 
            root = root.right 
    return False

面向对象编程中，封装是指将数据和操作数据的方法绑定在一起，并对外隐藏实现细节。

路径覆盖

时间限制：3.0 s

内存限制：512.0 MB

题目描述

给定一棵有 n 个结点的有根树 T ，结点依次以 1 , 2, . , n 编号 ，根结点编号为 1 。方便起见 ，编号为 i 的结点称为结点 i。

初始时 T 中的结点均为白色。你需要将 T 中的若干个结点染为黑色，使得所有叶子到根的路径上至少有一个黑色结

点。将结点 i 染为黑色需要代价 c，你需要在满足以上条件的情况下，最小化染色代价之和。

叶子是指 T 中没有子结点的结点。

 输入格式

第一行，一个正整数 n，表示结点数量。

输出格式

一行，一个整数，表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下，染色代价之和的最小值。

输入样例 1

4
1 2 3
5 6 2 3

输出样例 1

2

 输入样例 2

7
1 1 2 2 3 3
64 16 15 4 3 2 1

输出样例 2

10

数据范围