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

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N = NI()
    edges = [[i]+NLI() for i in range(N-1)]
    C = NLI()
    tree = [[] for _ in range(N+1)]
    for edge in edges:
        tree[edge[1]].append(edge[2])
        tree[edge[2]].append(edge[1])
    option_nums = []
    for i, node in enumerate(tree):
        option = len(node)
        option_nums.append([option, i])
    option_nums = sorted(option_nums, reverse=True)
    C = sorted(C, reverse=True)
    ans = {}
    for op, c in zip(option_nums, C):
        ans[op[1]] = c
    A = 0
    for edge in edges:
        x, y = edge[1], edge[2]
        A += min(ans[x], ans[y])
    print(A)
    for i in range(1, N+1):
        if i == N:
            print(str(ans[i]))
            continue
        print(str(ans[i]), end=" ")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    ab = in_nl2(N - 1)
    edge = [[] for _ in range(N)]

    for i in range(N - 1):
        a, b = ab[i]
        a, b = a - 1, b - 1
        edge[a].append(b)
        edge[b].append(a)

    C = sorted(in_nl(), reverse=True)

    dim = []
    for i, e in enumerate(edge):
        dim.append((len(e), i))

    dim.sort(reverse=True)

    V = [0] * N

    for i in range(N):
        V[dim[i][1]] = C[i]

    score = 0
    for i in range(N - 1):
        a, b = ab[i]
        a, b = a - 1, b - 1
        score += min(V[a], V[b])

    print(score)
    print(' '.join(map(str, V)))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())

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

c = list(map(int, input().split()))
c.sort()
print(sum(c) - max(c))

ans = []
s = [0] * n
que = deque([0])
while que:
    t = que.popleft()
    ans.append(c.pop())
    s[t] = 1
    for e in g[t]:
        if not s[e]:
            que.append(e)

print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())

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

c = list(map(int, input().split()))
c.sort()
ans = []
s = [0] * n
que = deque([0])
while que:
    t = que.popleft()
    ans.append(c.pop())
    s[t] = 1
    for e in g[t]:
        if not s[e]:
            que.append(e)    

