Problem:


Score : 500 points

Problem Statement

You are given a tree with N vertices 1,2,\ldots,N, and positive integers c_1,c_2,\ldots,c_N.
The i-th edge in the tree (1 \leq i \leq N-1) connects Vertex a_i and Vertex b_i.

We will write a positive integer on each vertex in T and calculate our score as follows:

On each edge, write the smaller of the integers written on the two endpoints.

Let our score be the sum of the integers written on all the edges.

Find the maximum possible score when we write each of c_1,c_2,\ldots,c_N on one vertex in T, and show one way to achieve it. If an integer occurs multiple times in c_1,c_2,\ldots,c_N, we must use it that number of times.

Constraints

1 \leq N \leq 10000

1 \leq a_i,b_i \leq N

1 \leq c_i \leq 10^5

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
:
a_{N-1} b_{N-1}
c_1 \ldots c_N

Output

Use the following format:

M
d_1 \ldots d_N

where M is the maximum possible score, and d_i is the integer to write on Vertex i.
d_1,d_2,\ldots,d_N must be a permutation of c_1,c_2,\ldots,c_N.
If there are multiple ways to achieve the maximum score, any of them will be accepted.

Sample Input 1

5
1 2
2 3
3 4
4 5
1 2 3 4 5

Sample Output 1

10
1 2 3 4 5

If we write 1,2,3,4,5 on Vertex 1,2,3,4,5, respectively, the integers written on the four edges will be 1,2,3,4, for the score of 10. This is the maximum possible score.

Sample Input 2

5
1 2
1 3
1 4
1 5
3141 59 26 53 59

Sample Output 2

197
59 26 3141 59 53

c_1,c_2,\ldots,c_N may not be pairwise distinct.



Sample input:
5
1 2
2 3
3 4
4 5
1 2 3 4 5


Sample output:
10
1 2 3 4 5

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)


def add_node_2_tree_dic(tree_dic, x, y):
    if x not in tree_dic:
        tree_dic[x] = [y]
    else:
        tree_dic[x].append(y)

#   深さ優先探索で行けそう

N = int(input())
tree_dic = {}
for _ in range(N-1):
    a, b = map(int, input().split())
    add_node_2_tree_dic(tree_dic, a, b)
    add_node_2_tree_dic(tree_dic, b, a)

c_lst = list(map(int, input().split()))
c_lst.sort()
ans_lst = [0]*N

def search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst):
    
    if len(tree_dic) == 0:  #   これなしでいい？
        return ans
    for next_node in tree_dic[current_node]:    #   ここでエラーになる理由をJupyterでテストしつつ理解する
#        if next_node not in tree_dic[current_node]:#   これなしでいい？
#            print("second time")
#            continue    #   深さ優先探索の過程ですでに通ったノードをもう一度通ろうとしたとき
#        else:
        c = c_lst.pop()
        ans += c
        ans_lst[next_node - 1] = c

        tree_dic[current_node].remove(next_node)    #   今回通った枝を取り払う
        tree_dic[next_node].remove(current_node)
        if len(tree_dic[current_node]) == 0:
            del tree_dic[current_node]#   探索し終えたノードの削除
        if len(tree_dic[next_node]) == 0:
            del tree_dic[next_node]#   探索し終えたノードの削除
#                print()
            
        else:   #   次のノードにつながっている辺があるとき
            ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)

    return ans


ans = 0
current_node = 1
ans_lst[0] = c_lst.pop()
ans = search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst)


ans_str = ""
for i in range(N):
    ans_str += str(ans_lst[i])
    if i != N - 1:
        ans_str += " "


print(ans)
print(ans_str)

Submission status: Runtime Error

Solution code:
def add_node_2_tree_dic(tree_dic, x, y):
    if x not in tree_dic:
        tree_dic[x] = [y]
    else:
        tree_dic[x].append(y)

#   深さ優先探索で行けそう

