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):
import copy
import queue
q = queue.Queue()
n = int(input())

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

def bfs():
    start = 0
    valid = [1]*100001
    q.put((start,0)) 
    valid[start] = 0
    level[start][1] = 0
    while not q.empty():
        p,d = q.get()
        for nei in neib[p]:
            if valid[nei]:
                valid[nei]=0
                level[nei][1] = d+1
                q.put((nei,d+1))
bfs()

level.sort(key = lambda x:x[1])
c = list(map(int,input().split()))
c.sort(reverse=True)
res = 0
for i in range(n):
    level[i].append(c[i])
    res += c[i]
res -= c[0]
print(res)
level.sort(key = lambda x:x[0])
for i in range(n):
    print(level[i][2],end=" ")
print("")

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

N=int(input())

L=[[]for i in range(N+1)]
C=[0 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)
    C[a]+=1
    C[b]+=1
M=0
m=0
for i in range(1,N+1):
    if len(L[i])>m:
        m=len(L[i])
        M=i
C=list(map(int,input().split()))
C.sort(reverse=True)

l=[-1 for i in range(N+1)]
l[M]=0

X=[0 for i in range(N+1)]
X[M]=C[0]
cnt=1
def dfs(x):
    for i in L[x]:
        if l[i]==-1:
            l[i]=l[x]+1
            global cnt
            X[i]=C[cnt]
            cnt+=1
            dfs(i)
dfs(M)


print(sum(X)-max(X))
ans=str(X[1])
for i in range(2,N+1):
    ans+=" "+str(X[i])
print(ans)

Solution (Python):
from collections import deque


N = int(input())
branch = [0] * (N - 1)
for i in range(N-1):
    branch[i] = list(map(int, input().split()))
C = list(map(int, input().split()))
C.sort(reverse=True)
M = sum(C[1:])

adj = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = branch[i]
    adj[a].append(b)
    adj[b].append(a)

ans = [-1] * (N+1)
deq = deque()
deq.appendleft(1)
while len(deq) > 0:
    v = deq.pop()
    ans[v] = C.pop(0)
    for u in adj[v]:
        if ans[u] == -1:
            deq.appendleft(u)

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

Solution (Python):
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 7)
n = int(input())
s = [list(map(int,input().split())) for i in range(n-1)]
c = list(map(int,input().split()))
c.sort()
t = [-1] * n 
p = sum(c[:n-1])
q = defaultdict(list)
for i in range(n-1):
    q[s[i][0]] += [s[i][1]]
    q[s[i][1]] += [s[i][0]]

t1 = [t,1]

def find(q,x,t1):
    r = q[x]
    t1[0][x-1] = 0
    for i in range(len(r)):
        if t1[0][r[i]-1] == 0:
            continue
        else:
            t1 = find(q,r[i],t1)
    t1[0][x-1] = t1[1]
    t1[1] += 1
    return t1

o = find(q,1,t1)
o1 = o[0]
print(p)
b = ""
for i in range(n):
    b += str(c[o1[i]-1]) + " "

print(b)

Solution (Python):
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True 
def ddprint(x):
  if DBG:
    print(x)

n = inn()
edges = []
dst = [ [] for i in range(n) ]
for i in range(n-1):
    a,b = inm()
    a -= 1
    b -= 1
    dst[a].append(b)
    dst[b].append(a)
    edges.append((a,b))
c = inl()

c.sort(reverse=True)
labs = [-1] * n
q = []
for i in range(n):
    if len(dst[i]) == 1:
        q.append(i)

while(len(q)>1):
    i = q.pop()
    labs[i] = c.pop()
    d = dst[i][0]
    dst[d].remove(i)
    if len(dst[d]) == 1:
        q.append(d)

i = q.pop()
labs[i] = c.pop()

m = 0
for z in edges:
    m += min(labs[z[0]], labs[z[1]])
print(m)
for i in range(n):
    printn(str(labs[i]) + ' ')
print("")

Solution (Python):
from collections import deque
 

N = int(input())
edge = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  edge[a-1] += [b-1]
  edge[b-1] += [a-1]
