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.

Solution (Python):
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    def bfs(n, e, fordfs, C):
        
        W = [-1] * n
        
        i = 0
        W[e] = C[i]
        i += 1
        que = deque()
        que.append(e)
        while que and i<n:
            now = que.popleft()
            for ne in fordfs[now]:
                if W[ne] == -1:
                    W[ne] = C[i]
                    i += 1
                    que.append(ne)
        return W
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        A, B = LI()
        V[A-1].append(B-1)
        V[B-1].append(A-1)
    C = LI(); C.sort(reverse=True)
    e = 0
    ans = bfs(N,e,V,C)
    print(sum(ans)-C[0])
    print(" ".join(map(str,ans)))
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Solution (Python):
from collections import deque
n=int(input())
g=[set() for i in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  g[a].add(b)
  g[b].add(a)
c=list(map(int,input().split()))
c.sort(reverse=True)
print(sum(c)-c[0])
q=deque()
nums=[0]*(n+1)
q.appendleft(1)
while q:
  d=q.popleft()
  nums[d]=c.pop(0)
  for node in g[d]:
    if nums[node]==0:
      q.append(node)
print(*nums[1:])

Solution (Python):
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
edges = [set() for _ in range(N+1)] 
for _ in range(N-1):
    a, b = lr()
    edges[a].add(b)
    edges[b].add(a)
    
C = lr()
C.sort(reverse=True)
degrees = [len(x) for x in edges]
deg_1 = [i for i, d in enumerate(degrees) if d == 1]
score = sum(C[1:])
answer = [None] * (N+1)


while deg_1:
    leaf = deg_1.pop()
    answer[leaf] = C.pop()
    if not deg_1:
        break
    cand = edges[leaf].pop()
    edges[cand].remove(leaf)
    degrees[cand] -= 1
    if degrees[cand] == 1:
        deg_1.append(cand)

print(score)
print(*answer[1:])

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n=int(input())
ab=[list(map(int,input().split())) for i in range(n-1)]
c=list(map(int,input().split()))
c.sort()
print(sum(c)-c[-1])
lst=[[] for i in range(n)]
nodelst=[0]*n
ans=0
for i in range(n-1):
    a,b=ab[i]
    lst[a-1].append(b)
    lst[b-1].append(a)


nodelst[0]=c[-1]
d=deque(lst[0])
cnt=-2
while d:
    tmp=d.popleft()-1
    if nodelst[tmp]==0:
        nodelst[tmp]=c[cnt]
        cnt-=1
        d+=lst[tmp]
print(*nodelst)

Solution (Python):
from collections import *
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
C=list(map(int,input().split()))
C.sort(reverse=True)
data=[[] for i in range(N+1)]
num=[-1 for i in range(N+1)]
num[1]=C[0]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)
sumc=sum(C[1:])

stack=[1]
stack=deque(stack)
visited=set()
visited.add(1)
idx=1
while stack:
    a=stack.popleft()
    for p in data[a]:
        if not p in visited:
            visited.add(p)
            num[p]=C[idx]
            idx+=1
            stack.append(p)
print(sumc)
print(" ".join([str(num[i]) for i in range(1,N+1)]))

Solution (Python):
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
C=list(map(int,input().split()))
C.sort(reverse=True)
data=[[] for i in range(N+1)]
num=[-1 for i in range(N+1)]
num[1]=C[0]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)
sumc=sum(C[1:])

stack=[1]
visited=set()
visited.add(1)
idx=1
while stack:
    a=stack.pop()
    for p in data[a]:
        if not p in visited:
            visited.add(p)
            num[p]=C[idx]
            idx+=1
            stack.append(p)
print(sumc)
print(" ".join([str(num[i]) for i in range(1,N+1)]))

Solution (Python):
from collections import deque
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
c = list(map(int,input().split()))
c.sort(reverse=True)
graph = [[] for i in range(n+1)]
parent = [0 for i in range(n+1)]
root = 1
order = []
que = deque([root])
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
while que:
  x = que.popleft()
  order.append(x)
  for y in graph[x]:
    if parent[x] == y:
      continue
    parent[y] = x
    que.append(y)
