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: Wrong Answer

Solution code:
def d_maximum_sum_of_minimum(N, Nodes, C):
    # 根から始め、巡回した葉にCの大きなものから順に書き込んで行く。
    import sys
    sys.setrecursionlimit(10**6)

    int_list = list(sorted(C))
    graph = [[] for _ in range(N)]
    for u, v in Nodes:  # 0-basedとする
        graph[u - 1].append(v - 1)
        graph[v - 1].append(u - 1)

    def traverse_tree(parent, current, ret=[0] * N):
        """各頂点にCの値が大きなもの順に書き込んでいく"""
        def dfs(p, c):
            ret[c] = int_list.pop()
            for next_edge in graph[c]:
                if next_edge != p:  # 木を「逆戻り」しない頂点だけ調べる
                    dfs(c, next_edge)
        dfs(parent, current)
        return ret
    tmp = traverse_tree(-1, 0)[1:]
    return str(sum(tmp)) + '\n' + ' '.join(map(str, tmp))

N = int(input())
Nodes = [[int(i) for i in input().split()] for j in range(N - 1)]
C = [int(i) for i in input().split()]
print(d_maximum_sum_of_minimum(N, Nodes, C))

Submission status: Wrong Answer

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

c = sorted(map(int, input().split()))
M = sum(c[:-1])
use = [0 for _ in range(N)]

for e in edge:
    a, b = e
    if use[a] == 0:
        use[a] = c.pop()
    if use[b] == 0:
        use[b] = c.pop()

print(M)
print(*use)

Submission status: Wrong Answer

Solution code:
n = int(input())

d = {}
br = []
sum_ = 0
res = ""

for i in range(n-1):
    a,b = map(int, input().split())
    br += [(a,b),]

    try:
        d[a] += 1
    except:
        d[a] = 1

    try:
        d[b] += 1
    except:
        d[b] = 1

d = sorted(d.items(), key=lambda x:x[1])

c = sorted(list(map(int, input().split())))

for ind,i in enumerate(c):
    d[ind] = (d[ind][0], i)

d = sorted(d)

# print(br)
# print(d)

# for i,j in br:
#     # print(i,j)
#     if d[i-1][1] < d[j-1][1]:
#         sum_ += d[i-1][1]
#     else:
#         sum_ += d[j-1][1]

sum_ = sum(c[:-1])

for i,j in d:
    res += str(j) + " "

print(sum)
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())

e = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
c = list(map(int,input().split()))
c.sort()
d = [0]*N
d[0] = str(c.pop())

for _ in range(N-1):
    for i in range(N-1):
        a,b = e[i]
        if d[a]==0 and d[b]!=0:
            d[a] = str(c.pop())
        elif d[a]!=0 and d[b]==0:
            d[b] = str(c.pop())

print(' '.join(d))

Submission status: Wrong Answer

Solution code:
import numpy as np 
N = int(input())
# N = 1000
# G = np.zeros((N,N),dtype = np.bool)

linked = [[] for i in range(N)]
pairs = []

for i in range(N-1):
    a,b = map(int,input().split())
    # a,b = 1,2
    pairs.append((a,b))
    linked[a-1].append(b-1)
    linked[b-1].append(a-1)


Cs = list(sorted(map(int,input().split())))
# Cs = [1 for i in range(N)]
# 

links = np.array([0 for i in range(N)])

for i in range(N):
    links[i] = len(linked[i])

minag = np.argmin(links)
nodeval = np.array([0 for i in range(N)])

stack = [minag]

visited = [False for i in range(N)]
# print(Cs)
while(len(stack)>0):
    minag = stack.pop()
    visited[minag] = True
    nodeval[minag] = Cs.pop(0)
    for l in linked[minag]:
        if not visited[l]:
            stack.append(l)
    # print(nodeval)

sumval=0
for p in pairs:
    sumval += min(nodeval[p[0]-1], nodeval[p[1]-1] )

print(sumval)
for i,l in enumerate(nodeval):
    print(l,end=" " if i!=N-1 else "\n")

Submission status: Wrong Answer

Solution code:
n = int(input())

d = {}
br = []
sum_ = 0
res = ""