A = list(map(int, input().split()))
A.sort(reverse = 1)
print(sum(A[1:]))

ans = [[0, A[0]]]
cnt = 1
visited = [1] + [0]*(N-1)
que = deque([0]) 
while que:
  u = que.pop()
  for v in edge[u]:
    if visited[v] == 0:
      que.append(v)
      visited[v] = 1
      ans += [[v,A[cnt]]]
      cnt += 1
ans.sort()

ans2 = []
for i in range(N):
  ans2 += [ans[i][1]]
print(' '.join(map(str, ans2)))

Solution (Python):

import sys
sys.setrecursionlimit(1000000)

n = int(input())
d = [0] * n
a = []
b = []
connected = [[] for _ in range(n)]
for i in range(n - 1):
    ai, bi = list(map(int, input().split()))
    d[ai-1] += 1
    d[bi-1] += 1
    a.append(ai-1)
    b.append(bi-1)
    connected[ai-1].append(bi-1)
    connected[bi-1].append(ai-1)

c = list(map(int, input().split()))
parents = [-1] * n
result = [0] * n
sortedc = sorted(c, reverse=True)

def dfs(current, parent):
    parents[current] = parent
    parent = parents[current]
    for i in connected[current]:
        if i != parent:
            dfs(i, current)


def ddfs(current):
    result[current] = sortedc.pop(0)
    nexts = []
    for i in connected[current]:
        if parents[current] != i:
            nexts.append((i, d[i]))
    sortedNexts = sorted(nexts, reverse=True, key=lambda x: x[1])

    for nxt, _ in sortedNexts:
        ddfs(nxt)

def main():

    dandi = []
    for i, di in enumerate(d):
        dandi.append((i, di))
    sortedd = sorted(dandi, reverse=True, key=lambda x: x[1])

    root = sortedd[0][0]
    dfs(root, -1)
    ddfs(root)

    resultSum = 0
    for i in range(n-1):
        resultSum += min(result[a[i]], result[b[i]])
    print(resultSum)
    print(' '.join(map(str, result)))



if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

N = int(input())
E = [[] for _ in range(N)]
for a, b in [[int(i) - 1 for i in input().split()] for _ in range(N - 1)]:
    E[a].append(b)
    E[b].append(a)
C = [int(i) for i in input().split()]
C.sort(reverse=True)

ans = [0] * N

def bfs(i):
    cur = 0
    Q = deque()
    Q.append(0)
    visited = [False] * N
    while Q:
        v = Q.popleft()
        visited[v] = True
        ans[v] = C[cur]
        cur += 1
        for e in E[v]:
            if visited[e]:
                continue
            Q.append(e)

bfs(0)
print(sum(C[1:]))
print(*ans)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
G = [[] for i in range(N)]
deg = [0] * N
E = []
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)
    E.append((a, b))
    deg[a] += 1
    deg[b] += 1

C = list(map(int, input().split()))
C = sorted(C)
que = deque()
for i in range(N):
    if deg[i] == 1:
        que.append(i)

D = [-1] * N
used = [0] * N
i = 0
while i < N:
    k = que.popleft()
    D[k] = C[i]
    i += 1
    for w in G[k]:
        deg[w] -= 1
        if deg[w] == 1:
            que.append(w)

ans = 0
for i in range(len(E)):
    ans += min(D[E[i][0]], D[E[i][1]])

print(ans)
print(*D)

Solution (Python):
from collections import deque

