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:
from collections import deque

N = int(input())

neighbors = [[] for _ in range(N)]

for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    neighbors[a].append(b)
    neighbors[b].append(a)
c = list(map(int, input().split()))
sorted_c = sorted(c)
max_c = sorted_c[-1]
max_c_pos = c.index(max_c)

closed = [0 for _ in range(N)]
use = [0 for _ in range(N)]
q = deque()
q.append(0)
use[0] = sorted_c.pop()
M = 0


while len(q) > 0:
    parent = q.pop()
    closed[parent] = use[parent]
    for neighbor in neighbors[parent]:
        if closed[neighbor] == 0:
            c2 = use[neighbor] = sorted_c.pop()
            c1 = closed[parent]
            w = c1 if c1 < c2 else c2
            M += w
            q.append(neighbor)

print(M)
print(*c)

Submission status: Wrong Answer

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)
 
# 木の端を求める
def findLeaf(edge, start=1):
    visited = [False for _ in range(len(edge))]
    next_v = edge[start]
    visited[start] = True
    count = 0
    
    while len(next_v) > 0:
        new_v = []
        for it in next_v:
    #         print(it)
            leaf = it
            for v in edge[it]:
                if not visited[v]:
                    new_v.append(v)
            visited[it] = True
        next_v = new_v
        count += 1
 
    return leaf, count
 
 
# 木の直径を求める
def findD(edge):
    leaf, _ = findLeaf(edge, 1)
    leaf, count = findLeaf(edge, leaf)
    return count
 
# 木の中心を求める
def findCenter(edge):
    leaf, _ = findLeaf(edge, 1)
    leaf, d = findLeaf(edge, leaf)
    r = d//2
 
    visited = [False for _ in range(len(edge))]
    start = leaf
    next_v = edge[start]
    # print(next_v, leaf)
    visited[start] = True
    count = 0
 
    while not r == count+1:
        new_v = []
        for it in next_v:
    #         print(it)
            leaf = it
            for v in edge[it]:
                if not visited[v]:
                    new_v.append(v)
            visited[it] = True
        next_v = new_v
        count += 1
        
    center = []
    for it in next_v:
        if len(edge[it]) > 1:
            center.append(it)
    return center
 
 
def calcCost(D, v_val):
    total = 0
    
    n = int(D[0])
    for i in range(1, n):
        a, b = map(int, D[i].split())
        total += min(v_val[a], v_val[b])
        
    return total
 
 
max_val = 0
max_v = 0
l, _ = findLeaf(edge)
for center in [l]:
    order = []
    start = center
    visited = [False for _ in range(len(edge))]
    next_v = edge[start]
    visited[start] = True
    order.append(center)
 
    # Get order from center
    while len(next_v) > 0:
        new_v = []
        for it in next_v:
    #         print(it)
            leaf = it
            for v in edge[it]:
                if not visited[v]:
                    new_v.append(v)
            visited[it] = True
            order.append(it)
        next_v = new_v
        
    # calculate cost
    v_val = [0]
    for i in order:
        v_val.append(c[i-1])
 
    val = calcCost(D, v_val)
    if val > max_val:
        max_val = val
        max_v = v_val
 
        
print(max_val)
print(' '.join(map(str, max_v[1:])))

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
 
#A
def A():
    n = II()
    print((n-2)*180)
    return
 
#B
def B():
    b = S()
    kati = b.count("o")
    kati += 15 - len(b)
    if kati >= 8:
        print("YES")
    else:
        print("NO")
    return
 
#C
def C():
    return
 
#D
def D():
    n = II()
    ab = LIR_(n-1)
    C = LI()
    C.sort(reverse=True)
    c = deque(C)
    edg = [[] for i in range(n)]
    for a, b in ab:
        edg[a].append(b)
        edg[b].append(a)
    for num,e in enumerate(edg):
        if len(e) == 1:
            start = num
            break
    q = deque()
    ans = [0 for i in range(n)]
    q.append(start)
    ans[start] = c.pop()
