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:
def intinput(): return map(int,input().split())

def ab(i):
    global c,l,x
    while len(l[i])>0:
        if x[l[i][0]]==0:
            x[l[i][0]] = c.pop(0)
        else:
            return
        l[l[i][0]].remove(i)
        ab(l[i][0])
        l[i].pop(0)
    return

n=int(input())
l = [[] for _ in range(n+1)]
for i in range(n-1):
    a,b=intinput()
    l[a].append(b)
    l[b].append(a)
c = list(intinput())
c.sort(reverse=1)
x = [0 for _ in range(n+1)]
x[1]=c.pop(0)
for i in range(1,n+1):
    ab(i)
print(sum(x[2:]))
f = ""
q= len(x[1:])
for i in range(q):
    if i != q-1:
        f += str(x[i+1])+" "
    else:
        f += str(x[i+1])
print(f)

Submission status: Runtime Error

Solution code:
n = int(input())
edge = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)

cost = list(map(int, input().split()))
c = sorted(cost, reverse=True)
w = [0] * n
w[0] = c.pop(0)
chk = [*edge[0]]

while chk != []:
    node = chk.pop(0)
    if w[node] == 0:
        w[node] = c.pop(0)
        chk.extend(edge[node])

print(sum(cost) - max(cost))
print(' '.join(map(str, w)))

Submission status: Runtime Error

Solution code:
def intinput(): return map(int,input().split())

def ab(i):
    global c,l,x
    while len(l[i])>0:
        if x[l[i][0]]==0:
            x[l[i][0]] = c.pop(0)
        else:
            return
        l[l[i][0]].remove(i)
        ab(l[i][0])
        l[i].pop(0)
    return

n=int(input())
l = [[] for _ in range(n+1)]
for i in range(n-1):
    a,b=intinput()
    l[a].append(b)
    l[b].append(a)
c = list(intinput())
c.sort(reverse=1)
x = [0 for _ in range(n+1)]
x[1]=c.pop(0)
for i in range(1,n+1):
    ab(i)
print(sum(x[2:]))
f = ""
q= len(x[1:])
for i in range(q):
    if i != q-1:
        f += str(x[i+1])+" "
    else:
        f += str(x[i+1])
print(f)def intinput(): return map(int,input().split())

def ab(i):
    global c,l,x
    while len(l[i])>0:
        if x[l[i][0]]==0:
            x[l[i][0]] = c.pop(0)
        else:
            return
        l[l[i][0]].remove(i)
        ab(l[i][0])
        l[i].pop(0)
    return

n=int(input())
l = [[] for _ in range(n+1)]
for i in range(n-1):
    a,b=intinput()
    l[a].append(b)
    l[b].append(a)
c = list(intinput())
c.sort(reverse=1)
x = [0 for _ in range(n+1)]
x[1]=c.pop(0)
for i in range(1,n+1):
    ab(i)
print(sum(x[2:]))
f = ""
q= len(x[1:])
for i in range(q):
    if i != q-1:
        f += str(x[i+1])+" "
    else:
        f += str(x[i+1])
print(f)

Submission status: Runtime Error

Solution code:
import copy
arc_ = []


N = int(input())

arc_num_for_each_node = [0]*N
len_l = 2
# N = 2 
while len_l == 2:
    line = input().split()
    len_l = len(line)
    if len_l == 2:
        arc_.append([int(line[0])-1, int(line[1])-1])
        arc_num_for_each_node[int(line[0])-1] += 1
        arc_num_for_each_node[int(line[1])-1] += 1
    else:
        c_ = [int(v) for v in line]
        
c_.sort()
      
max_value = 0
max_c = []

def get_result(arc, c_set):
    sum_v = 0
    for i in range(len(arc)):
        sum_v += min(c_set[arc[i][0]], c_set[arc[i][1]])
    return sum_v

def poi(ct, arc, c_set, ignore_list, index):
    global max_value, max_c
    if len(ct) == 0:
        result = get_result(arc, c_set)
        if result > max_value:
            max_value = result
            max_c = c_set
    elif ignore_list[index]:
        poi(ct, arc, c_set, ignore_list, index+1)
    else:
        for i in range(len(ct)):
            c_set_[index] = ct[i]
            ct_tmp = copy.deepcopy(ct)
            ct_tmp.remove(ct[i])
            poi(ct_tmp, arc, c_set, ignore_list, index+1)
            