N = int(input())
s = [set() for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    s[a - 1].add(b - 1)
    s[b - 1].add(a - 1)
c = list(map(int, input().split()))
c.sort(reverse=True)
ans = [0] * N
ans[0] = c[0]
cp = 1
i = 0
pre = -1
dq = deque()
while True:
    for x in s[i]:
        if x != pre:
            ans[x] = c[cp]
            cp += 1
            dq.appendleft((x, i))
    if dq:
        i, pre = dq.pop()
    else:
        break

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

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op



inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    
    n = get_int()
    a, b = get_data(n-1, [int, int])
    c = get_li()
    c.sort()
    node2children = defaultdict(set)
    for ai, bi in zip(a, b):
        node2children[ai].add(bi)
        node2children[bi].add(ai)
    leaves = deque()
    for node, children in node2children.items():
        if len(children) == 1:
            leaves.append(node)
    sequence = []
    score = 0
    i = 0
    while len(leaves) > 0:
        node = leaves.popleft()
        sequence.append(node)
        if len(node2children[node]) == 0:
            break
        score += c[i]
        i += 1
        parent = node2children[node].pop()
        node2children[parent].discard(node)
        if len(node2children[parent]) == 1:
            leaves.append(parent)
    print(score)
    print(" ".join(
        map(
            lambda x: str(x[1]),
            sorted(
                enumerate(c),
                key=lambda x: sequence[x[0]]
            )
        )
    ))
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Solution (Python):
N=int(input())
edge=[list(map(int,input().split())) for i in range(N-1)]
C=list(map(int, input().split()))
from heapq import heapify,heappop
for i in range(N):
    C[i]=-C[i]
heapify(C)
c=[[] for i in range(N)]
for i,j in edge:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
d=[-1]*N
d[0]=-heappop(C)
v=[0]*N
v[0]=1
SUM=d[0]
import sys
sys.setrecursionlimit(10**5)
def dfs(p,v,d):
    global SUM
    for n in c[p]:
        if v[n]==0:
            d[n]=-heappop(C)
            SUM+=d[n]
            v[n]=1
            dfs(n,v,d)
dfs(0,v,d)
print(SUM-d[0])
for i in range(N-1):
    print(d[i],end=' ')
print(d[N-1])

Solution (Python):

from operator import itemgetter
from heapq import heappop, heappush
def solve(): 
    N = int(input())
    E = [[] for i in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        E[a].append(b)
        E[b].append(a)
    C = list(map(int, input().split()))
    C.sort(reverse=True)
    D = ['' for i in range(N+1)]
    j = 1
    hq = [(0,1)]
    checked = []
    while hq:
        _j ,n = heappop(hq)
        checked.append(n)
        D[n] = str(C[_j])
        for m in E[n]:
            if not m in checked:
                heappush(hq, (j, m))
                j += 1
    res = str(sum(C[1:])) + '\n' +' '.join(D[1:])
    return str(res)

if __name__ == '__main__':
    print(solve())

Solution (Python):
import numpy as np
from collections import defaultdict
from functools import reduce
import queue


n = int(input())

edges = defaultdict(set)

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

q = queue.Queue()

for node, li in edges.items():
    if len(li) == 1:
        q.put(node)

C = sorted(list(map(int, input().split())))
c_idx = 0

res = np.zeros(n, dtype=int)

while not q.empty():
    node = q.get()
    if res[node] != 0:
        continue
    res[node] = C[c_idx]
    c_idx += 1

    if len(edges[node]) > 0:
        n2 = edges[node].pop()
        edges[n2].remove(node)
        if len(edges[n2]) == 1:
            q.put(n2)

print(sum(C[:n-1]))
print(*res)

Solution (Python):




from collections import deque
 
N = int(input())
 
edges = [[] for _ in range(N)]
 
for i in range(N-1):
    u, v = map(int, input().rstrip().split(' '))
    u = u - 1
    v = v - 1
    
    edges[u].append(v)
    edges[v].append(u)
    
X = sorted(list(map(int, input().rstrip().split(' '))), key=lambda x: -x)

temp = deque([0])
 
vertices = [-1] * N
count_vertices = 0
value = 0
while len(temp) > 0:
    a = temp.popleft()
    vertices[a] = X[count_vertices]
    count_vertices += 1
    
    for edge in edges[a]:
        if vertices[edge] == -1:
            temp.append(edge)
 
print(sum(X[1:]))
print(' '.join(list(map(str, vertices))))

Solution (Python):
N=int(input())
from collections import defaultdict,deque
B=[tuple(map(int,input().split())) for i in range(N-1)]
branch=defaultdict(set)
for a,b in B:
    branch[a-1]|={b-1}
    branch[b-1]|={a-1}
C=list(map(int,input().split()))
cnt=[len(branch[i]) for i in range(N)]
M=0
start=-1
for i in range(N):
    if M<len(branch[i]):
        M=len(branch[i])
        start=i
C.sort(reverse=True)
idx=0
ans=[0]*N
check=deque([start])
while len(check)>0:
    now=check.popleft()
    ans[now]=C[idx]
    idx+=1
    nex=[(i,len(branch[i])) for i in branch[now] if ans[i]==0]
    nex.sort(key=lambda x:x[1],reverse=True)
    check+=deque([i[0] for i in nex])
res=0
for a,b in B:
    res+=min(ans[a-1],ans[b-1])
print(res)
print(" ".join(list(map(str,ans))))

Solution (Python):

import sys



def solve(N: int, a: "List[int]", b: "List[int]", C: "List[int]"):
    conn = [[] for _ in range(N)]
    for i in range(N - 1):
        conn[a[i] - 1].append(b[i] - 1)
        conn[b[i] - 1].append(a[i] - 1)
    
    counts = [[] for _ in range(N)]
    for i in range(N):
        l = len(conn[i])
        
        counts[i] = [len(conn[i]), conn[i], 0, i]
    

    ret = 0
    
    C.sort()
    idx = 0
    while idx < N:
        for cnt in counts:
            if cnt[2] == 0 and cnt[0] <= 1:
                cnt[2] = C[idx]
                idx += 1
                for node in cnt[1]:
                    counts[node][0] -= 1
            
    vals = [0] * N
    for cnt in counts:
        vals[cnt[3]] = cnt[2]
    for i in range(N - 1):
        ret += min(vals[a[i] - 1], vals[b[i] - 1])
    print(ret)
    print(' '.join([str(v) for v in vals]))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int()] * (N-1)  
    b = [int()] * (N-1)  
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    c = [ int(next(tokens)) for _ in range(N) ]  
    solve(N, a, b, c)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
N=int(input())
A=[0 for i in range(N-1)]
B=[0 for i in range(N-1)]
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    A[i],B[i]=a,b
    G[a].append(b)
    G[b].append(a)
j=0
for i in range(N):
    if len(G[i])>len(G[j]):
        j=i
c=sorted([int(i) for i in input().split()])
d=[-1 for i in range(N)]
q=deque([j])
while(len(q)>0):
    r=q.popleft()
    d[r]=c.pop()
    for p in G[r]:
        if d[p]==-1:
            q.append(p)
M=0
for i in range(N-1):
    M+=min(d[A[i]],d[B[i]])
print(M)
print(" ".join([str(i) for i in d]))

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

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


n = ni()
edges = [tuple(li_()) for _ in range(n-1)]
c = list(li())
c.sort()

visited = [False]*n

graph = [[] for _ in range(n)]
for l, r in edges:
    graph[l].append(r)
    graph[r].append(l)

cnt = 0
num = [0]*n

def dfs(node, graph):
    global cnt
    visited[node] = True
    for nei in graph[node]:
        if not visited[nei]:
            dfs(nei, graph)

    num[node] = c[cnt]
    cnt += 1

dfs(0, graph)

ans = 0
for l, r in edges:
    ans += min(num[l], num[r])

print(ans)
print(*num)

Solution (Python):
from collections import deque
from heapq import heapify, heappop

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

start = None
for i in range(n):
    if len(edge[i]) == 1:
        start = i
        break

visited = [0]*n
q = deque()
q.append((start))
while q:
    now = q.pop()
    if visited[now]:
        continue
    a = heappop(cc)
    visited[now] = -a
    for i in edge[now]:
        if not visited[i]:
            q.append(i)
print(sum(c) - max(c))
print(*visited)

Solution (Python):
import sys
sys.setrecursionlimit(2000000)

N = int(input())
ab = list(list(map(int,input().split())) for i in range(N-1))
c = list(map(int,input().split()))
c.sort(reverse=True)
print(sum(c)-c[0])
tree = [[-1]for i in range(N)]
for a,b in ab:
    tree[a-1].append(b)
    tree[b-1].append(a)
def func(l):
    if tree[l-1][0] != -1:
        return
    tree[l-1][0] = c.pop(0)
    for i in tree[l-1][1:]:
        func(i)
func(1)
for i in tree:
    print(i[0],end = " ")

Solution (Python):
N = int(input())
ab = []
abn = [0]*N
abw = [[] for _ in range(N)]
for i in range(N-1):
  a,b = list(map(int,input().split()))
  ab.append([a,b])
  abw[a-1].append(b)
  abw[b-1].append(a)
  abn[a-1] += 1
  abn[b-1] += 1
c = sorted(list(map(int,input().split())))
cn = 0
d = [0]*N
s = [i for i in range(N)]
while cn <N:
  cut = []
  for i in s:
    if (abn[i] == 1 and cn<N) or len(s) == 1:
      d[i] = c[cn]
      cn += 1
      cut.append(i)
      abn[i] -=1
      s.remove(i)
  for j in cut:
    for k in abw[j]:
      abn[k-1] -= 1
print(sum(c)-max(c))
print(" ".join(map(str,d)))

Solution (Python):





N = int(input())
score = 0

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

C = [int(x) for x in input().split()]
deg = [len(x) for x in edge]


deg_1 = [i for i,x in enumerate(deg) if x == 1]

D = [None]*(N+1)
C.sort(reverse = True)
M = sum(C) - C[0] 
  
while deg_1:
  v = deg_1.pop()
  if not deg_1:
    D[v] = C.pop()
    break
  w = edge[v].pop()
  edge[w].remove(v)
  deg[w] -= 1
  if deg[w] == 1:
    deg_1.append(w)
  D[v] = C.pop()

  
print(M)
print(' '.join(map(str,D[1:])))

Solution (Python):
def sol(_inp=input):
    n=int(_inp())
    tree={i+1:set() for i in range(n)}
    assigned=[0 for _ in range(n)]
    for _ in range(n-1):
        i,j=map(int,_inp().split())
        tree[i].add(j)
        tree[j].add(i)
    cs=sorted(list(map(int,_inp().split())))
    tree_orig={i:tree[i].copy() for i in tree}
    for c in cs[:-1]:
        for v in tree:
            if len(tree[v])==1:
                assigned[v-1]=c
                w=list(tree[v])[0]
                tree[v]=set()
                tree[w].remove(v)
                break
    else:
        assigned[w-1]=cs[-1]
    res=sum(min(assigned[v-1],assigned[w-1]) for v in tree_orig for w in tree_orig[v])//2
    return '{}\n{}'.format(res,' '.join(str(c) for c in assigned))
print(sol())

Solution (Python):

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')


def A():
    n = II()
    print((n-2)*180)
    return


def B():
    b = S()
    kati = b.count("o")
    kati += 15 - len(b)
    if kati >= 8:
        print("YES")
    else:
        print("NO")
    return


def C():
    return


def D():
    n = II()
    ab = LIR_(n-1)
    C = LI()
    C.sort(reverse=True)
    c = deque()
    for ci in C:
        c.appendleft(ci)
    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()

    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


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == '__main__':
    D()

Solution (Python):

from collections import defaultdict

from math import factorial

def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))