#    print(start)
    while q:
        p = q.pop()
        for e in edg[p]:
            if not ans[e]:
                ans[e] = c.pop()
                q.append(e)
    anssum = 0
    for a, b in ab:
        anssum += min(ans[a], ans[b])
    print(anssum)
    ans = list(map(str, ans))
    print(" ".join(ans))
 
 
    return
 
#E
def E():
    return
 
#F
def F():
    return
 
#G
def G():
    return
 
#H
def H():
    return
 
#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
N=int(input())
listA=[]
listB=[]
for i in range(N-1):
  a,b=map(int,input().split())
  listA+=[a]
  listB+=[b]
list1=list(map(int,input().split()))
list2=sorted(list1)
print(sum(list2)-list2[-1])
print(*list2)

Submission status: Wrong Answer

Solution code:
from sys import stdin
n = int(stdin.readline().rstrip())
l = [0]*n;
hen = []
for i in range(n-1):
  a,b = [int(x) for x in stdin.readline().rstrip().split()]
  hen.append((a,b))
  l[a-1] += 1;
  l[b-1] += 1;
c = list(map(int, input().split()))

c.sort()
ans = [0]*n

for i in range(n):
   for j in range(n):
      if (len(c)==0):
          break
      if l[j] == i:
         ans[j] = c.pop(0); 
    
sum = 0

for i in range(n-1):
    a, b = hen[i]
    if ans[a-1] < ans[b-1]:
        sum += ans[a-1]
    else:
        sum += ans[b-1]

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
R = []
def dfs(v, p):
    for next in link[v]:
        if next == p:
            continue
        res[next] = min(c[v], c[next])
        if c[v] < c[next]:
            R.append(c[v])
        else:
            R.append(c[next])
        dfs(next, v)

N = int(input())
res = [0] * N
link = [[] * N for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    link[a-1].append(b-1)
    link[b-1].append(a-1)
c = list(map(int, input().split()))

dfs(0, -1)
R.append(max(c))
print(sum(res))

print(*R)

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())
ab_li = []
for i in range(N-1):
    ab_li.append([int(_) for _ in input().split()])
c = [int(_) for _ in input().split()]

seq_li = [i for i in range(N)]
seq = list(itertools.permutations(seq_li))
seq = [list(_) for _ in seq]

max_count = 0
for i, c_li in enumerate(seq):
  count = 0
  tmp_li = [c[i_] for i_ in c_li]
  for a, b in ab_li:
    count += min(tmp_li[a-1], tmp_li[b-1])
  if max_count < count:
    max_count = count
    max_index = i
print(max_count)
submit_c_index = seq[max_index]
submit_c = [c[i]for i in submit_c_index]
print(submit_c)

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 = []
heapq.heapify(gs)
# Gを小さい順に並べ替える
for i,g in enumerate(G):
    n = len(g)
    heapq.heappush(gs,(n,i))

ds = [0]*N
for i in range(N):
    n, j = heapq.heappop(gs)
    ds[j] = cs[i]

used = [False] * N
used[0] = True 
ans = 0

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

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from heapq import heappush, heappop
from collections import deque
from collections import defaultdict
N = int(input())
l = []
p = [0]*N
lp = [0]*(N)
p = [0]*N
d =defaultdict(list)
dd =defaultdict(int)
for i in range(N-1):
    ta ,tb = map(int,input().split())
    l.append([ta-1,tb-1])
    dd[ta-1]+=1
    dd[tb-1]+=1    
li = list(map(int,input().split()))

for i in range(N):
    dd[i] +=1

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

    
li.sort()
for m,(i , j) in enumerate(sd):
    lp[i] = li[m]
for i,j in l:
    d[i].append([j,lp[j]])
    d[j].append([i,lp[i]])