c_set_ = [0]*N
ignore_list = [False]*N
for i in range(N):
    if arc_num_for_each_node[i] == 0:
        c_set_[i] = c_.pop(0)
        ignore_list[i] = True
    elif arc_num_for_each_node[i] == 1:
        c_set_[i] = c_.pop(0)
        ignore_list[i] = True
poi(c_, arc_, c_set_, ignore_list, 0)

print(max_value)
print(' '.join([str(v) for v in max_c]))

Submission status: Runtime Error

Solution code:
visit_list = []


def topological_sort():
    for s in range(n):
        if color[s] == 0:
            dfs(s)

def dfs(u):
    color[u] = 1
    for v in graph[u]:
        if color[v] == 0:
            dfs(v)
    visit_list.append(u)        
 
 
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)    

topological_sort()
c = [int(i) for i in input().split()]
c.sort()
t_list = [[visit_list[i], c[i]] for i in range(n)]
t_list.sort()
print(sum(c[:-1]))
a_list = [str(t[1]) for t in t_list]
print(" ".join(a_list))

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
    tmp_lst = tree_dic[current_node][:]
    for next_node in tmp_lst:
        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:
import numpy as np
from sys import stdin

N = int(stdin.readline().rstrip())

vs = np.array([list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)])
cs = np.sort(np.array(list(map(int, stdin.readline().rstrip().split()))))[::-1]

max_score = np.sum(cs[1:])

def make_tree(i):
    global vs
    children = vs[np.any(vs == i, axis=1)].flatten()
    children = children[children != i]
    vs =vs[np.all(vs != i, axis=1)]

    return np.array([i, np.array(list(map(make_tree ,children)))])

tree = make_tree(1)
c_pos = np.empty_like(cs)

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
    tmp_lst = tree_dic[current_node][:]
    for next_node in tmp_lst:
#        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 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))

Submission status: Runtime Error

Solution code:
class Queue(object):

    def __init__(self):
        self.queue_list = []

    def enqueue(self, value):
        self.queue_list.append(value)

    def dequeue(self):
        try:
            # 先頭をとりだす
            value = self.queue_list.pop(0)
        except IndexError:
            value = None

        return value
N = int(input())

pair = []
tree = {}

for _ in range(N-1):
    a, b = list(map(int, input().split(" "))) 
    if a in tree.keys():
        tree[a].append(b)
    else:
        tree[a] = [b]
        
    if b in tree.keys():
        tree[b].append(a)
    else:
        tree[b] = [a]
    pair.append([a,b])
    
c = list(map(int, input().split(" ")))
c.sort(reverse=True)
c = c[:N+2]

queue = Queue()
tree_l = {}
for key in tree.keys():
    tree_l[key] = len(tree[key])

ans = {}
max_node = max((v, k) for k, v in tree_l.items())[1]
ans[max_node] = c[0]
used = [max_node]
cnt = 0

candi = {}
for i in tree[max_node]:
    candi[i] = tree_l[i]

for k, v in sorted(candi.items(), key=lambda x: -x[1]):
    queue.enqueue(k)

while True:
    node = queue.dequeue()
    cnt += 1
    ans[node] = c[cnt]
    
    if cnt == N-1:
        break
    
    candi = {}
    for i in tree[node]:
        candi[i] = tree_l[i]
    for k, v in sorted(candi.items(), key=lambda x: -x[1]):
        if k not in used:
            queue.enqueue(k)

            
total = 0
for a, b in pair:
    if ans[a] > ans[b]:
        total += ans[b]
    else:
        total += ans[a]
        
print(total)
for i in range(1, N, 1):
    print(ans[i], end=" ")

print(ans[N])

Submission status: Runtime Error

Solution code:
import numpy as np
from sys import stdin

N = int(stdin.readline().rstrip())

vs = np.array([list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)])
cs = np.sort(np.array(list(map(int, stdin.readline().rstrip().split()))))[::-1]

# if N == 1:
#     print('0')
#     print(cs[0])

max_score = np.sum(cs[1:])

def make_tree(i):
    global vs
    children = vs[np.any(vs == i, axis=1)].flatten()
    children = children[children != i]
    vs =vs[np.all(vs != i, axis=1)]

    return np.array([i, np.array(list(map(make_tree ,children)))])

tree = make_tree(1)

c_pos = np.empty_like(cs)
def show_tree(tree):
    global cs
    c_pos[tree[0]-1] = cs[0]
    cs = np.delete(cs, 0)
    [show_tree(t) for t in tree[1]]