for i in range(n-1):
    a,b = map(int, input().split())
    br += [(a,b),]

    try:
        d[a] += 1
    except:
        d[a] = 1

    try:
        d[b] += 1
    except:
        d[b] = 1

d = sorted(d.items(), key=lambda x:x[1])

c = sorted(list(map(int, input().split())))

for ind,i in enumerate(c):
    d[ind] = (d[ind][0], i)

d = sorted(d)

# print(br)
# print(d)

# for i,j in br:
#     # print(i,j)
#     if d[i-1][1] < d[j-1][1]:
#         sum += d[i-1][1]
#     else:
#         sum += d[j-1][1]

sum_ = sum(c) - c[0]

for i,j in d:
    res += str(j) + " "

print(sum)
print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np 
N = int(input())
# N = 1000
# G = np.zeros((N,N),dtype = np.bool)

linked = [[] for i in range(N)]

for i in range(N-1):
    a,b = map(int,input().split())
    # a,b = 1,2
    linked[a-1].append(b-1)
    linked[b-1].append(a-1)


Cs = list(sorted(map(int,input().split())))
# Cs = [1 for i in range(N)]
# 

links = np.array([0 for i in range(N)])

for i in range(N):
    links[i] = len(linked[i])

minag = np.argmin(links)
nodeval = np.array([0 for i in range(N)])

stack = [minag]

visited = [False for i in range(N)]
# print(Cs)
while(len(stack)>0):
    minag = stack.pop()
    visited[minag] = True
    nodeval[minag] = Cs.pop(0)
    for l in linked[minag]:
        if not visited[l]:
            stack.append(l)
    # print(nodeval)

for i,l in enumerate(nodeval):
    print(l,end=" " if i!=N-1 else "\n")

Submission status: Wrong Answer

Solution code:
from collections import deque
# import heapq


N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    # グラフに頂点を追加
    G[u-1].append((v-1))
    G[v-1].append((u-1))
cs = sorted(list(map(int,input().split())),reverse=True)
print(cs)
gs = [len(g) for g in G]
K = gs.index(min(gs))

ds = [-1]*N
used = [False] * N
ans = 0

# BFS
q = deque([K])
ds[K] = cs[0]
i = 1
while len(q) > 0:
    a = q.popleft()
    Vs = G[a]
    for u in Vs:
        if ds[u] == -1:
            q.append(u)
            ds[u] = cs[i]
            used[u] = True
            i += 1
ansd = ""
for d in ds:
    ansd += str(d)+" "
print(sum(cs)-max(cs))
print(ansd)

Submission status: Wrong Answer

Solution code:
from scipy.sparse import*
n,*t=map(int,open(0).read().split())
c=sorted(t[-n:])
f=[0]*n
for i in csgraph.depth_first_order(csr_matrix(([1]*~-n,(t[:-n:2],t[1:-n:2])),[n+1]*2),1)[0]:n-=1;f[i-1]=c[n]
print(sum(c[:-1]),*f)

Submission status: Wrong Answer

Solution code:
from collections import deque
# import heapq


N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    # グラフに頂点を追加
    G[u-1].append((v-1))
    G[v-1].append((u-1))
cs = sorted(list(map(int,input().split())),reverse=True)

gs = [len(g) for g in G]
K = gs.index(min(gs))

ds = [-1]*N
used = [False] * N
ans = 0

# BFS
q = deque([K])
print(K)
ds[K] = cs[0]
i = 1
while len(q) > 0:
    a = q.popleft()
    Vs = G[a]
    for u in Vs:
        if ds[u] == -1:
            q.append(u)
            ds[u] = cs[i]
            used[u] = True
            i += 1
ansd = ""
for d in ds:
    ansd += str(d)+" "
print(sum(cs)-max(cs))
print(ansd)

Submission status: Wrong Answer

Solution code:
from collections import deque
import heapq


N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    # グラフに頂点を追加
    G[u-1].append((v-1))
    G[v-1].append((u-1))
cs = sorted(list(map(int,input().split())))

gs = [len(g) for g in G]
K = gs.index(min(gs))

ds = [-1]*N
used = [False] * N
ans = 0

# BFS
q = deque([K])
ds[K] = cs[0]
i = 1
while len(q) > 0:
    a = q.popleft()
    Vs = G[a]
    for u in Vs:
        if ds[u] == -1:
            q.append(u)
            ds[u] = cs[i]
            used[u] = True
            i += 1