q = deque()
q.append(0)
ll = []
while q:
    if len(q) == 0:break
    t = q.popleft()
    c = lp[t]
    p[t] = 1
    for i ,j in d[t]:

        if p[i] == 0:
            ll.append(min(c,j))
            q.appendleft(i)
print(sum(li)-li[-1])
print(*lp)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from heapq import heappush, heappop
from collections import deque
from collections import defaultdict
N = int(input())
l = []
p = [0]*N
lp = [0]*(N)
p = [0]*N
d =defaultdict(list)
dd =defaultdict(int)
for i in range(N-1):
    ta ,tb = map(int,input().split())
    l.append([ta-1,tb-1])
    dd[ta-1]+=1
    dd[tb-1]+=1    
li = list(map(int,input().split()))

for i in range(N):
    dd[i] +=1

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

    
li.sort()
for m,(i , j) in enumerate(sd):
    lp[i] = li[m]
for i,j in l:
    d[i].append([j,lp[j]])
    d[j].append([i,lp[i]])
q = deque()
q.append(0)
ll = []
while q:
    if len(q) == 0:break
    t = q.popleft()
    c = lp[t]
    p[t] = 1
    for i ,j in d[t]:

        if p[i] == 0:
            ll.append(min(c,j))
            q.appendleft(i)
print(sum(li)-li[0])
print(*lp)

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())
ab = [[int(i) for i in input().split()] for _ in range(N-1)]
c = [int(i) for i in input().split()]

c.sort(reverse=True)

edge = [0] * N

for a, b in ab :
    edge[a-1] += 1
    edge[b-1] += 1

heap = []

for i in range(N) :
    heapq.heappush(heap, (-edge[i], i))

ret = [0] * N

while heap :
    _, k = heapq.heappop(heap)
    ret[k] = str(c.pop())

print(' '.join(ret))

Submission status: Wrong Answer

Solution code:
def topological_sort1():

    for u in range(n):
        if (indeg[u] == 0) & (color[u] == 0):
            bfs(u)
from queue import Queue
def bfs(s):
    q = Queue()
    q.put(s)
    color[s] = 1
    while q.qsize() > 0:
        u = q.get()
        visit_list.append(u)
        
        for v in graph[u]:
            if (indeg[v] == 0) & (color[v] == 0):
                color[v] = 1
                q.put(v)
                
visit_list = []
 
n = int(input())
color = [0] * n
indeg = [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_sort1()
c = [int(i) for i in input().split()]
c.sort()
t_list = [[visit_list[i], str(c[i])] for i in range(n)]
t_list.sort()
print(sum(c) - c[-1])
print(" ".join(list(map(lambda x: x[1], t_list))))

Submission status: Wrong Answer

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

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


N = int(input())
nodes = []
root = 0
for i in range(N):
    nodes.append(Node(-1, [], [], []))
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:
import numpy as np
n=int(input())
d=[0]*n
p=[]
for i in range(n-1):
     a,b=map(int,input().split())
     a-=1
     b-=1
     d[a]-=1
     d[b]-=1
     p.append((a,b))
c=sorted(list(map(int,input().split())))[::-1]
idxs=np.argsort(d)[::-1]
for idx in idxs:
     x=c.pop()
     d[idx]=x
ans=0
for x in p:
     a,b=x
     ans+=min(d[a],d[b])
print(ans)
d=list(map(str,d))
print(' '.join(d))

Submission status: Wrong Answer

Solution code:
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))

for i in range(N):
    cur = T2.pop()
    cur.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:
n = int(input())
a = []
b = []
for _ in range(n-1):
    a1,b1 = map(int, input().split())
    a.append(a1)
    b.append(b1)

c = [int(_) for _ in input().split()]
sorted(c, reverse = True)

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

print(k)

string = ""
for i in range (n):
    string = string + str(c[i])
    if i != n-1:
        string += " "

print(string)

Submission status: Wrong Answer