ans = []
for i in range(n):
  ans.append((order[i],c[i]))
ans.sort()
print(sum(c[1:]))
for i in ans:
  print(i[1],end=" ")

Solution (Python):
N=int(input())

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

for i in range(N-1):
    a,b=map(int,input().split())
    G[a].append(b)
    G[b].append(a)
C=list(map(int,input().split()))
C.sort(reverse=True)
S=sum(C[1:])

num=[0 for i in range(N+1)]
un_used=[True for i in range(N+1)]

q=[]
q.append(1)
un_used[1]=False

while q:
    node = q.pop(0)
    num[node] = C.pop(0)
    
    for i in range(len(G[node])):
        if un_used[G[node][i]]:
            un_used[G[node][i]]=False
            q.append(G[node][i])

print(S)
print(" ".join(map(str,num[1:])))

Solution (Python):
N=int(input())
E=[[] for _ in range(N)]
for _ in range(N-1):
    a,b=map(lambda x:int(x)-1, input().split())
    E[a].append(b)
    E[b].append(a)
C=list(map(int, input().split()))

C.sort(reverse=True)

ans=[0]*(N)
stack=[0]
ans[0]=C[0]
k=1
while stack:
    n=stack.pop()
    for to in E[n]:
        if ans[to]!=0: continue
        ans[to]=C[k]
        k+=1
        stack.append(to)

print(sum(C[1:]))
print(' '.join(map(str,ans)))

Solution (Python):
from collections import deque
N = int(input())
tree = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    tree[a].append(b)
    tree[b].append(a)
C = list(map(int, input().split()))
C.sort(reverse=True)
q = deque([0])
visited = [False] * N
ans = {}
ans[0] = C[0]
visited[0] = True
pointa = 1
while len(q):
    v = q.pop()
    for e in tree[v]:
        if visited[e]:
            continue
        visited[e] = True
        ans[e] = C[pointa]
        pointa += 1
        q.append(e)
num = []
for i in range(N):
    num.append(str(ans[i]))
print(sum(C[1:]))
print(" ".join(num))

Solution (Python):
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
import heapq


"""
"""
N = gi()
t = [[] for i in range(N + 5)]

for i in range(1, N):
    a = gi()
    b = gi()
    t[a].append(b)
    t[b].append(a)
cs = [0] * N
for i in range(N):
    cs[i] = gi()
cs.sort()
print(sum(cs) - max(cs))
vs = [0] * (N + 5)
ci = N - 1
q = deque()
q.append(1)

while len(q):
    v = q.pop()
    
    vs[v] = cs[ci]
    ci -= 1
    for u in t[v]:
        if vs[u]:
            continue
        else:
            q.append(u)
for i in range(1, N + 1):
    print("%d " % (vs[i]), end="")

Solution (Python):
from heapq import heapify, heappop
N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N - 1)]
C = list(map(int, input().split()))

M = sum(C) - max(C)

nl = [list() for i in range(N)]
for a, b in AB:
    nl[a - 1].append(b - 1)
    nl[b - 1].append(a - 1)

v0 = -1
mlen = 0
for i, n in enumerate(nl):
    if len(n) > mlen:
        mlen = len(n)
        v0 = i

q = [-c for c in C]
heapify(q)
ans = [0] * N
stack = [(v0, -1)]
while len(stack) > 0:
    v, p = stack.pop()
    c = heappop(q)
    ans[v] = -c
    for next_v in nl[v]:
        if next_v != p:
            stack.append((next_v, v))
print(M)
print(*ans)

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(10 ** 7)

    def dfs(v):
        nonlocal curr

        num[v] = 0  

        for u in g[v]:
            if num[u] >= 0:
                continue
            dfs(u)
        num[v] = c[curr]
        curr += 1

    n = int(input())

    g = [set() for _ in range(n)]
    for _ in range(n - 1):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(b)
        g[b].add(a)
        
        
    *c, = sorted(map(int, input().split()))

    num = [-1] * n
    curr = 0
    dfs(0)

    print(sum(c[:-1]))
    print(*num)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

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

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