ansd = ""
for d in ds:
    ansd += str(d)+" "
print(sum(cs)-max(cs))
print(ansd)

Submission status: Wrong Answer

Solution code:
class Node:
  def __init__(self,data):
    self.data = data
    self.childs = []
    self.depth = 0
    self.number = 0

N = int(input())
Nodes = []
for i in range(N+1):
  Nodes.append(Node(i))

for i in range(N-1):
  tmp_A,tmp_B = (int(i) for i in input().split())
  A = min(tmp_A,tmp_B)
  B = min(tmp_A,tmp_B)
  Nodes[A].childs.append(B)

c = [int(i) for i in input().split()]

for Node in Nodes:
  for child in Node.childs:
    Nodes[child].depth = Node.depth + 1

Nodes.pop(0)
Nodes = sorted(Nodes, key=lambda x: x.depth, reverse = True)

c.sort()
for Node in Nodes:
  Node.number = c[0]
  c.pop(0)

Nodes = sorted(Nodes, key=lambda x: x.data)

ans = 0
ans_list = []

for Node in Nodes:
  ans_list.append(Node.number)
  for child in Node.childs:
    ans += min(Nodes[child-1].number,Node.number)

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [0]*(n-1)
b = [0]*(n-1)
for i in range(n-1):
    a[i], b[i] = list(map(int, input().split()))
c = list(map(int, input().split()))
c.sort()
x = a
x.extend(b)
y = []
for i in range(n):
    y.append([i,x.count(i+1)])

y.sort(key=lambda x:x[1])

s = 0
z = [0]*n
for i in range(n):
    z[y[i][0]] = c[i]
    
for i in range(n-1):
    s = s+min(z[a[i]-1],z[b[i]-1])

print(s)
for i in range(n):
  print(z[i], end=" ")

Submission status: Wrong Answer

Solution code:
class Node:
  def __init__(self,data):
    self.data = data
    self.childs = []
    self.depth = 0
    self.number = 0

N = int(input())
Nodes = []
for i in range(N+1):
  Nodes.append(Node(i))

for i in range(N-1):
  A,B = (int(i) for i in input().split())
  Nodes[A].childs.append(B)

c = [int(i) for i in input().split()]

for Node in Nodes:
  for child in Node.childs:
    Nodes[child].depth = Node.depth + 1

Nodes.pop(0)
Nodes = sorted(Nodes, key=lambda x: x.depth, reverse = True)

c.sort()
for Node in Nodes:
  Node.number = c[0]
  c.pop(0)

Nodes = sorted(Nodes, key=lambda x: x.data)

ans = 0
ans_list = []

for Node in Nodes:
  ans_list.append(Node.number)
  for child in Node.childs:
    ans += min(Nodes[child-1].number,Node.number)

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

Submission status: Wrong Answer

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):
    try:
        tmp_lst = tree_dic[current_node][:]
    except:
        pass

    for next_node in tmp_lst:
        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]#   探索し終えたノードの削除
        else:   #   次のノードにつながっている辺があるとき
            try: 
                ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)

            except:
                pass

    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: Wrong Answer

Solution code:
def getN():
    return int(input())

def getMN():
    return list(map(int, input().split()))

def getlist():
    return list(map(int, input().split()))
from queue import Queue
import copy
n =getN()

nodes = [[] for i in range(n)]

for i in range(n-1):
    a, b = getlist()
    nodes[a-1].append(b-1)
    nodes[b-1].append(a-1)


nodes = [(node, i) for i, node in enumerate(nodes)]
serve = copy.deepcopy(nodes)
scores = sorted(getlist(), reverse=True)
nodes = sorted(nodes, key=lambda x: -len(x[0]))
start = nodes[0][1]
# print(nodes, start)

def bfs(nodes, start, n):
    state = [0] * n
    state[start] = 1
    prior = [0] * n
    q = Queue()
    pridx = 0
    q.put(start)
    while(not q.empty()):
        next = q.get()
        for nx in serve[next][0]:
            if state[nx] == 0:
                q.put(nx)
                state[nx] = 1
                pridx += 1
                prior[nx] = pridx

    return prior

