Problem p03026 (python)

Fixed submission:

def input_from_console():
    n = int(input())
    a_list, b_list = [], []
    for i in range(n - 1):
        data = input()
        a, b = map(int, data.split())
        if b > a:
            a, b = b, a  # swap smaller one.
        a_list.append(a)
        b_list.append(b)
    c_list = []
    c_list = list(map(int, input().split()))
    return n, a_list, b_list, c_list


def solve(n, a_list, b_list, c_list):
    edge = [[] for i in range(n)]
    for i in range(len(a_list)):
        a, b = a_list[i] - 1, b_list[i] - 1  # convert to 0 based index.
        edge[a].append(b)
        edge[b].append(a)
    c_list_new = sorted(c_list, reverse=True)

    value = sum(c_list_new[1:])

    vertices = [None] * n
    vertices[0] = c_list_new.pop(0)

    search_path = []
    search_path.extend(edge[0])

    while search_path:
        node = search_path.pop(0)
        if vertices[node] is None:
            vertices[node] = c_list_new.pop(0)
            search_path.extend(edge[node])
    return str(value) + '\n' + ' '.join(map(str, vertices))


def main():
    n, a_list, b_list, c_list = input_from_console()
    print(solve(n, a_list, b_list, c_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

Buggy submission (verdict: Runtime Error):

def input_from_console():
    n = int(input())
    a_list, b_list = [], []
    for i in range(n - 1):
        data = input()
        a, b = map(int, data.split())
        if b > a:
            a, b = b, a  # swap smaller one.
        a_list.append(a)
        b_list.append(b)
    c_list = list(map(int, input().split()))
    return n, a_list, b_list, c_list


def solve(n, a_list, b_list, c_list):
    edge = [[] for i in range(n)]  # 0 based list of list.
    for i in range(len(a_list)):
        a, b = a_list[i] - 1, b_list[i] - 1  # convert to 0 based index.
        edge[a].append(b)
        edge[b].append(a)
    c_list.sort(reverse=True)
    graph_value = sum(c_list[1:])  # edge should have the value except the maximum.
    
    vertices = [None] * n
    
    def depth_first_search(node):
        vertices[node] = c_list.pop(0)
        
        for next_node in edge[node]:
            if vertices[next_node] is None:
                depth_first_search(next_node)

    depth_first_search(0)

    return "{:d}\n{}".format(graph_value, ' '.join(map(str, vertices)))


def main():
    n, a_list, b_list, c_list = input_from_console()
    print(solve(n, a_list, b_list, c_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

Buggy submission (verdict: Runtime Error):

def input_from_console():
    n = int(input())
    a_list, b_list = [], []
    for i in range(n-1):
        data = input()
        a, b = map(int, data.split())
        if b > a:
            a, b = b, a  # swap smaller one.
        a_list.append(a)
        b_list.append(b)
    c_list = []
    c_list = list(map(int, input().split()))
    lr_list = []
    return n, a_list, b_list, c_list


def solve(n, a_list, b_list, c_list):
    total = 0
    c_list = sorted(c_list, reverse=True) # Because maximum number is not selected at all.
    import itertools
    current_max = 0
    current_list = []

    c_list_new = [c_list[item-1] for item in set(a_list + b_list)]
    for new_list in itertools.permutations(c_list_new, n):
        total = 0
        for i in range(n - 1):
            total += min(new_list[a_list[i]-1], new_list[b_list[i]-1])
        if total >= current_max:
            current_max = total
            current_list = new_list

    return f"{current_max}\n" + " ".join(map(str, current_list))


def main():
    n, a_list, b_list, c_list = input_from_console()
    print(solve(n, a_list, b_list, c_list))

Buggy submission (verdict: Runtime Error):

def input_from_console():
    n = int(input())
    a_list, b_list = [], []
    for i in range(n-1):
        data = input()
        a, b = map(int, data.split())
        if b > a:
            a, b = b, a  # swap smaller one.
        a_list.append(a)
        b_list.append(b)
    c_list = []
    c_list = list(map(int, input().split()))
    lr_list = []
    return n, a_list, b_list, c_list


def solve(n, a_list, b_list, c_list):
    total = 0
    c_list = sorted(c_list, reverse=True) # Because maximum number is not selected at all.
    import itertools
    current_max = 0
    current_list = []
    for new_list in itertools.permutations(c_list, n):
        total = 0
        for i in range(n - 1):
            total += min(new_list[a_list[i]-1], new_list[b_list[i]-1])
        if total >= current_max:
            current_max = total
            current_list = new_list

    return f"{current_max}\n" + " ".join(map(str, current_list))


def main():
    n, a_list, b_list, c_list = input_from_console()
    print(solve(n, a_list, b_list, c_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()