print(*ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
g = [[] * n for i in range(n)]
for i in range(n-1):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  g[u].append(v)
  g[v].append(u)
  
d = list(map(int,input().split()))
from collections import deque
 
que = deque()
que.append(0)
chk = [False]*n
chk[0] = True
ans = [0]*n
ans[0] = d[0]
cnt = 1
while que:
  now = que.popleft()
  if cnt == n:
    break
  for i in g[now]:
    if not chk[i]:
      chk[i] = True
      ans[i] = d[cnt]
      cnt += 1
      que.append(i)
      
d.sort()
print(sum(d[:n-1]) if n > 1 else 0)
print(*ans)

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
graph = [[] for i in range(N)]
for _ in range(N-1):
  a,b = IL()
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
jisu = [(len(graph[i]),i) for i in range(N)]
jisu.sort()
A = IL()
A.sort()
ans = [-1 for i in range(N)]
for i in range(N):
  ans[jisu[i][1]] = A[i]
M = 0
for i in range(N):
  for j in graph[i]:
    M += min(ans[i],ans[j])
print(M//2)
print(*ans)

Submission status: Wrong Answer

Solution code:
import heapq
import sys
from collections import deque


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    N = int(input())
    tree = [[] for _ in range(N)]
    edge = deque([])

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

    C = list(map(int, input().split()))
    C.sort()
    D = []
    for c in C:
        heapq.heappush(D, -c)

    answer = [0] * N
    a, b = edge.popleft()

    new_node = deque([])
    for n in tree[a]:
        new_node.append(n)
    for n in tree[b]:
        new_node.append(n)

    while new_node:
        s = new_node.popleft()
        if answer[s] == 0:
            answer[s] = heapq.heappop(D) * (-1)
        for n in tree[s]:
            if answer[n] == 0:
                new_node.append(n)

    print(sum(C[:-1]))
    print(*answer)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq
import sys
from collections import deque


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    N = int(input())
    tree = [[] for _ in range(N)]
    edge = deque([])

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

    C = list(map(int, input().split()))
    C.sort()
    D = []
    for c in C:
        heapq.heappush(D, c)

    answer = [0] * N
    a, b = edge.popleft()

    new_node = deque([])
    for n in tree[a]:
        new_node.append(n)
    for n in tree[b]:
        new_node.append(n)

    while new_node:
        s = new_node.popleft()
        if answer[s] == 0:
            answer[s] = heapq.heappop(D)
        for n in tree[s]:
            if answer[n] == 0:
                new_node.append(n)

    print(sum(C[:-1]))
    print(*answer)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    edges = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edges[a].append(b)
        edges[b].append(a)

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

    cnt = [None] * N
    for i in range(N):
        l = len(edges[i])
        cnt[i] = l

    # 隣接ノードが少ない順
    ids = sorted(range(N), key=lambda x: cnt[x])
    ans = [None] * N
    for i in range(N // 2):
        ans[ids[2 * i]] = C[i]
        ans[ids[2 * i + 1]] = C[N - i - 1]

    if N % 2 == 1:
        ans[ids[-1]] = C[N // 2 + 1]

    s = 0
    q = deque([0])
    visited = [False] * N
    visited[0] = True
    while q:
        i = q.popleft()

        for j in edges[i]:
            if visited[j]:
                continue

            s += min(ans[i], ans[j])
            visited[j] = True
            q.append(j)

    print(s)
    print(*ans, sep=" ")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    N = int(input())
    tree = [[] for _ in range(N)]
    edge = []

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

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

    node_num = []
    for i in range(N):
        node_num.append([i, len(tree[i])])

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

    node_number = [0 for _ in range(N)]
    for i in range(N):
        node_number[node_num[i][0]] = C[i]

    edge_num = []
    for i in range(N - 1):
        a, b = edge[i]
        edge_num.append(min(node_number[a], node_number[b]))
    print(sum(edge_num))
    print(*node_number)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    edges = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edges[a].append(b)
        edges[b].append(a)

    C = list(map(int, input().split()))
    idx = -1
    m = INF
    for i in range(N):
        if m > C[i]:
            idx = i
            m = C[i]

    q = deque([idx])
    visited = [False] * N
    visited[idx] = True

    ans = 0
    order = [C[idx]]
    while q:
        i = q.popleft()

        for j in edges[i]:
            if visited[j]:
                continue

            ans += min(C[i], C[j])
            order.append(C[j])
            visited[j] = True
            q.append(j)

    print(ans)
    print(*order, sep=" ")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
ed = [[] for _ in range(n)]
al,be = [],[]
for _ in range(n-1):
    a,b = map(int,input().split())
    al.append(a-1)
    be.append(b-1)
    ed[a-1].append(b-1)
    ed[b-1].append(a-1)
    
c = list(map(int,input().split()))

q = []
for i in range(n):
    q.append((len(ed[i]),i))
    
q.sort(reverse = True)
c.sort(reverse = True)
ans = [0]*n

for i in range(n):
    ans[q[i][1]] = c[i]
    
sc = 0
for i in range(n-1):
    sc += min(ans[al[i]],ans[be[i]])
    
print(sc)
print(*ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
ab=[list(map(int,input().split())) for _ in range(n-1)]
c=list(map(int,input().split()))
c.sort()
print(sum(c)-c[-1])
ki=[[i,0] for i in range(n)]
for a,b in ab:
  a,b=a-1,b-1
  ki[a][1]+=1
  ki[b][1]+=1
# 次数の低いノードから順に小さな値を入れていく
ans=[0]*n
ki.sort(key=lambda x:x[1])
for i in range(n):
  ans[ki[i][0]]=c[i]
print(' '.join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
l = sorted(list(map(int,input().split())),reverse=True)
ans = [-1]*n
for i in range(n):
    if len(e[i]) == 1:
        q = deque([])
        q.append(i)
        now = 1
        ans[i] = l[now]
        while q:
            b = q.popleft()
            for nex in e[b]:
                if ans[nex] == -1:
                    ans[nex] = l[now]
                    now += 1
                    q.append(nex)
        count = 0
        for j in range(n):
            for k in e[j]:
                count += min(ans[j],ans[k])
        print(count//2)
        print(*ans)
        exit()

Submission status: Wrong Answer

Solution code:
n = int(input())
ki = [[0,i] for i in range(n)]
route = []
ans = [0 for i in range(n)]
for i in range(n-1):
    a , b = map(lambda x: int(x)-1,input().split())
    ki[a][0] += 1
    ki[b][0] += 1
    route.append((a,b))
ki.sort()
c = list(map(int,input().split()))
c.sort()
for i in range(n):
    ans[ki[i][1]] = c[i]
m = 0
for a , b in route:
    m += min(ans[a],ans[b])

print(m)
print(*ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int,input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
C = list(map(int,input().split()))
C.sort(reverse = True)

D = [0] * N

index = 0
# def dfs(x, parent):
#     global index
#     D[x] = C[index]
#     index += 1
#     for u in edges[x]:
#         if u != parent:
#             dfs(u, x)

# dfs(0, -1)

print(sum(C[1:]))
print(*D)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
query = [getNM() for i in range(N - 1)]
C = getList()
C.sort()

dist = [[] for i in range(N)]
for i in range(N - 1):
    a, b = query[i]
    dist[a - 1].append(b - 1)
    dist[b - 1].append(a - 1)

sta = 0

for i in range(N):
    if len(dist[i]) == 1:
        sta = i
        break

point = [-1] * N

def dfs(now):
    u = C.pop()
    point[now] = u
    for i in dist[now]:
        if point[i] >= 0:
            continue
        dfs(i)

dfs(sta)

print(*point)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
query = []
dist = [[] for i in range(N)]
for i in range(N - 1):
    a, b = getNM()
    query.append([a - 1, b - 1])
    dist[a - 1].append(b - 1)
    dist[b - 1].append(a - 1)
lista = [[i] for i in range(N)]
for i in range(N):
    lista[i].append(len(dist[i]))
lista.sort(key = lambda i: i[1])

d = sorted(getList())
num = [0] * N
for i in range(N):
    num[lista[i][0]] = d[i]

ans = 0
for que in query:
    a1, b1 = que
    ans += min(num[a1], num[b1])
print(ans)
print(*num)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
query = []
dist = [[] for i in range(N)]
for i in range(N - 1):
    a, b = getNM()
    query.append([a - 1, b - 1])
    dist[a - 1].append(b - 1)
    dist[b - 1].append(a - 1)
lista = [[i] for i in range(N)]
for i in range(N):
    lista[i].append(len(dist[i]))
lista.sort(key = lambda i: i[1])

d = sorted(getList())
num = [0] * N
for i in range(N):
    num[lista[i][0]] = d[i]

ans = 0
for que in query:
    a1, b1 = que
    ans += min(num[a1], num[b1])
print(ans)

Submission status: Wrong Answer

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


def DFS(num):
    if color[num]=="white":
        ans[num]=C.pop()
        color[num]="black"
        for i in T[num]:
            DFS(i)


n=int(input())
AB=[list(map(int,input().split())) for _ in range(n-1)]
C=sorted(list(map(int,input().split())))
color=["white" for _ in range(n)]

T=[[] for _ in range(n)]
for a,b in AB:
    T[a-1].append(b-1)
    T[b-1].append(a-1)

ans=[0 for _ in range(n)]
DFS(0)

point=0
color=["white" for _ in range(n)]
for i in range(n):
    if len(T[i])>0:
        color[i]="black"
        for j in T[i]:
            if color[j]=="white":
                point +=min(ans[i],ans[j])
                color[j]="black"

print(point)
print(*ans)

Submission status: Wrong Answer

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


def DFS(num):
    if color[num]=="white":
        ans[num]=C.pop()
        color[num]="black"
        for i in T[num]:
            DFS(i)


n=int(input())
AB=[list(map(int,input().split())) for _ in range(n-1)]
C=sorted(list(map(int,input().split())))
color=["white" for _ in range(n)]

T=[[] for _ in range(n)]
for a,b in AB:
    T[a-1].append(b-1)
    T[b-1].append(a-1)

ans=[0 for _ in range(n)]
DFS(0)

point=0
color=["white" for _ in range(n)]
for i in range(n):
    if len(T[i])>0:
        color[i-1]="black"
        for j in T[i]:
            if color[j-1]=="white":
                point +=min(ans[i-1],ans[j-1])
                color[j-1]="black"

print(point)
print(*ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
AB=[list(map(int,input().split())) for _ in range(n-1)]
C=sorted(list(map(int,input().split())))
color=["white" for _ in range(n)]

ans=[0 for _ in range(n)]
T=[[] for _ in range(n+1)]
for a,b in AB:
    T[a].append(b)
    T[b].append(a)

for i in range(1,n+1):
    if len(T[i])>0 and color[i-1]=="white":
        ans[i-1]=C.pop()
        color[i-1]="black"
        for j in T[i]:
            if color[j-1]=="white":
                ans[j-1]=C.pop()
                color[j-1]="black"

point=0
color=["white" for _ in range(n)]
for i in range(1,n+1):
    if len(T[i])>0:
        color[i-1]="black"
        for j in T[i]:
            if color[j-1]=="white":
                point +=min(ans[i-1],ans[j-1])
                color[j-1]="black"
                
print(point)
print(*ans)

Submission status: Wrong Answer

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

c = list(map(int, input().split()))
c.sort()
graph.sort(key=lambda x:len(x[1]))
node = [None]*n
for i in range(n):
    node[graph[i][0]] = c[i]
ans = 0
for a, b in edge:
    ans += min(node[a], node[b])
print(ans)
print(*node)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from collections import defaultdict,deque
N = int(stdin.readline().rstrip())
adj = defaultdict(set)

for i in range(N-1):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]
    adj[a].add(b)
    adj[b].add(a)
    
C = [int(x) for x in stdin.readline().rstrip().split()]

ans = sum(C) - max(C)
print(ans)

visit_p = deque()
visit_p.append(1)
visited = [False]*(N+1)
visited[1] = True

C.sort(reverse=True)
 
print(C[0],end=" ")
cnt = 1

while visit_p:
    now_v = visit_p.popleft()
    for v in adj[now_v]:
        if visited[v]:
            continue
        print(C[cnt],end=" ")
        cnt += 1
        visited[v] = True
        visit_p.append(v)

Submission status: Wrong Answer

Solution code:
from collections import deque

def main():
    N = int(input())
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
    C = list(map(int, input().split()))
    cnt = [0] * N
    visited = [False] * N
    Q = deque([0])
    while Q:
        q = Q.popleft()
        visited[q] = True
        for v in edge[q]:
            if q == v:
                continue
            if visited[v]:
                continue
            cnt[q] += 1
            Q.append(v)

    tmp = []
    for i in range(N):
        tmp.append((cnt[i],i))
    tmp.sort()
    C.sort()
    d = [0] * N
    for i in range(N):
        d[tmp[i][1]] = C[i]

    print(sum(C) - max(C))
    print(*d)
    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
    C = list(map(int, input().split()))
    cnt = []
    for i in range(N):
        cnt.append((len(edge[i]),i))

    cnt.sort(reverse=True)
    C.sort(reverse=True)
    d = [0] * N
    for i in range(N):
        d[cnt[i][1]] = C[i]

    M = sum(C) - max(C)
    print(M)
    print(*d)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
con = defaultdict(int)
for i in range(N - 1):
    ai, bi = map(int, input().split())
    con[ai] += 1
    con[bi] += 1
c = list(map(int, input().split()))

c.sort(reverse=True)
print(sum(c[1:]))
d = [0] * N
for i, ci in enumerate(sorted(con.items(), key=lambda t: t[1], reverse=True)):
    d[ci[0] - 1] = c[i]
print(' '.join(list(map(str, d))))

Submission status: Wrong Answer

Solution code:
N=int(input())

D={v:0 for v in range(N)}
X=[]
for i in range(N-1):
    a,b=map(int,input().split())
    D[a-1]+=1
    D[b-1]+=1
    X.append((a-1,b-1))

E=sorted(D.items(),key=lambda x:x[1],reverse=True)

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

H=[0]*N
for i in range(N):
    H[E[i][0]]=C[i]

S=0
for (u,v) in X:
    S+=min(C[u],C[v])

print(S)
for i in range(N):
    print(H[i],end="")
    if i!=N-1:
        print(" ",end="")

print()

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
cl = list(map(int, input().split()))

d = [0]*n
for a,b in ab:
    d[a-1] += 1
    d[b-1] += 1

l = [(v,i) for i,v in enumerate(d)]
l.sort()
cl.sort()

res = [0]*n
for i in range(n):
    res[l[i][1]] = cl[i]

r = 0
for a,b in ab:
    r += min(res[a-1], res[b-1])

print(r)
print(*res)

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
cl = list(map(int, input().split()))

d = [0]*n
for a,b in ab:
    d[a-1] += 1
    d[b-1] += 1

l = [(v,i) for i,v in enumerate(d)]
l.sort(reverse=True)
cl.sort(reverse=True)

res = [0]*n
for i in range(n):
    res[l[i][1]] = cl[i]

r = 0
for a,b in ab:
    r += min(res[a-1], res[b-1])

print(r)
print(*res)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
edge=[[] for _ in range(N)]
for _ in range(N-1):
    a,b=map(int1,input().split())
    edge[a].append(b)
    edge[b].append(a)
C=list(map(int,input().split()))
C.sort(reverse=1)
print(sum(C)-C[0])
que=deque([0])
ans=[-1]*N
while que:
    v=que.popleft()
    ans[v]=C.pop()
    for nv in edge[v]:
        if ans[nv]==-1:
            que.append(nv)
print(*ans)

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque
inf = 10 ** 15
mod = 10 ** 9 + 7
n = int(input())
ab = [[] for i in range(n)]
count = [0 for i in range(n)]
score = [0 for i in range(n)]
edge = []
for i in range(n-1):
    a,b = map(int, input().split())
    edge.append([a-1, b-1])
    count[a-1]+=1
    count[b-1]+=1
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
count = list(enumerate(count))
count.sort(key=lambda x:x[1])
c = list(map(int, input().split()))
c.sort()
for i,(ind,_) in enumerate(count):
    score[ind] = c[i]
ans = 0
for a,b in edge:
    ans+=min(score[a], score[b])
print(ans)
print(*score, sep=' ')