prior = bfs(nodes, start, n)
#print(prior)

print(sum(scores[1:]))
prlist = [0 for i in range(n)]
for i, j in zip(scores, prior):
    prlist[j] = i

print(" ".join(map(str, prlist)))


"""
7
1 2
3 2
2 4
4 5
5 6
5 7
1 1 1 4 5 6 7
"""

Submission status: Wrong Answer

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

    for next_node in tmp_lst:
        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]#   探索し終えたノードの削除
        else:   #   次のノードにつながっている辺があるとき
            try: 
                ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)

            except:
                pass

    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: Wrong Answer

Solution code:
class Node:
  def __init__(self,data):
    self.data = data
    self.childs = []
    self.depth = 0
    self.number = 0

N = int(input())
Nodes = []
for i in range(N+1):
  Nodes.append(Node(i))

for i in range(N-1):
  A,B = (int(i) for i in input().split())
  Nodes[A].childs.append(B)

c = [int(i) for i in input().split()]


for Node in Nodes:
  for child in Node.childs:
    Nodes[child].depth = Node.depth + 1

Nodes.pop(0)
Nodes = sorted(Nodes, key=lambda x: x.depth)

c.sort(reverse=True)
for Node in Nodes:
  Node.number = c[0]
  c.pop(0)

Nodes = sorted(Nodes, key=lambda x: x.data)

ans = 0
ans_list = []

for Node in Nodes:
  ans_list.append(Node.number)
  for child in Node.childs:
    ans += min(Nodes[child-1].number,Node.number)

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

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

class Node:
    def __init__(self, parent, child,value):
        self.parent = parent
        self.child = child
        self.value = value


N = int(input())
nodes = []
root = 0
for i in range(N):
    nodes.append(Node(-1, [], 0))
for i in range(N-1):
    a, b = map(int,input().split())
    if nodes[a-1].parent != -1: #頂点aは既に親を持つ->頂点bを頂点aの子にする
        nodes[a-1].child.append(b-1)
        nodes[b-1].parent = a-1
    else: #頂点aは根->頂点bを頂点aの親にする
        nodes[a-1].parent = b-1
        nodes[b-1].child.append(a-1)
op = 0
while nodes[op].parent != -1:
    op = nodes[op].parent
root = op

C = list(map(int, readline().split()))
C.sort()
score = sum(C)
score -= C[N-1]
print(str(score))

queue = [root]
while queue:
    op = queue.pop(0)
    nodes[op].value = C[-1]
    C.pop(-1)
    numchild = len(nodes[op].child)
    for i in range(numchild):
        queue.append(nodes[op].child[i])
for i in range(N):
    if i != N-1:
        write(str(nodes[i].value) + " ")
    else:
        write(str(nodes[i].value) + "\n")

Submission status: Wrong Answer

Solution code:
import sys
import itertools
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

n = int(input())
t = [[i] for i in range(n)]
w = []
for i in range(n-1):
    x, y = lmi()
    w.append([x-1,y-1])
    t[x-1].append(y-1)
    t[y-1].append(x-1)

c = lmi()

#print(t)
#print(c)

c.sort()

l = [0] * n

t.sort(key = lambda x: len(x))

for i in range(n):
    #print(t[i])
    l[t[i][0]] = c[i]

s = 0
for i, j in w:
    s += min(l[i], l[j])


print(s)
print(' '.join(map(str,l)))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [0]*(n-1)
b = [0]*(n-1)
for i in range(n-1):
    a[i], b[i] = list(map(int, input().split()))
c = list(map(int, input().split()))
c.sort()
x = a
x.extend(b)
y = []
for i in range(n):
    y.append([i,x.count(i+1)])

y.sort(key=lambda x:x[1], reverse=True)

s = 0
z = [0]*n
for i in range(n):
    z[y[i][0]] = c[i]
    
for i in range(n-1):
    s = s+min(c[a[i]-1],c[b[i]-1])

print(s)
for i in range(n):
  print(c[i], end=" ")