Solution code:
I=lambda:map(int,input().split())
N = int(input())
T = {i:[] for i in range(N)}
E = []
for _ in range(N-1):
    a,b = I()
    E += [[a-1,b-1]]
    T[a-1] += [b]
    T[b-1] += [a]
Cs = sorted(list(I()))[::-1]
l = sorted(T.keys(), key=lambda k:-len(T[k]))
#print(l)
S = {l[i]:Cs[i] for i in range(N)}
M = 0
for a,b in E:
    M += min(S[a], S[b])
print(M)
print(*[S[i] for i in range(N)])

Submission status: Wrong Answer

Solution code:
m = int(input())

a_list = list()
b_list = list()
for i in range(m-1):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)

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

a2_list = list()
for i in range(m-1):
    for num in range(m+1):
        if a_list[i] == num:
            a2_list.append(c[num-1])

b2_list = list()
for i in range(m-1):
    for num in range(m+1):
        if b_list[i] == num:
            b2_list.append(c[num-1])

sum = 0
mini_list = list()
for k in range(m-1):
    mini = min(a2_list[k], b2_list[k])
    sum += mini
    mini_list.append(mini)

print(sum)

Submission status: Wrong Answer

Solution code:
N = int(input())
L = [list(map(int,input().split())) for k in range(N-1)]
c = list(map(int,input().split()))
G = [[0,k] for k in range(N)]

for e in L:
    G[e[0]-1][0] += 1
    G[e[1]-1][0] += 1

c = sorted(c)
G = sorted(G)
ans = [0 for k in range(N)]
for k in range(N-1):
    ans[G[k][1]] = c[k]
ans[G[N-1][1]] = c[-1]

T = [[] for k in range(N)]
for k in range(N-1):
    u,v,w = L[k][0],L[k][1],min(ans[L[k][0]-1],ans[L[k][1]-1])
    T[u-1].append([v-1,w])
    T[v-1].append([u-1,w])

kyori = [-1 for k in range(N)]
kyori[T[0][0][0]] = 0
que = [T[0][0][0]]
a = 0
while len(que) > 0:
    now = que.pop()
    for tsugi in T[now]:
        if kyori[tsugi[0]] == -1:
            kyori[tsugi[0]] = kyori[now] + tsugi[1]
            a += abs(kyori[tsugi[0]] - kyori[now])
            que.append(tsugi[0])
print(a)
print(*ans,sep=" ")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import itertools

def combinations(iterable):
    pool = tuple(iterable)
    r = len(pool)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

n = int(input())
nodes = []
for i in range(n - 1):
    a, b = map(int, input().split())
    nodes.append([a, b])
cs = [int(e) for e in input().split()]

count = 0
maxCount = 0
maxList = []

# cLoop = itertools.permutations(cs)
cLoop = combinations(cs)

for c in cLoop:
    for node in nodes:
        if(c[node[0] - 1] < c[node[1] - 1]):
            count = count + c[node[0] - 1]
        else:
            count = count + c[node[1] - 1]
    if(count > maxCount):
        maxCount = count
        maxList = c
    count = 0

print(maxCount)
print(' '.join(map(str, maxList)))

Submission status: Wrong Answer

Solution code:
n=int(input())
num=[[0,i] for i in range(n)]
d=[0 for i in range(n)]

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

c=list(map(int,(input().split())))
c.sort()
c.reverse()
num.sort()
for i in range(n):
  d[num[i][1]]=c[i]