tmp = len(graph[0])
start = 0
for index, x in enumerate(graph):
    if len(x) > tmp:
        tmp = len(x)
        start = index

ans = 0
ans_lst = [-1] * N
ans_lst[start] = c.pop()
stack = [start]
while stack:
    x = stack.pop()
    for next_ in graph[x]:
        if ans_lst[next_] == -1:
            tmp = c.pop()
            ans_lst[next_] = tmp
            stack.append(next_)
            ans += tmp

print (ans)
print (*ans_lst, sep = ' ')

Solution (Python):
from collections import deque
N = int(input())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
C = sorted(list(map(int,input().split())))
A = [0 for _ in range(N+1)]
hist = [0 for _ in range(N+1)]
que = deque([1])
hist[1] = 1
cur = 0
while que:
    i = que[-1]
    if len(G[i])==1:
        A[i] = C[cur]
        cur += 1
        hist[i] = 2
        que.pop()
    flag = 2
    for j in G[i]:
        if hist[j]==0:
            que.append(j)
            hist[j] = 1
            flag = 1
    if flag==2 and hist[i]==1:
        A[i] = C[cur]
        cur += 1
        hist[i] = 2
        que.pop()
cnt = 0
hist = {(i,j):0 for i in range(1,N+1) for j in G[i]}
for i in range(1,N+1):
    for j in G[i]:
        if hist[(i,j)]==0:
            cnt += min(A[i],A[j])
            hist[(i,j)] = 1
            hist[(j,i)] = 1
print(cnt)
print(*A[1:])

Solution (Python):
import sys


stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) 
rs = lambda: stdin.readline().rstrip()  

N = ri()
nodes = [set() for _ in range(N+1)]

for _ in range(N-1):
    a, b = rl()
    nodes[a].add(b)
    nodes[b].add(a)

C = rl()
C.sort(reverse=True)
score = sum(C[1:])
deg = [len(x) for x in nodes]
deg_1 = [i for i, x in enumerate(deg) if x == 1]
answer = [0] * (N+1)

while deg_1:
    v = deg_1.pop()
    if not deg_1:
        answer[v] = C.pop()
        break
    w = nodes[v].pop()
    nodes[w].remove(v)
    deg[w] -= 1
    if deg[w] == 1:
        deg_1.append(w)
    answer[v] = C.pop()

print(score)
print(*answer[1:])

Solution (Python):
import sys

N=int(input())
ab=[list(map(int,input().split())) for i in range(N-1)]
c=list(map(int,input().split()))
c.sort(reverse=True)
data=[[] for i in range(N+1)]
for a,b in ab:
    data[a].append(b)
    data[b].append(a)
    
flag=[0]*(N+1)
ans=[0]*(N+1)
flag[1]=1
k=0
que=[1]
while que:
    for u in que:
        ans[u]=c[k]
        k+=1
    if k>N:
        break
    h=[]
    for u in que:
        for v in data[u]:
            if flag[v]==0:
                flag[v]=1
                h.append(v)
    que=h
print(sum(ans[2:]))
print(*ans[1:])

Solution (Python):
from collections import deque

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]
C = list(map(int, input().split()))

C.sort()
C = C[::-1]

graph = [[] for _ in range(N + 1)]
check = [1] * (N + 1)
for A, B in AB:
  graph[A].append(B)
  graph[B].append(A)

answer = [0] * (N + 1)
stack = deque()
stack.append(1)
check[1] = 0
ci = 0

while stack:
  s = stack.popleft()
  answer[s] = C[ci]
  ci += 1
  for g in graph[s]:
    if check[g]:
      check[g] = 0
      stack.append(g)
      
print(sum(C) - max(C))
print(*answer[1:])