Submission status: Wrong Answer

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

    for next_node in tmp_lst:
        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]#   探索し終えたノードの削除

        try:
            if len(tree_dic[next_node]) == 0:
                del tree_dic[next_node]#   探索し終えたノードの削除

            else:   #   次のノードにつながっている辺があるとき
                ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)
 
 
        except:
            return ans

    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: Wrong Answer

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

    for next_node in tmp_lst:
        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)

        try:
            if len(tree_dic[current_node]) == 0:
                del tree_dic[current_node]#   探索し終えたノードの削除
            if len(tree_dic[next_node]) == 0:
                del tree_dic[next_node]#   探索し終えたノードの削除

            else:   #   次のノードにつながっている辺があるとき
                ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)
 
 
        except:
            return ans

    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: Wrong Answer

Solution code:
import sys
import itertools
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

n = int(input())
t = [[i] for i in range(n)]
for i in range(n-1):
    x, y = lmi()
    t[x-1].append(y-1)
    t[y-1].append(x-1)

c = lmi()
c.sort()

l = [0] * n

t.sort(key = lambda x: len(x))

for i in range(n):
    l[t[i][0]] = c[i]


print(sum(c) - c[-1])
print(' '.join(map(str,l)))

Submission status: Wrong Answer

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):
    tmp_lst = tree_dic[current_node][:]
    try:
        for next_node in tmp_lst:
            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]#   探索し終えたノードの削除
                
            else:   #   次のノードにつながっている辺があるとき
                ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)

        return ans

    except:
        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: Wrong Answer

Solution code:
import numpy as np

class Tree():
    """
    木の端点
    """
    def __init__(self, id):
        self.id = id
        self.sub = [] # 繋がっている端点
        self.val = 0  # 割り当てられた値

N = int(input())
T = [Tree(i) for i in range(N)]
pair = []
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    pair.append((a, b))
    T[a].sub.append(T[b])
    T[b].sub.append(T[a])

*C, = map(int, input().split())
C.sort

T2 = sorted(T, key=lambda x: len(x.sub))

while len(C) > 0:
    cur = T2.pop()
    cur.val = C.pop()
    for sub in cur.sub:
        for i, t in enumerate(T2):
            if t == sub:
                T2.pop(i)
        if sub.val == 0:
            sub.val = C.pop()
ans = 0
for i in range(N-1):
    a, b = pair[i]
    ans += min(T[a].val, T[b].val)
print(ans)
a = [t.val for t in T]
print(*a)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import numpy as np
import collections

N = int(stdin.readline())

ab = []
l = []
count = dict()

for i in range(N-1):
    a, b =[int(x) for x in input().split()]
    l.append(a)
    l.append(b)
    ab.append([a,b])
    
c = [int(x) for x in input().split()]
c.reverse()
    
# [PythonのCounterでリストの各要素の出現個数をカウント \| note\.nkmk\.me](https://note.nkmk.me/python-collections-counter/)
cnt = collections.Counter(l)
common = cnt.most_common()

for j in range(N):
    count[common[j][0]] = c[j]

sum = 0
for j in range(N-1):
  tmp = min(count[ab[j][0]], count[ab[j][1]])
  sum = sum + tmp
print(sum)

print(' '.join([str(c) for c in list(count.values())]))

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
g = [[] for i in range(n)]

for i in range(n-1):
  a,b = na()
  g[a-1].append(b-1)
  g[b-1].append(a-1)

c = na()
c = sorted(c)

print(sum(c)-c[0])

ans = [0]*n
st = [0]

while st:
  d = st.pop()
  ans[d] = c.pop()
  for v in g[d]:
    if ans[v] == 0:
      st.append(v)

print(' '.join([str(s) for s in ans]))

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

class Node:
    def __init__(self, parent, child,value):
        self.parent = parent
        self.child = child
        self.value = value


N = int(input())
nodes = []
root = 0
for i in range(N):
    nodes.append(Node(-1, [], 0))
for i in range(N-1):
    a, b = map(int,input().split())
    if nodes[a-1].parent != -1:
        nodes[a-1].child.append(b-1)
        nodes[b-1].parent = a-1
    else:
        nodes[a-1].parent = b-1
        nodes[b-1].child.append(a-1)
        root = b-1
C = list(map(int, readline().split()))
C.sort()
score = sum(C)
score -= C[N-1]
print(str(score))

queue = [root]
while queue:
    op = queue.pop(0)
    nodes[op].value = C[-1]
    C.pop(-1)
    numchild = len(nodes[op].child)
    for i in range(numchild):
        queue.append(nodes[op].child[i])