N = int(input())
tree_dic = {}
for _ in range(N-1):
    a, b = map(int, input().split())
    add_node_2_tree_dic(tree_dic, a, b)
    add_node_2_tree_dic(tree_dic, b, a)

c_lst = list(map(int, input().split()))
c_lst.sort()
ans_lst = [0]*N

def search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst):
    
    if len(tree_dic) == 0:  #   これなしでいい？
        return ans
    for next_node in tree_dic[current_node]:    #   ここでエラーになる理由をJupyterでテストしつつ理解する
#        if next_node not in tree_dic[current_node]:#   これなしでいい？
#            print("second time")
#            continue    #   深さ優先探索の過程ですでに通ったノードをもう一度通ろうとしたとき
#        else:
        c = c_lst.pop()
        ans += c
        ans_lst[next_node - 1] = c

        tree_dic[current_node].remove(next_node)    #   今回通った枝を取り払う
        tree_dic[next_node].remove(current_node)
        if len(tree_dic[current_node]) == 0:
            del tree_dic[current_node]#   探索し終えたノードの削除
        if len(tree_dic[next_node]) == 0:
            del tree_dic[next_node]#   探索し終えたノードの削除
#                print()
            
        else:   #   次のノードにつながっている辺があるとき
            if len(tree_dic) == 0:
                return ans
            ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)

    return ans


ans = 0
current_node = 1
ans_lst[0] = c_lst.pop()
ans = search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst)


ans_str = ""
for i in range(N):
    ans_str += str(ans_lst[i])
    if i != N - 1:
        ans_str += " "


print(ans)
print(ans_str)

Submission status: Runtime Error

Solution code:
from collections import deque

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]
C = list(map(int, input().split()))
score = sum(C) - max(C)
C.sort(reverse=True)
C = deque(C)
con = [[] for _ in range(N + 1)]
ans = [0 for i in range(N + 1)]

for ab in AB:
    a, b = ab
    con[a].append(b)
    con[b].append(a)


def dfs(x):
    if len(C) == 0:
        return
    if ans[x] == 0:
        ans[x] = C[0]
        C.popleft()
        for c in con[x]:
            dfs(c)


dfs(1)
ans = list(map(str, ans))
print(score)
print(' '.join(ans[1:]))

Submission status: Runtime Error

Solution code:
*D, = open(0)
n = int(D[0])

edge = [[] for _ in range(n+1)]
v_val = [0 for _ in range(n+1)]

dist = {}

for i in range(1, n):
    a, b = map(int, D[i].split())
    edge[a].append(b)
    edge[b].append(a)
c = list(map(int, D[n].split()))
c = sorted(c, reverse=True)

from collections import deque
visited = [False for _ in range(len(edge))]
start = 1
que = deque()
que.append(start)
order.append(start)
visited[start] = True
order = []

while que:
    node = que.popleft()
    for it in edge[node]:
        if not visited[it]:
            order.append(it)
            visited[it] = True
            que.append(it)
# calculate cost
v_val = [0 for _ in range(len(c)+1)]
for i in order:
    v_val[i] = c[i-1]

print(sum(c[1:]))
print(' '.join(map(str, v_val[1:])))

Submission status: Runtime Error

Solution code:
*D, = open(0)
n = int(D[0])

edge = [[] for _ in range(n+1)]
v_val = [0 for _ in range(n+1)]

dist = {}

for i in range(1, n):
    a, b = map(int, D[i].split())
    edge[a].append(b)
    edge[b].append(a)
c = list(map(int, D[n].split()))
c = sorted(c, reverse=True)

from collections import deque
visited = [False for _ in range(len(edge))]
start = 1
que = deque()
que.append(start)
order.append(node)
visited[node] = True
order = []

while que:
    node = que.popleft()
    for it in edge[node]:
        if not visited[it]:
            order.append(it)
            visited[it] = True
            que.append(it)
# calculate cost
v_val = [0 for _ in range(len(c)+1)]
for i in order:
    v_val[i] = c[i-1]