Solution (Python):
from collections import deque
N = int(input())
G = {k: [] for k in range(N)}
E = [0]*N
ans = [-1]*N

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

    E[a-1] += 1
    E[b-1] += 1

C = sorted([int(i) for i in input().split()], reverse=True)
print(sum(C[1:]))


ans[E.index(max(E))] = C[0]
que = deque([(E.index(max(E)), -1)])

idx = 0
while que:
    ci, p = que.popleft()

    for ni in G[ci]:
        if ni != p:
            idx += 1
            ans[ni] = C[idx]
            que.append((ni, ci))

print(*ans)

Solution (Python):
from collections import deque
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

c = list(map(int, input().split()))
c.sort()
score = sum(c)-c[-1]

for i in range(n):
    if len(graph[i]) == 1:
        next_v = deque([i])
        break

ans = [-1]*n
while next_v:
    v = next_v.popleft()
    ans[v] = c.pop()
    for i in graph[v]:
        if ans[i] != -1:
            continue
        next_v.append(i)

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

Solution (Python):

n=int(input())
node={i:[]for i in range(n+1)}
visited=[False for i in range(n+1)]


first=0

for _ in range(n-1):
    a,b=map(int,input().split())
    node[a].append(b)
    node[b].append(a)
    if _==0:
        first+=a
        

dictionary=[0 for i in range(n+1)]

clist=list(map(int,input().split()))
clist=sorted(clist,reverse=True)
counter=0
dictionary[first]=clist[0]
K=sum(clist[1:])
from collections import deque
d=deque()
e=deque()
d.append(first)
visited[first]=True
while d:
    for some in d:
        for point in node[some]:
            if visited[point]==False:
                
                counter+=1
                visited[point]=True
                dictionary[point]=clist[counter]
                e.append(point)
            else:
                pass
    d=e
    e=deque()
print(K)
print(*dictionary[1:])

Solution (Python):

n=int(input())
node={i:[]for i in range(n+1)}
visited=[False for i in range(n+1)]


first=0

for _ in range(n-1):
    a,b=map(int,input().split())
    node[a].append(b)
    node[b].append(a)
    if _==0:
        first+=a
        

dictionary=[0 for i in range(n+1)]

clist=list(map(int,input().split()))
clist=sorted(clist,reverse=True)
counter=0
dictionary[first]=clist[0]
K=sum(clist[1:])
from collections import deque
d=deque()
e=deque()
d.append(first)
visited[first]=True
while d:
    for some in d:
        for point in node[some]:
            if visited[point]==False:
                
                counter+=1
                visited[point]=True
                dictionary[point]=clist[counter]
                e.append(point)
            else:
                pass
    d=e
    e=deque()
print(K)
print(*dictionary[1:])

Solution (Python):

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

stack = [0]
j = 0

while len(stack) > 0: 
    tmp = stack.pop(-1)
    check[tmp] = 1
    ans_list[tmp] = str(c[j])
    j += 1
    for i in range(len(reach[tmp])):
        if check[reach[tmp][i]] == 0:
            stack.append(reach[tmp][i])
        else:
            pass
    
print(sum(c) - max(c))
print(' '.join(ans_list))

Solution (Python):
N = int(input())
import collections

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

Cs = sorted(map(int, input().split()))
print(sum(Cs) - max(Cs))

sw = [-1] * N
stk = collections.deque([0])
while len(stk) > 0:
    crN = stk.popleft()
    if sw[crN] < 0:
        sw[crN] = Cs.pop()
        for l in Ls[crN]:
            stk.append(l)

print(*sw)

Solution (Python):
N = int(input())
import collections

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

Cs = sorted(map(int, input().split()), reverse=True)
print(sum(Cs) - Cs[0])

sw = [-1] * N
sw[0] = Cs[0]
ct = 1
stk = collections.deque()
stk.appendleft(0)
while len(stk) > 0:
    crN = stk[0]
    if len(Ls[crN]) == 0:
        stk.popleft()
        continue
    nxN = Ls[crN].popleft()
    if sw[nxN] > 0:
        continue
    sw[nxN] = Cs[ct]
    ct += 1
    stk.append(nxN)