for i in range(N):
    if i != N-1:
        write(str(nodes[i].value) + " ")
    else:
        write(str(nodes[i].value) + "\n")

Submission status: Wrong Answer

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):
    tmp_lst = tree_dic[current_node][:]
    try:
        for next_node in tmp_lst:
            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]#   探索し終えたノードの削除
                
            else:   #   次のノードにつながっている辺があるとき
                ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)

    except:


        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: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

class Node:
    def __init__(self, parent, child,value):
        self.parent = parent
        self.child = child
        self.value = value


N = int(input())
nodes = []
root = 0
for i in range(N):
    nodes.append(Node(-1, [], 0))
for i in range(N-1):
    a, b = map(int,input().split())
    if nodes[a-1].parent != -1:
        nodes[a-1].child.append(b-1)
        nodes[b-1].parent = a-1
    else:
        nodes[a-1].parent = b-1
        nodes[b-1].child.append(a-1)
        root = b-1
C = list(map(int, readline().split()))
C.sort()
score = sum(C)
score -= C[N-1]
print(str(score))

queue = [root]
while queue:
    op = queue.pop(0)
    nodes[op].value = C[-1]
    C.pop(-1)
    numchild = len(nodes[op].child)
    for i in range(numchild):
        queue.append(nodes[op].child[i])
for i in range(N):
    if i != N-1:
        write(str(nodes[i].value) + " ")
    else:
        write(str(nodes[i].value) + "\n")
print(nodes[0].child)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
g = [[] for i in range(n)]

for i in range(n-1):
  a,b = na()
  g[a-1].append(b-1)
  g[b-1].append(a-1)

c = na()
c = sorted(c)[::-1]

print(sum(c)-c[0])

ans = [0]*n
st = [0]

while st:
  d = st.pop()
  ans[d] = c.pop()
  for v in g[d]:
    if ans[v] == 0:
      st.append(v)

print(' '.join([str(s) for s in ans]))

Submission status: Wrong Answer

Solution code:
n = int(input())
adj = [[i,0] for i in range(n+1) ]
adj_path = []
for _ in range(n-1):
    a,b = map(int,input().split())
    adj_path.append([a,b])
    adj[a][1] += 1
    adj[b][1] += 1
c_list = sorted(list(map(int,input().split())))
out = [0 for i in range(n+1)]
if len(adj_path) == 0:
    print(0)
    print(" ")
else:
    for i,[name,rank] in enumerate(sorted(adj,key=lambda x:x[1])):
        out[name] = c_list[i-1]
    score = 0
    for a,b in adj_path:
        score += min(out[a],out[b])
    print(score)
    print(" ".join(str(x) for x in out[1:]))

Submission status: Wrong Answer

Solution code:
#一部のケースでACしそうなのでやってみる


n = int(input())
a = []
b = []
for i in range(n-1):
        data = list(map(int,input().split()))
        a.append(data[0])
        b.append(data[1])
c = list(map(int,input().split()))
c.sort(reverse=True)
data = []
for i in range(n):#[頂点の登場回数,頂点番号]の形にする
        data.append([a.count(i)+b.count(i),i])
data.sort()#出てくる回数が少ない順に
print(data)
for i in range(n):#[頂点番号,書き込むべき整数]の形にする
        del data[i][0]
        data[i].append(c[i])
data.sort()#頂点番号順に
for i in range(n):#[書き込むべき整数]
        del data[i][0]
print(data)
for i in range(n):
        data.append(data[i][0])
del data[0:n+1]
print(sum(data))
print(" ".join(map(str,data)))

Submission status: Wrong Answer

Solution code:
n = int(input())
deg = [0 for _ in range(n)]
edges = []
for _ in range(n-1):
	a, b = map(int, input().split())
	deg[a-1] += 1
	deg[b-1] += 1
	edges.append([a-1, b-1])
c = sorted(list(map(int, input().split())))
degg = [[deg[i], i] for i in range(n)]
degg.sort(key=lambda x: x[0])
num = [0 for _ in range(n)]
for i in range(n):
	num[degg[i][1]] = c[i]

ans = 0
for a, b in edges:
	ans += min(num[a], num[b])

print(ans)
print(*num)