show_tree(tree)

print(max_score)
print(' '.join([str(c) for c in c_pos]))

Submission status: Runtime Error

Solution code:
import numpy as np
from sys import stdin

N = int(stdin.readline().rstrip())

vs = np.array([list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)])
cs = np.sort(np.array(list(map(int, stdin.readline().rstrip().split()))))[::-1]

# if N == 1:
#     print('0')
#     print(cs[0])

max_score = np.sum(cs[1:])

def make_tree(i):
    global vs
    children = vs[np.any(vs == i, axis=1)].flatten()
    children = children[children != i]
    vs =vs[np.all(vs != i, axis=1)]

    return np.array([i, np.array(list(map(make_tree ,children)))])

tree = make_tree(1)

c_pos = np.empty_like(cs)
def show_tree(tree):
    global cs
    c_pos[tree[0]-1] = cs[0]
    cs = np.delete(cs, 0)
    [show_tree(t) for t in tree[1]]

show_tree(tree)

print(max_score)
[print('%d ' % c, end='') for c in c_pos]

Submission status: Runtime Error

Solution code:
# -*- Coding: utf-8 -*-

n = int(input())
A = []
A = [list(map(int,input().split())) for i in range(n-1)]
C = list(map(int,input().split()))

C2 = []
for i in range(n):
    C2.append([C[i],i])

C2.sort()

ans = sum(C)-C2[-1][0]

T = [[] for i in range(n)]
for i in range(len(A)):
    T[A[i][0]-1].append(A[i][1]-1)
    T[A[i][1]-1].append(A[i][0]-1)
#print(T)


E = [[0,i] for i in range(n)]
E[0][0]=1
# co = 0
# while co < n-1:
#     #print(co)
#     t = 0
#     while t < n+1 :
#         if len(T[t]) == 1:
#             E.append(t)
#             if co == n-2 :
#                 E.append(T[t][0])
#             T[T[t][0]].remove(t)
#             T[t] = []
#             co += 1
#         t += 1

def ho(u):
    p = E[u][0]
    for j in range(len(T[u])):
        if E[T[u][j]][0] == 0:
            E[T[u][j]][0] = p+1
            ho(T[u][j])
ho(0)
#print(E)
E.sort(reverse=1)


#print(E)

D = [0 for i in range(n)]
for i in range(n):
    D[E[i][1]] = C2[i][0]

print(ans)
s = ""
for i in range(n):
    s += str(D[i])
    s += " "
    
print(s)

Submission status: Runtime Error

Solution code:
n = int(input())
edgeList0 = [list(map(int, input().split())) for i in range(n-1)]
cList = list(map(int,input().split()))
cList.sort(reverse=True)
print(sum(cList[1:]))
edgeList = []
for _ in range(n):
  edgeList.append([])
for i in edgeList0:
  edgeList[i[0]-1].append(i[1]-1)
  edgeList[i[1]-1].append(i[0]-1)

def edgefunc(j):
  numList.append((j,cList.pop(0)))
  if len(edgeList[j]) != 0:
    for k in edgeList[j]:
      edgeList[k].remove(j)
      edgefunc(k)

numList = []
edgefunc(0)
numList.sort()
answer2 = ""
for l in numList:
  answer2 += str(l[1]) + " "
print(answer2[:-1])

Submission status: Runtime Error

Solution code:
import numpy as np
from sys import stdin

N = int(stdin.readline().rstrip())

vs = np.array([list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)])
cs = np.sort(np.array(list(map(int, stdin.readline().rstrip().split()))))[::-1]

max_score = np.sum(cs[1:])

def make_tree(i):
    global vs
    children = vs[np.any(vs == i, axis=1)].flatten()
    children = children[children != i]
    vs =vs[np.all(vs != i, axis=1)]

    return np.array([i, np.array(list(map(make_tree ,children)))])

tree = make_tree(1)

c_pos = np.empty_like(cs)
def show_tree(tree):
    global cs
    print(tree)
    c_pos[tree[0]-1] = cs[0]
    cs = np.delete(cs, 0)
    [show_tree(t) for t in tree[1]]

show_tree(tree)

print(max_score)
[print('%d ' % c, end='') for c in c_pos]

Submission status: Runtime Error

Solution code:
def intinput(): return map(int,input().split())