print(" ".join(map(str, sw)))

Solution (Python):
N = int(input())
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
c = list(map(int,input().split()))
c.sort()
ans = sum(c) - max(c)
F = []
for i in range(1,N+1):
    n = len(G[i])
    if n == 1:
        F.append(i)
d = {}
i = 0
while i < N:
    x = F.pop(0)
    d[x] = c[i]
    i += 1
    if len(G[x]) > 0:
        y = G[x][0]
        G[y].remove(x)
        if len(G[y]) == 1:
            F.append(y)
ANS = []
for i in range(1,N+1):
    ANS.append(d[i])
print(ans)
print(*ANS)

Solution (Python):
import sys
import collections
input = sys.stdin.readline
N = int(input())
edge = [list(map(int,input().split())) for _ in range(N-1)]
c = sorted(list(map(int,input().split())),reverse=True)
graph = [[] for _ in range(N)]
ans = [-1 for _ in range(N)]
queue = collections.deque()

for e in edge:
    graph[e[0]-1].append(e[1]-1)
    graph[e[1]-1].append(e[0]-1)

for i in range(N):
    if len(graph[i])==1:
        queue.append(i)
        ans[i] = c[0]
        break
k=1
while queue:
    node = queue.popleft()
    for adj in graph[node]:
        if ans[adj]==-1:
            ans[adj] = c[k]
            k += 1
            queue.append(adj)
            
print(sum(c)-max(c))
print(*ans)

Solution (Python):
n=int(input())
a=[[]for i in range(n+1)]
for i in range(n-1):
    b,c=map(int,input().split())
    a[b].append(c)
    a[c].append(b)
b=[1]
c=[1]
l=[0]*(n+1)
l[1]=1
while len(b)>0:
    d=[]
    for i in b:
        for j in a[i]:
            if l[j]==0:
                d.append(j)
                c.append(j)
                l[j]=1
    b=d[:]
c=c[::-1]
e=sorted(list(map(int,input().split())))
b=[0]*n
for i in range(n):
    b[c[i]-1]=e[i]
print(sum(e[:-1]))
print(*b)

Solution (Python):
import sys
from collections import defaultdict as dd
from collections import deque as dq
input = sys.stdin.readline
N = int(input())
e = dd(list)
if N == 1:
  print(0)
  print(1)
  exit(0)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
res = [0] * (N + 1)
x = list(map(int, input().split()))
x.sort()
print(sum(x[: -1]))
p = 0
dimp = 0
for i in range(N + 1):
  if len(e[i]) > dimp:
    p = i
    dimp = len(e[i])
Q = dq([])
Q.append(p)
vis = set()
while len(Q):
  q = Q.popleft()
  y = x.pop()
  vis.add(q)
  res[q] = y
  for n in e[q]:
    if n in vis: continue
    Q.append(n)

print(" ".join(list(map(str, res[1: ]))))

Solution (Python):
def examD():
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        A, B = LI()
        V[A-1].append(B-1)
        V[B-1].append(A-1)
    C = LI(); C.sort()
    e = 0
    low = 0; up = N-1
    ans = 0; W = [-1] * N
    
    W[e] = C[up]; up -=1
    que = deque()
    que.append(e)
    while que or low<up:
        now = que.popleft()
        if len(V[now])==1 and now!=0:
            W[now] = C[low]
            ans += W[now]
            low +=1
        elif now!=0:
            W[now] = C[up]
            up -= 1
            ans += W[now]
        for ne in V[now]:
            if W[ne] == -1:
                que.append(ne)
    print(ans)
    print(" ".join(map(str,W)))

from string import digits
import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Solution (Python):
from collections import deque

n = int(input())
ab = [list(map(int, input().split())) for i in range(n-1)]
c = sorted(list(map(int, input().split())), reverse = True)
tree = [list() for i in range(n)]
already = [1] * n 
ans = [0] * n
k = 0
queue = deque([0])