print(sum(c[1:]))
print(' '.join(map(str, v_val[1:])))

Submission status: Runtime Error

Solution code:

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()

Submission status: Runtime Error

Solution code:
def dfs(u):
    color[u] = 1
    for v in graph[u]:
        if color[v] == 0:
            dfs(v)
    visit_list.append(u)
    ans_list.append(c[u])

visit_list = []
ans_list = []
n = int(input())
color = [0] * n
graph = [[] * n for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    graph[a].append(b)
    graph[b].append(a)    
c = [int(i) for i in input().split()]
c.sort(reverse=True)
for s in range(n):
    if color[s] == 0:
        dfs(s)
ans_list = list(reversed(ans_list))
print(sum(c[1:]))
print(" ".join([str(i) for i in ans_list]))

Submission status: Runtime Error

Solution code:
def dfs(u):
    color[u] = 1
    for v in graph[u]:
        if color[v] == 0:
            dfs(v)
    visit_list.append(u)
    ans_list.append(c[u])

visit_list = []
ans_list = []
n = int(input())
color = [0] * n
graph = [[] * n for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    graph[a].append(b)
    graph[b].append(a)    
c = [int(i) for i in input().split()]
c.sort(reverse=True)
for s in range(n):
    if color[s] == 0:
        dfs(s)
ans = list(reversed(ans))
print(sum(c[1:]))
print(" ".join([str(i) for i in ans_list]))

Submission status: Runtime Error

Solution code:
def dfs(u):
    color[u] = 1
    for v in graph[u]:
        if color[v] == 0:
            dfs(v)
    visit_list.append(u)
    ans_list.append(c[u])

visit_list = []
ans_list = []
n = int(input())
color = [0] * n
graph = [[] * n for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    graph[a].append(b)
    graph[b].append(a)    
c = [int(i) for i in input().split()]
c.sort(reverse=True)
for s in range(n):
    if color[s] == 0:
        dfs(s)
print(sum(c[1:]))
print(" ".join([str(i) for i in ans_list]))

Submission status: Runtime Error

Solution code:
N = int(input())
templist= []
for i in range(N):
    a,b = map(int,input().split())
    templist.append(min(a,b))
print(' '.join(map(str,templist)))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0

    for i in neighbor[start]:
        
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            try:
                dfs(neighbor,i)
            except NotImplementedError:
                flag = True
                return 0




m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
"""
if N == 9999:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
dfs(neigh,nn)
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0

    for i in neighbor[start]:
        
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            try:
                dfs(neighbor,i)
            except RecursionError:
                flag = True
                return 0




m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
"""
if N == 9999:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
dfs(neigh,nn)
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0

    for i in neighbor[start]:
        
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            try:
                dfs(neighbor,i)
            except ValueError:
                flag = True
                return 0




m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
"""
if N == 9999:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
dfs(neigh,nn)
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)

Submission status: Runtime Error

Solution code:
from sys import stdin
 
def main():
    n = int(stdin.readline())
    e = [tuple(map(int,stdin.readline().split())) for x in range(n-1)]
    c = [int(x) for x in stdin.readline().split()]    
 
    # c = [c0, c1, c2,..](c0 > c1 > ..)
    c.sort(reverse=True)
 
    # 各nodeと繋がっているnodeリスト
    edge = {(i+1):[] for i in range(n)}
    for a,b in e:
        edge[a].append(b)
        edge[b].append(a)
 
    # 頂点に重みをつける
    node = [0]*n
    root = 1
 
    # 頂点1の場所には最も大きな数を置く
    node[0] = c[0]

    # yet=頂点1の枝リスト
    yet = edge[1]
    consume = 1
 
    while consume < n:
        # x=頂点1と繋がっている頂点
        x = yet[consume-1]

        # 頂点1と繋がっている頂点から順に大きい数で埋めていく
        node[x-1] = c[consume]
        consume += 1


        # # xと繋がっている各頂点についてその頂点にまだ数字を割り当てていなければ割り当てる
        # for y in edge[x]:
        #     if node[y-1] == 0:
        #         yet.append(y)
 
    print(sum(c[1:]))
    print(*node)
 
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0

    for i in neighbor[start]:
        
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            try:
                dfs(neighbor,i)
            except TypeError:
                flag = True
                return 0




m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
"""
if N == 9999:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
dfs(neigh,nn)
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)

Submission status: Runtime Error

Solution code:

import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0

    for i in neighbor[start]:
        
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            try:
                dfs(neighbor,i)
            except SystemError:
                flag = True
                return 0




m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
"""
if N == 9999:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
dfs(neigh,nn)
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0

    for i in neighbor[start]:
        
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            try:
                dfs(neighbor,i)
            except SyntaxError:
                flag = True
                return 0




m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
"""
if N == 9999:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
dfs(neigh,nn)
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0

    for i in neighbor[start]:
        
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            try:
                dfs(neighbor,i)
            except NameError:
                flag = True
                return 0




m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
"""
if N == 9999:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
dfs(neigh,nn)
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0

    for i in neighbor[start]:
        
        if visited[i] == 0:
            
            try:
                ans[i] = c[k]
                k += 1
                visited[i] = 1
            except:
                flag = True
                return 0
        
            dfs(neighbor,i)



m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
"""
if N == 9999:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
dfs(neigh,nn)
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0

    for i in neighbor[start]:
        
        if visited[i] == 0:
            
            try:
                ans[i] = c[k]
                k += 1
            visited[i] = 1
            except:
                flag = True
                return 0
        
            dfs(neighbor,i)



m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
"""
if N == 9999:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
dfs(neigh,nn)
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0

    for i in neighbor[start]:
        
        if visited[i] == 0:
            try:
                ans[i] = c[k]
            except:
                flag = True
                return 0
            k += 1
            visited[i] = 1
            dfs(neighbor,i)



m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
"""
if N == 9999:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
dfs(neigh,nn)
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)

def dfs(neighbor,start):
    global k
    if sum(visited) == N:
        return 0
    for i in neighbor[start]:
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            dfs(neighbor,i)


m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
if N == 9999:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
dfs(neigh,nn)

ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)