def main():
    num = int(input())

    parent_dic = [-1 for i in range(num)]
    now_dic = defaultdict(set)
    data_dic = []

    for i in range(num - 1):
        a, b = map(int, input().split())
        now_dic[a].add(b)
        now_dic[b].add(a)
        data_dic.append([a, b])

    ans_omomi = [-1 for i in range(num + 1)]

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

    

    now_data = set()
    now_data.add(1)
    next_data = set()

    count = 0
    ans_omomi[1] = omomi_data[count]

    count += 1



    while len(now_data) > 0:
        for ele_pare in now_data:
            for ele in now_dic[ele_pare]:
                if ans_omomi[ele] != -1:
                    continue
                ans_omomi[ele] = omomi_data[count]
                count += 1
                next_data.add(ele)
        now_data = next_data
        next_data = set()

    
    


    final_omomi = 0
    for i in range(num - 1):
        kari = min(ans_omomi[data_dic[i][0]], ans_omomi[data_dic[i][1]])
        final_omomi += kari
    print(final_omomi)
    print(' '.join(list(map(str, ans_omomi[1:]))))


if __name__ == '__main__':
    main()

Solution (Python):
import queue

N = int(input())
edge = [set([]) for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].add(b)
    edge[b].add(a)
c = list(map(int, input().split()))
c.sort()
q = queue.Queue()
for i in range(N):
    if len(edge[i]) == 1:
        q.put(i)