def ab(i):
    global c,l,x
    while len(l[i])>0:
        x[l[i][0]]=c.pop(0)
        l[l[i][0]].remove(i)
        ab(l[i][0])
        l[i].pop(0)

    return

n=int(input())
l = [[] for _ in range(n+1)]
for i in range(n-1):
    a,b=intinput()
    l[a].append(b)
    l[b].append(a)
c = list(intinput())
c += [0,0,0,0,0,0,0]
c.sort(reverse=1)
x = [0 for _ in range(n+1)]
x[1]=c.pop(0)
for i in range(1,n+1):
    ab(i)
print(sum(x[2:]))
f = ""
q= len(x[1:])
for i in range(q):
    if i != q-1:
        f += str(x[i+1])+" "
    else:
        f += str(x[i+1])
print(f)

Submission status: Runtime Error

Solution code:



N=int(input())
road_list = [[] for i in range(N)]

for i in range(N-1):
    a,b=list(map(int,input().split()))
    a=a-1
    b=b-1
    road_list[a].append(b)
    road_list[b].append(a)
c = list(map(int,input().split()))
from collections import deque
Q = deque([[0,0]])
ans = []
checked_list = [False for i in range(N)]
checked_list[0]=True
count_list = [10**9 for i in range(N)]
count_list[0] = 0

while len(Q)>0:
    v,count = Q.pop()
    count+=1
    for v1 in road_list[v]:        
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.append([v1,count])
            count_list[v1]=count

c.sort()

count_list = [[i,count_list[i]] for i in range(N)]
count_list = sorted(count_list, key=lambda x:x[1],reverse=True)
d = [[count_list[i][0],c[i]] for i in range(N)]
d = sorted(d, key=lambda x:x[0])
d = [d[i][1] for i in range(N)]
print(sum(c[:-1]))
print(*d)


N,A,B,C = list(map(int,input().split()))

Submission status: Runtime Error

Solution code:
import heapq
from collections import defaultdict

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()


N = n()
M = 0
ds = [None] * N

edges = defaultdict(set)
ranks = [0] * N
for i in range(N-1):
    a, b = nl()
    edges[a-1].add(b-1)
    edges[b-1].add(a-1)
    ranks[a-1] += 1
    ranks[b-1] += 1
cs = sorted(nl())
M = sum(cs[:-1])

h = []
for i in range(N):
    heapq.heappush(h, (ranks[i], i))

for i in range(N):
    rank, node = heapq.heappop(h)
    ds[node] = cs[i]
    for next_node in edges[node]:
        heapq.heappush(h, (ranks[next_node]-1, next_node))
        edges[next_node].remove(node)

print(M)
print(' '.join([str(d) for d in ds]))

Submission status: Runtime Error

Solution code:
def intinput(): return map(int,input().split())

def ab(i):
    global c,l,x
    while len(l[i])>0:
        x[l[i][0]]=c.pop(0)
        l[l[i][0]].remove(i)
        ab(l[i][0])
        try:
            l[i].pop(0)
        except:
            pass
    return

n=int(input())
l = [[] for _ in range(n+1)]
for i in range(n-1):
    a,b=intinput()
    l[a].append(b)
    l[b].append(a)
c = list(intinput())
c.sort(reverse=1)
x = [0 for _ in range(n+1)]
x[1]=c.pop(0)
for i in range(1,n+1):
    ab(i)
print(sum(x[2:]))
f = ""
q= len(x[1:])
for i in range(q):
    if i != q-1:
        f += str(x[i+1])+" "
    else:
        f += str(x[i+1])
print(f)

Submission status: Runtime Error

Solution code:
def intinput(): return map(int,input().split())

def ab(i):
    global c,l,x
    while len(l[i])>0:
        try:
            l[l[i][0]].remove(i)
        except:
            pass
        x[l[i][0]]=c.pop(0)
        ab(l[i][0])
        l[i].pop(0)
        
    return

n=int(input())
l = [[] for _ in range(n+1)]
for i in range(n-1):
    a,b=intinput()
    l[a].append(b)
    l[b].append(a)
c = list(intinput())
c.sort(reverse=1)
x = [0 for _ in range(n+1)]
x[1]=c.pop(0)
for i in range(1,n+1):
    ab(i)
print(sum(x[2:]))
f = ""
q= len(x[1:])
for i in range(q):
    if i != q-1:
        f += str(x[i+1])+" "
    else:
        f += str(x[i+1])
print(f)

Submission status: Runtime Error