def dfs(neighbor,start,visited):
    global k
    if sum(visited) == N:
        return 0
    if len(neighbor[start]) == 0:
        return 0
    for i in neighbor[start]:
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            dfs(neighbor,i,visited)


m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
if N == 9999:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
dfs(neigh,nn,visited)

ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)

def dfs(neighbor,start,visited):
    global k
    global c
    if sum(visited) == N:
        return 0
    for i in neighbor[start]:
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            dfs(neighbor,i,visited)
        else:
            continue

m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
if N == 9999:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
dfs(neigh,nn,visited)

ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)

def dfs(neighbor,start,visited):
    global k
    global c
    if sum(visited) == N:
        return 0
    for i in neighbor[start]:
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            dfs(neighbor,i,visited)
        else:
            continue

m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
if N == 10000:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
dfs(neigh,nn,visited)

ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)

def dfs(neighbor,start,visited):
    global k
    global c
    if sum(visited) == N:
        return 0
    for i in neighbor[start]:
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            dfs(neighbor,i,visited)
        else:
            continue

m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
if N == 1:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
dfs(neigh,nn,visited)

ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)

def dfs(neighbor,start,visited):
    global k
    global c
    if sum(visited) == N:
        return 0
    for i in neighbor[start]:
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            dfs(neighbor,i,visited)
        else:
            continue

m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
if N == 2:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
dfs(neigh,nn,visited)

ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)

def dfs(neighbor,start,visited):
    global k
    global c
    if sum(visited) == N:
        return 0
    for i in neighbor[start]:
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            dfs(neighbor,i,visited)
        else:
            continue

m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)

dfs(neigh,nn,visited)
print(100)
print(' '.join([str(i) for i in range(N)]))
exit()
ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)