ans = [0] * N
i = 0
while not q.empty():
    j = q.get()
    ans[j] = c[i]
    i += 1
    if len(edge[j]) == 0:
        continue
    k = list(edge[j])[0]
    edge[k].remove(j)
    if len(edge[k]) == 1:
        q.put(k)
print(sum(c[:-1]))
for i in ans:
    print(i, end = " ")
print()

Solution (Python):
from collections import deque


n = int(input())
info = [list(map(int, input().split())) for i in range(n-1)]
c = list(map(int, input().split()))
c = sorted(c, reverse = True)
tree = [[] for i in range(n)]

for i in range(n-1):
    tree[info[i][0] - 1].append(info[i][1]-1)
    tree[info[i][1] - 1].append(info[i][0]-1)

for i in range(n):
    if len(tree[i]) == 1:
        leaf = i
        break

q = deque([])
q.append([-1, leaf])
visited = [False]*n
visited[leaf] = True
max_ans = 0
ans = [0]*n
j = 0

while q:
    prev_pos, now_pos = q.pop()
    ans[now_pos] = c[j]
    j += 1
    if prev_pos != -1:
        max_ans += min(ans[prev_pos], ans[now_pos])
    for i in tree[now_pos]:
        if not visited[i]:
            visited[i] = True
            q.append([now_pos, i])