for index,(a,b) in enumerate(ab):
  a -= 1
  b -= 1
  tree[a].append((index,b))
  tree[b].append((index,a))
while queue:
  now = queue.popleft()
  already[now] = 0
  ans[now] = c[k]
  k += 1
  for index,i in tree[now]:
    if already[i]:
      queue.append(i)
         
print(sum(c[1:]))
print(*ans)

Solution (Python):
import heapq
import sys
sys.setrecursionlimit(20000)
N = int(input())
ab = [tuple(map(int, input().split())) for i in range(N-1)]
c = list(map(int, input().split()))

print(sum(c) - max(c))
c = list(map(lambda x: x*(-1), c))
heapq.heapify(c)
d = [[0, i] for i in range(N)]
g = [set() for i in range(N)]
for a, b in ab:
    d[a-1][0] += 1
    d[b-1][0] += 1
    g[a-1].add(b-1)
    g[b-1].add(a-1)
d.sort(reverse=True, key=lambda x: x[0])
for i in range(N):
    d[i][0] = -1


ans = ["-1"]*N
ans[d[0][1]] = str(-1 * heapq.heappop(c))


def dfs(start):
    for x in g[start]:
        if ans[x] == "-1":
            ans[x] = str(-1 * heapq.heappop(c))
            dfs(x)


dfs(d[0][1])
d.sort(key=lambda x: x[1])


print(" ".join(ans))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



n = I()
G = [[] for _ in range(n)]
for a, b in LIR(n - 1):
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


C = sorted(LI())
ans = [0] * n
ans[0] = C.pop()
total = sum(C)
dq = deque([0])
while dq:
    u = dq.popleft()
    for v in G[u]:
        if not ans[v]:
            ans[v] = C.pop()
            dq += [v]


print(total)
print(*ans)