print(sum(c)-c[0])
s=str(d)
t=""
for i in range(len(s)//3):
  t+=s[3*i+1]+" "
print(t[0:-1])

Submission status: Wrong Answer

Solution code:
import itertools

N = int(input())
ab = [list(map(int,input().split())) for i in range(N-1)]
c = list(map(int,input().split()))

ab_flatten = [flatten for inner in ab for flatten in inner]
ab_sort=sorted(ab_flatten,reverse=True,key=lambda x:ab_flatten.count(x))
ab_sort_unique = sorted(set(ab_sort), key=ab_sort.index)

c_sort = sorted(c,reverse=True)


ans = [0]*N

for i in range(N):
    if i == N-1:
        ans[ab_sort_unique[i]-1] = c_sort[0]
    else:
        ans[ab_sort_unique[i]-1] = c_sort[i+1]

ab_score = sum([min([ans[(ab[i][0]-1)],ans[(ab[i][1]-1)]]) for i in range(N-1)])

print(ab_score)
[print(ans[i],end=' ') for i in range(N)]

Submission status: Wrong Answer

Solution code:
N=int(input())
listA=[]
listB=[]
for i in range(N-1):
  a,b=map(int,input().split())
  listA+=[a]
  listB+=[b]
list1=list(map(int,input().split()))
list2=sorted(list1)
print(sum(list2)-list2[-1])

Submission status: Wrong Answer

Solution code:
N = int(input())

for i in range(N - 1):
    a, b = map(int, input().split())

cList = list(map(int, input().split()))

cList.sort()
cList.reverse()

total = 0
for i in range(N-1):
    total += cList[i+1]

print(total)
for i in range(N):
    print(cList[i], end=" ")

Submission status: Wrong Answer

Solution code:
N=int(input())


listA=[]
for i in range(N-1):
    eline= list(map(int,input().split()))
    listA.append(eline)
listB=list(map(int,input().split()))


import numpy as np
nodelist=np.zeros(N)
point=np.zeros(N)
for i in range(N-1):
    nodelist[listA[i][0]-1]=nodelist[listA[i][0]-1]+1
    nodelist[listA[i][1]-1]=nodelist[listA[i][1]-1]+1
hg=np.argsort(nodelist, axis=0)
nodelist.sort(axis=0)
for i in range(N):
    id1=int(hg[i])
    #print(id1)
    point[id1]=listB[i]
#print(point)
score=0
for i in range(N-1):
    left=listA[i][0]
    right=listA[i][1]
    spt=min(point[left-1],point[right-1])
    score=score+spt
print(int(score))
import sys
for i in range(N-1):
        print(int(point[i]),end=" ")
print(int(point[N-1]))

Submission status: Wrong Answer

Solution code:
n = int(input())
lis = [list(map(int,input().split())) for x in range(n-1)]
clis = list(map(int,input().split()))
ans_lis = [0]*n
ans = 0
for x in lis:
    ans += min(clis[x[0]-1],clis[x[1]-1])
    ans_lis[x[0]-1] = clis[x[0]-1]
    ans_lis[x[1]-1] = clis[x[1]-1]
print(ans)
print(*ans_lis)

Submission status: Wrong Answer

Solution code:
N = int(input())
memo = [[0,i] for i in range(N+1) ]
for i in range(N-1):
    a,b = map(int, input().split())
    memo[a][0] += 1
    memo[b][0] += 1
memo.sort(reverse = True)
memo.remove([0,0])

c = list(map(int, input().split()))
c.sort(reverse = True)
ans = 0
for i in range(1,N):
    ans += c[i]
lans = [0 for i in range(N)]
for i in range(N):
    lans[memo[i][1]-1] = c[i]
answer = str(lans[0])
for i in range(1,N):
    answer += " " + str(lans[i])
print(ans)
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

def cal(d, x):
    if len(d[x]) == 0:
        return 0
    
    total = 0
    for i, v in enumerate(d[x]):
        total += cal(d, v-1) + 1
    return total
    

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

c = list(map(int,input().split()))
c.sort(reverse=True)

w = []
for i in range(n):
    w.append([cal(d, i-1), i+1])
w.sort(reverse=True)

ans = [0 for _ in range(n)]
for x, y in zip(c, w):
    ans[y[1]-1] = x
print(sum(c[1:]))
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 1000003
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = int(input())
ab = [inpl() for _ in range(N-1)]
cc = inpl()
cc.sort()

lines = defaultdict(set)
for a,b in ab:
	a -= 1
	b -= 1
	lines[a].add(b)
	lines[b].add(a)

def search (s,w_0): #s->t
	global weight
	global q

	for t in list(lines[s]):
		w = w_0+1
		if weight[t] > w:
			heapq.heappush(q, [w,t])
			weight[t] = w

s = 0
weight = [INF]*N
weight[s] = 0
q = [[0,s]]
heapq.heapify(q)
while q:
	w,n = heapq.heappop(q)
	search(n,w)

s = weight.index(max(weight))
kokazu = [0]*N

def dfs1(s,b):
    tmp = 1
    if len(lines[s]) == 1 and b!= -1:
        kokazu[s] = tmp
        return tmp
    for t in lines[s]:
        if t == b:
            continue
        else:
            tmp += dfs1(t,s)
    kokazu[s] = tmp
    return tmp

dfs1(s,-1)

ansl = [0]*N
ind = 0

def dfs2(s,b):
    global ind
    global ansl
    ansl[s] = ind
    #print(s,ind)
    ind += 1
    tmpl = []
    for t in lines[s]:
        if t == b:
            continue
        tmpl.append([kokazu[t],t])
    tmpl.sort()
    for n,t in tmpl:
        dfs2(t,s)

dfs2(s,-1)

cnt = 0
for a,b in ab:
    cnt += min(cc[ansl[a-1]],cc[ansl[b-1]])

print(cnt)
ans = [cc[ansl[i]] for i in range(N)]
print(' '.join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
import sys
#import numpy as np

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    AB = ii2nnn(N-1)
    C = i2nn()
    C.sort()
    NR = [[i, 0, 0] for i in range(N)]
    for a, b in AB:
        NR[a-1][1] += 1
        NR[b-1][1] += 1
    NR.sort(key=lambda v: v[1])
    for c, nr in zip(C, NR):
        nr[2] = c
    NR.sort(key=lambda v: v[0])
    n = 0
    for a, b in AB:
        n += min(NR[a-1][2], NR[b-1][2])
    print(n)
    print(' '.join([str(nr[2]) for nr in NR]))

main()

Submission status: Wrong Answer

Solution code:
n=int(input())
num=[[0,i] for i in range(n)]
d=[0 for i in range(n)]

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

c=list(map(int,(input().split())))
c.sort()
c.reverse()
num.sort()
for i in range(n):
  d[num[i][1]]=c[i]
print(sum(c)-c[0])
s=str(d)

for i in range(len(s)//3):
  print(s[3*i+1])

Submission status: Wrong Answer

Solution code:
from collections import Counter
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        # x = self.find(x)
        # y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

    def is_same(self, x, y):
        return self.find(x) == self.find(y)


N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
c = sorted(list(map(int, input().split())), reverse=True)
ret = [0] * N
M = N - 1
uf1=UnionFind(N)
for i,j in ab:
    a,b=i,j 
    uf1.union(a-1,b-1)
pair = uf1.par.copy()
for i in range(N):
    uf1.find(i)

most = Counter(uf1.par).most_common()
ret[most[0][0]] = c[0]
pair = pair[:most[0][0]] + pair[most[0][0]+1:]
cnt = 0
for i, v in enumerate(c):
    if i == 0:
        continue
    if ret[cnt] > 0:
        cnt += 1
    ret[cnt] = v
    cnt += 1

print(sum(c[1:]))
print(' '.join([str(r) for r in ret]))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

def cal(d, x):
    if len(d[x]) == 0:
        return 0
    
    total = 0
    for i, v in enumerate(d[x]):
        total += cal(d, v-1) + 1
    return total
    
n = int(input())
d = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    d[a-1].append(b)

c = list(map(int,input().split()))
c.sort(reverse=True)

w = []
for i in range(n):
    w.append([cal(d, i-1), i+1])
w.sort(key=lambda x:x[1])

ans = [0 for _ in range(n)]
for x, y in zip(c, w):
    print(x,y)
    ans[y[1]-1] = x
print(sum(c[1:]))
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
#import numpy as np

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    AB = ii2nnn(N-1)
    C = i2nn()
    C.sort()
    NR = [[i, 0, 0] for i in range(N)]
    print(NR)
    for a, b in AB:
        NR[a-1][1] += 1
        NR[b-1][1] += 1
    NR.sort(key=lambda v: v[1])
    for c, nr in zip(C, NR):
        nr[2] = c
    NR.sort(key=lambda v: v[0])
    n = 0
    for a, b in AB:
        n += min(NR[a-1][2], NR[b-1][2])
    print(n)
    print(' '.join([str(nr[2]) for nr in NR]))

main()

Submission status: Wrong Answer

Solution code:
import copy
N = int(input())
I = []
for j in range(N - 1):
    I.append(list(map(int, input().split())))
c = list(map(int, input().split()))
c.sort(reverse=True)
datalist = []
suudata = []
suudatalist = []
suudatalist2 = []

for i in I:
    datalist.append(i[0])
    datalist.append(i[1])
#print(datalist)
for i in range(N):
    j = i + 1
    suudata.append(j)
    suudata.append(datalist.count(j))
    suudata2 = copy.copy(suudata)
    suudatalist.append(suudata2)
    suudata.clear()
#print(suudatalist)
suudatalist.sort(key=lambda x:-x[1])
for i in range(N):
    suudatalist2.append(suudatalist[i][0])
#print(suudatalist)
class Node:
    def __init__(self):
        self.nodedata = 0
class Eda:
    def __init__(self):
        self.min = 0
        self.leftnodenum = 0
        self.rightnodenum = 0
edalist = []
nodelist = []
for i in range(N):
    nodelist.append(Node())
    #nodelist[i].nodedata = c[i]
    nodelist[i].nodedata = c[suudatalist2.index(i + 1)]
    #print(nodelist[i].nodenum, nodelist[i].nodedata)

for i in range(N - 1):
    edalist.append(Eda())
    edalist[i].leftnodenum = I[i][0]
    edalist[i].rightnodenum = I[i][1]
    edalist[i].min = min(nodelist[edalist[i].leftnodenum-1].nodedata, nodelist[edalist[i].rightnodenum-1].nodedata)
    #print(edalist[i].edanum, edalist[i].leftnodenum, edalist[i].rightnodenum, edalist[i].min)

sum = 0
for i in range(N - 1):
    sum += edalist[i].min

#出力
print(sum)
for i in range(N):
    print(nodelist[i].nodedata, end=" ")
print("")

Submission status: Wrong Answer

Solution code:
N = int(input())
memo = [[0,i] for i in range(N+1) ]
for i in range(N-1):
    a,b = map(int, input().split())
    memo[a][0] += 1
    memo[b][0] += 1
memo.sort(reverse = True)
memo.remove([0,0])
c = list(map(int, input().split()))
c.sort(reverse = True)
ans = 0
for i in range(1,N):
    ans += c[i]
lans = [0 for i in range(N)]
for i in range(N):
    lans[memo[i][1]-1] = c[i]
print(ans)
print(lans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
c=list(map(int,input().split()))
c.sort()
L=[[0,i+1] for i in range(n)]
ans=[0 for i in range(n)]
for i in range(n-1):
  L[l[i][0]-1][0]+=1
  L[l[i][1]-1][0]+=1
L.sort()
L.reverse()
for i in range(n):
  ans[L[i][1]-1]=c[i]

ct=0
for i in range(n-1):
  ct+=min(ans[l[i][0]-1],ans[l[i][1]-1])
for i in range(n):
  ans[i]=str(ans[i])
print(ct)
print(' '.join(ans))