Solution code:
visit_list = []
def topological_sort():
    for s in range(n):
        if color[s] == 0:
            dfs(s)

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


n = int(input())
if n > 1:
    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)    

    topological_sort()
    c = [int(i) for i in input().split()]
    c.sort()
    t_list = [[visit_list[i], c[i]] for i in range(n)]
    t_list.sort()
    print(sum(c[:-1]))
    a_list = [str(t[1]) for t in t_list]
    print(" ".join(a_list))
else:
    k = int(input())
    print(k)
    print(k)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit

n = int(input())
edge = [[] for _ in range(n)]
e = []
for i in range(n - 1):
    a, b = map(int, input().split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
    e.append((a - 1, b - 1))
c = list(map(int, input().split()))
c.sort(reverse=True)

def point(x, prev, turn=0):
    if turn > n:
        return
    dp[x] = c[n - dp.count(0)]
    for i in edge[x]:
        if dp[i] != 0:
            continue
        if i == prev:
            continue
        else:
            point(i, x, turn + 1)
    return

for i in range(n):
    if len(edge[i]) > 1:
        continue
    else:
        dp = [0] * n
        point(i, -1)
        break

ans = sum(c) - max(c)

print(ans)
print(" ".join(map(str, dp)))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from collections import deque



## input
N = int(input())
tr = [{-1} for _ in range(N)]
for _ in range(N-1):
  a,b = map(int, input().split())
  tr[a-1].add(b-1)
  tr[b-1].add(a-1)
costs = list(map(int, input().split()))
costs = sorted(costs, reverse=True)+[0]

## solve
root = 0

idx = deque()
def make_tr(rt,p):
  if p > N or p < 0:
    return 0
  idx.append(p)
  for q in tr[p]:
    if q != rt and q > 0:
      make_tr(p,q)

make_tr(-1,root)

ans = [None for _ in range(N)]
j = 0
for i in idx:
  ans[i] = str(costs[j])
  j += 1

## output
print(sum(costs[1:]))
print(" ".join(ans))

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 = []
    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()

Submission status: Runtime Error

Solution code:

visit_list = []
def topological_sort():
    for s in range(n):
        if color[s] == 0:
            dfs(s)

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


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)    

topological_sort()
c = [int(i) for i in input().split()]
c.sort()
t_list = [[visit_list[i], c[i]] for i in range(n)]
t_list.sort()
print(sum(c[:-1]))
a_list = [str(t[1]) for t in t_list]
print(" ".join(a_list))

Submission status: Runtime Error

Solution code:
#

import itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