Solution (Python):
from collections import deque
N = int(input())
g = [set() for i in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    g[a].add(b)
    g[b].add(a)
    
c = list(map(int, input().split()))
c.sort(reverse=True)

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

q = deque()
nums = [0] * (N + 1)

q.appendleft(1)

while q:
  d = q.popleft()
  nums[d] = c.pop(0)
  for node in g[d]:
    if nums[node] == 0:
      q.append(node)
print(*nums[1:])

Solution (Python):
from collections import deque
N = int(input())
g = [set() for i in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    g[a].add(b)
    g[b].add(a)
    
c = list(map(int, input().split()))
c.sort(reverse=True)

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

q = deque()
nums = [0] * (N + 1)

q.appendleft(1)

while q:
  d = q.popleft()
  nums[d] = c.pop(0)
  for node in g[d]:
    if nums[node] == 0:
      q.appendleft(node)
print(*nums[1:])

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    
    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 self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

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

m = sum(c_arr) - max(c_arr)
ans = [0]*(n + 1)
a,b = edge.pop()
ans[a] = c_arr.pop()
ans[b] = c_arr.pop()
uf = UnionFind(n)
uf.union(a,b)
while edge:
    for i in range(len(edge)):
        if uf.same_check(a,edge[i][0]):
            if not uf.same_check(a,edge[i][1]):
                ans[edge[i][1]] = c_arr.pop()
                uf.union(edge[i][0],edge[i][1])
                edge.pop(i)
                break
        elif uf.same_check(a,edge[i][1]):
            ans[edge[i][0]] = c_arr.pop()
            uf.union(edge[i][0],edge[i][1])
            edge.pop(i)
            break
print(m)
print(*ans[1:])

Solution (Python):
from collections import deque
n=int(input())
ans=[0 for i in range(n)]
l=[[] for i in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  l[a].append(b)
  l[b].append(a)
l1=sorted(list(map(int,input().split())))
l1=l1[::-1]
sum=0
for i in range(1,n):
  sum+=l1[i]
q=deque(l1)
q1=deque([[1]])
while q:
  l2=q1.popleft()
  for i in l2:
    if ans[i-1]!=0:
      pass
    else:
      n2=q.popleft()
      ans[i-1]=n2
      q1.append(l[i])
print(sum)
answ=""
for i in range(n):
  answ+=str(ans[i])+" "
print(answ)

Solution (Python):
def main():

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

    max_l = 0
    max_i = -1
    for i in range(N):
        if len(count[i]) > max_l:
            max_l = len(count[i])
            max_i = i

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

    cur = [max_i]
    val = [0 for _ in range(N)]
    i = 0
    val[max_i] = c[i]
    i += 1
    ans = 0
    while cur:
        temp = []
        for j in cur:
            for k in count[j]:
                if val[k] == 0:
                    val[k] = c[i]
                    ans += c[i]
                    i += 1
                    temp.append(k)
        cur = temp

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

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n=int(input())
    ab=[list(map(int,input().split())) for _ in [0]*(n-1)]
    c=sorted(list(map(int,input().split())),reverse=True)
    g=[set() for _ in [0]*n]
    [g[a-1].add(b-1) for a,b in ab]
    [g[b-1].add(a-1) for a,b in ab]
    l=[]
    print(sum(c)-max(c))
    for i in range(n):
        if len(g[i])==1:
            l.append(i)
    ans_l=[0]*n
    while l:
        i=l.pop()
        ans_l[i]=c.pop()
        for j in g[i]:
            g[j].remove(i)
            if len(g[j])==1:
                l.append(j)
        g[i]=set()
    print(*ans_l)
main()

Solution (Python):
n, *L = map(int, open(0).read().split())
ab = L[:2 * n - 2]
c = sorted(L[2 * n - 2:])
con = [[] for _ in range(n)]
ans = [0] * n
tot = sum(c) - max(c)
for a, b in zip(*[iter(ab)] * 2):
	con[a - 1].append(b - 1)
	con[b - 1].append(a - 1)
vis = [0] * n
q = [0]
vis[0] = 1
while q:
	cur = q.pop()
	ans[cur] = c.pop()
	for nxt in con[cur]:
		if vis[nxt]:
			continue
		q.append(nxt)
		vis[nxt] = 1
print(tot)
print(*ans)

Solution (Python):
import sys
input = sys.stdin.readline
n=int(input())
edge=[set() for i in range(n+1)]
for i in range(n-1):
    a,b=[int(j) for j in input().split()]
    edge[a].add(b)
    edge[b].add(a)

c=[int(j) for j in input().split()]
d=[len(i) for i in edge]

d1=[i for i,x in enumerate(d) if x==1]

ans=[None]*(n+1)
c.sort()
c.reverse()
m=sum(c)-c[0]

while d1:
    v=d1.pop()
    if not d1:
        ans[v]=c.pop()
        break
    w=edge[v].pop()
    edge[w].remove(v)
    d[w]-=1
    if d[w]==1:
        d1.append(w)
    ans[v]=c.pop()

print(m)
print(*ans[1:])

Solution (Python):
n = int(input())
edge = [ [ int(v)-1 for v in input().split() ] for i in range(n-1) ]
num_list = sorted([ int(v) for v in input().split() ])
parent_list = [ None for i in range(n) ]
connect_list = [ [] for i in range(n) ]

for a, b in edge:
    connect_list[a].append(b)
    connect_list[b].append(a)

connect_point = [ len(i) for i in connect_list ]
p = connect_point.index(max(connect_point))

depth_list = [[p]]
search_list = [p]
parent_list[p] = -1

while search_list:
    new_search_list = []
    for i in search_list:
        for j in connect_list[i]:
            if parent_list[j] is None:
                parent_list[j] = i
                new_search_list.append(j)
    if new_search_list:
        depth_list.append(new_search_list)
    search_list = new_search_list

node = [ None for i in range(n) ]
q = 0

for i in depth_list[::-1]:
    for j in i:
        node[j] = num_list[q]
        q += 1

print(sum(num_list[:-1]))
print(*node)