print(max_ans)

for i in range(n-1):
    print(str(ans[i]) + " ", end="")
print(ans[n-1], end="")
print()

Solution (Python):
from collections import deque

n = int(input())
nums = [-1 for _ in range(n)]
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = list(map(lambda x: int(x) - 1, input().split()))
    edges[a].append(b)
    edges[b].append(a)

cs = sorted(list(map(int, input().split())), reverse=True)
cost = sum(cs[1:])
cs = deque(cs)

start = -1
for i, e in enumerate(edges):
    if len(e) == 1:
        start = i
        break

q = deque([start])
while len(q) > 0:
    p = q.popleft()
    c = cs.popleft()
    nums[p] = c
    for np in edges[p]:
        if nums[np] == -1:
            q.append(np)

print(cost)
print(' '.join(map(str, nums)))

Solution (Python):
n=int(input())
pair={}
nodes=[0]*n
for _ in range(n-1):
    a,b=map(int,input().split())
    pair.setdefault(a, [])
    pair.setdefault(b, [])
    pair[a]+=[b]
    pair[b] += [a]
c=list(map(int,input().split()))
c.sort()
kei=sum(c[:-1])
cnt=0
nodes[0]=c.pop()
tugi=pair[1]
while c:
    ntugi=[]
    for i in tugi:
        nodes[i-1]=c.pop()
        for ii in pair[i]:
            if nodes[ii-1]>0:continue
            ntugi+=[ii]
    tugi=ntugi
print(kei)
print(*nodes)

Solution (Python):
import numpy as np

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

C = np.fromiter(map(int, input().split()), np.int)
C = np.sort(C)[::-1]

Z = [-1] * N

stack = [0]
index = 0
while stack:
	v = stack.pop()
	if Z[v] >= 0:
		continue
	Z[v] = C[index]
	index += 1
	stack.extend(E[v])

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

Solution (Python):
from collections import defaultdict, deque

N = int(input())
abList = [list(map(int, input().split())) for _ in range(N-1)]
cList = sorted(list(map(int, input().split())), reverse=True)

dd = defaultdict(list)
for ab in abList:
    a, b = ab
    dd[a].append(b)
    dd[b].append(a)

nodeDict = defaultdict(int)
treeQ = deque()
nodeDict[1] = cList[0]
treeQ.append(1)
ci = 1
while(treeQ):
    node = treeQ.popleft()
    for nextNode in dd[node]:
        if not nodeDict[nextNode]:
            treeQ.append(nextNode)
            nodeDict[nextNode] = cList[ci]
            ci += 1