def main():
    N = int(input())
    d = [0] * N
    multi = [0] * N

    edges = defaultdict(list)
    edges_l = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        d[a-1] += 1
        d[b-1] += 1
        multi[a-1] += 1
        multi[b-1] += 1

        edges_l.append((a-1, b-1))
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)

    for i in range(len(d)):
        d[i] = (d[i], i)
    d.sort(key=lambda v: v[0], reverse=True)

    C = list(map(int, input().split()))
    C.sort(reverse=True)
    # print(d)
    # print(C)
    used = [False] * N
    ans = [0] * N
    count = 0
    que = d[i]
    while que:
        dub, index = que.pop()
        if not used[index]:
            # print('i = {}, Ci = {}'.format(i, C[i]))
            ans[index] = C[count]
            used[index] = True
            count += 1

        # print(edges[i])
        for nei in edges[index]:
            if not used[nei]:
                que.append(d[nei])

    val = 0
    for a, b in edges_l:
        node_val = min(ans[a], ans[b])
        val += node_val

    print(val)
    print(' '.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- Coding: utf-8 -*-

n = int(input())
A = [list(map(int,input().split())) for i in range(n-1)]
C = list(map(int,input().split()))

C2 = []
for i in range(n):
    C2.append([C[i],i])

C2.sort()

ans = sum(C)-C2[-1][0]

T = [[] for i in range(n)]
for i in range(len(A)):
    T[A[i][0]-1].append(A[i][1]-1)
    T[A[i][1]-1].append(A[i][0]-1)
#print(T)


E = [[0,i] for i in range(n)]
E[0][0]=1
# co = 0
# while co < n-1:
#     #print(co)
#     t = 0
#     while t < n+1 :
#         if len(T[t]) == 1:
#             E.append(t)
#             if co == n-2 :
#                 E.append(T[t][0])
#             T[T[t][0]].remove(t)
#             T[t] = []
#             co += 1
#         t += 1

def ho(u):
    p = E[u][0]
    for j in range(len(T[u])):
        if E[T[u][j]][0] == 0:
            E[T[u][j]][0] = p+1
            ho(T[u][j])
ho(0)
#print(E)
E.sort(reverse=1)


#print(E)

D = [0 for i in range(n)]
for i in range(n):
    D[E[i][1]] = C2[i][0]

print(ans)
s = ""
for i in range(n):
    s += str(D[i])
    s += " "

print(s)

Submission status: Runtime Error

Solution code:
N = int(input())
tree = [[] for _ in range(N + 1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
c = [int(s) for s in input().split()]
c.sort(reverse=True)

anst = [0] * (N + 1)
anss = 0


def visit(a, prev):
    global anst, anss
    ans = 0
    for b in tree[a]:
        if b != prev:
            ci = visit(b, a)
            anss += ci
    ci = c.pop()
    anst[a] = ci
    return ci


visit(1, 1)
print(anss)
print(" ".join((str(i) for i in anst[1:])))

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import defaultdict

def rec(start, p):
    if ans[start] != -1:
        return p
    ans[start] = C[p]
    p += 1
    for node in tree[start+1]:
        p = rec(node-1, p)
    return p

N = int(input())
tree = defaultdict(list)
degree = [0 for i in range(N)]
edges = [0 for i in range(N-1)]
for i in range(N-1):
    a, b = map(int, input().split())
    edges[i] = (a, b)
    tree[a].append(b)
    tree[b].append(a)
for k, v in tree.items():
    degree[k-1] = len(v)
# print(degree)
sort_i = np.argsort(degree)[::-1]
# max_di = sort_i[-1]
# print(sort_i)
C = list(map(int, input().split()))
C = sorted(C, reverse=True)
# C = list(sorted(zip(sorted(C), list(sort_i)),key=lambda x: x[1]))
# print(C[sort_i])
ans = 0
visited_e = []
# start = max_di + 1
visited = [False for i in range(N)]
p = 0
ans = [-1 for i in range(N)]
M = 0

rec(sort_i[0], p)

for e in edges:
    M += min(ans[e[0]-1], ans[e[1]-1])
    # print(ans)
print(M)
print(' '.join(list(map(lambda x: str(x), ans))))

Submission status: Runtime Error

Solution code:
N = int(input())
route_list = list()
cross_count_list = [0] * N

for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    cross_count_list[a] += 1
    route_list.append({'a': a, 'b': b})

c_list = sorted(list(map(int, input().split())), reverse=True)

node_count_list = sorted([{'node': i, 'cross_count': cross_count_list[i]}
                         for i in cross_count_list], key=lambda x: x['cross_count'], reverse=True)
node_number_list = [0] * N
for i in range(N):
    node_number_list[i] = c_list[i]

answer = 0
for route in route_list:
    answer += min(node_number_list[route['a'] - 1], node_number_list[route['b'] - 1])

print(answer)
print(' '.join(list(map(str, node_number_list))))

Submission status: Runtime Error

Solution code:
# -*- Coding: utf-8 -*-

n = int(input())
A = [list(map(int,input().split())) for i in range(n-1)]
C = list(map(int,input().split()))

C2 = []
for i in range(n):
    C2.append([C[i],i])

C2.sort()

ans = sum(C)-C2[-1][0]

T = [[] for i in range(n)]
for i in range(len(A)):
    T[A[i][0]-1].append(A[i][1]-1)
    T[A[i][1]-1].append(A[i][0]-1)
#print(T)


E = [[0,i] for i in range(n)]
E[1][0]=1
# co = 0
# while co < n-1:
#     #print(co)
#     t = 0
#     while t < n+1 :
#         if len(T[t]) == 1:
#             E.append(t)
#             if co == n-2 :
#                 E.append(T[t][0])
#             T[T[t][0]].remove(t)
#             T[t] = []
#             co += 1
#         t += 1

def ho(u):
    p = E[u][0]
    for j in range(len(T[u])):
        if E[T[u][j]][0] == 0:
            E[T[u][j]][0] = p+1
            ho(T[u][j])
ho(1)
#print(E)
E.sort(reverse=1)


#print(E)

D = [0 for i in range(n)]
for i in range(n):
    D[E[i][1]] = C2[i][0]

print(ans)
s = ""
for i in range(n):
    s += str(D[i])
    s += " "

print(s)