ans1 = sum(cList[1:])
ans2 = ""
for node in nodeDict:
    ans2 += str(nodeDict[node]) + " "

print(ans1)
print(ans2)

Solution (Python):
from collections import defaultdict
n = int(input())
connected_nodes = defaultdict(lambda: {})

for _ in range(n-1):
  a, b = map(int, input().split())
  if a > b:
    a, b = b, a
  connected_nodes[a-1][b-1] = True
  connected_nodes[b-1][a-1] = True

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

if n == 1:
  print(0)
  print(1)
  exit(0)
if n == 2:
  print(min(edges[0]))
  print('1 2')
  exit(0)



cs = sorted(cs)
answer_sum = sum(cs) - cs[-1]

visiting = [0]
number_map = {}
number_map[0] = cs.pop()

while True:
  if len(number_map.keys()) == n:
    break
  node = visiting.pop()
  
  
  to_search = list(connected_nodes[node].keys())
  for neighbor in to_search:
    if neighbor in number_map:
      continue
    
    number_map[neighbor] = cs.pop()
    connected_nodes[node].pop(neighbor)
    connected_nodes[neighbor].pop(node)
    visiting.append(neighbor)


print(answer_sum)
print(' '.join([str(number_map[k]) for k in sorted(number_map.keys())]))

Solution (Python):
import sys
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


N = int_raw()
tree = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = ints_raw()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

Cs = list(ints_raw())
Cs.sort(reverse=True)
ans_node = [-1]*N
def main():
    max_deg_idx = 0
    max_deg = len(tree[0])
    for idx in range(N):
        if max_deg < len(tree[idx]):
            max_deg = len(tree[idx])
            max_deg_idx = idx
    cur_node_idx = max_deg_idx
    neighbour = []
    ans_node[cur_node_idx] = Cs[0]
    ans = 0
    for c in Cs[1:]:    
        for a in tree[cur_node_idx]:
            if ans_node[a]==-1:
                heappush(neighbour,[-len(tree[a]),a])
        cur_node_idx = heappop(neighbour)[1]
        ans_node[cur_node_idx] = c
        ans += c
    print (ans)
    print (*ans_node,sep=" ")


main()

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

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

c = list(map(int,input().split()))
c.sort()
c = c[::-1]
max = c[0]
ans = [0 for i in range(N)]

d = [-1 for i in range(N)]
d[0] = 0
ans[0] = c.pop(0)
q = deque([0 * (N - 1)])
while len(q) > 0:
    u = q.popleft()
    for v in edge[u]:
        if d[v] > -1:
            continue
        d[v] = d[u] + 1
        ans[v] = c.pop(0)
        q.append(v)

print(sum(ans) - max)
print(*ans, sep=" ")

Solution (Python):
def li():
    return list(map(int, input().split()))


if __name__ == "__main__":
    n = int(input())
    edge_list = [li() for _ in range(n - 1)]
    c_list = li()

    tree_dict = {}
    for edge in edge_list:
        if edge[0] not in tree_dict:
            tree_dict[edge[0]] = [edge[1]]
        else:
            tree_dict[edge[0]].append(edge[1])
        if edge[1] not in tree_dict:
            tree_dict[edge[1]] = [edge[0]]
        else:
            tree_dict[edge[1]].append(edge[0])

    dim1_list = []
    for key, value in tree_dict.items():
        if len(value) == 1:
            dim1_list.append(key)

    c_list.sort()

    score = sum(c_list) - c_list[-1]
    cost_dict = {}
    
    
    
    
    for c in c_list[:-1]:
        node = dim1_list.pop()
        cost_dict[node] = c
        connected = tree_dict[node][0]
        tree_dict[connected].remove(node)
        if len(tree_dict[connected]) == 1:
            dim1_list.append(connected)
    node = dim1_list.pop()
    cost_dict[node] = c_list[-1]

    print(score)
    for i in range(1, n):
        print(cost_dict[i], end=" ")
    print(cost_dict[n])