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,=map(int,input().split())

from collections import deque

def bfs(s):
    seen = [0]*N
    d = [0]*N
    prev = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
          prev[b] = a
    return d, prev

d, prev = bfs(0)
order = list(zip(*sorted(enumerate(d), key=lambda x:x[1])))[0]

dp = [1]*N
for v in order[::-1]:
    if len(G[v])==0:
        dp[v] = 1
    dp[prev[v]] += dp[v]
    
sizes=[0]*N
for i in range(N):
  if i == 0:
    tmp = max([dp[v] for v in G[i]])
    sizes[i]=tmp
    continue
  tmp = max(dp[i]-1,N-dp[i])
  sizes[i]=tmp
  
MIN=10**20
argmin=-1
for i in range(N):
  if sizes[i]<MIN:
    MIN=sizes[i]
    argmin=i
    
c = sorted(c,reverse=True)
score=[0]*N
score[argmin]=c[0]

def bfs2(s):
    i = 1
    seen = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          score[b] = c[i]
          i += 1
    return 
  
bfs2(argmin)

ans=0
for i in range(N):
  for j in G[i]:
    if i>j:continue
    ans += min(score[i],score[j])
    
print(ans)
print(*score) N=int(input()) N int(input()) int input() input [] for _ in range(N) for _ in range(N) _ range(N) range N for _ in range(N) [] G=[[] for _ in range(N)] 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)
   i range(N-1) range N-1 N 1 a,b=map(int,input().split()) a map(int,input().split()) map int input().split() ().split () input split b G[a-1].append(b-1) [a-1].append [a-1] G a-1 a 1 append b-1 b 1 G[b-1].append(a-1) [b-1].append [b-1] G b-1 b 1 append a-1 a 1 *c,=map(int,input().split()) *c c map(int,input().split()) map int input().split() ().split () input split from collections import deque def bfs(s):
    seen = [0]*N
    d = [0]*N
    prev = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
          prev[b] = a
    return d, prev bfs seen = [0]*N seen [0]*N [0] 0 N d = [0]*N d [0]*N [0] 0 N prev = [0]*N prev [0]*N [0] 0 N todo = deque() todo deque() deque seen[s]=1 seen[s] seen s 1 todo.append(s) todo.append todo append s while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
          prev[b] = a
     len(todo) len todo a = todo.popleft() a todo.popleft() todo.popleft todo popleft for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
          prev[b] = a
     b G[a] G a if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
          prev[b] = a
     seen[b] == 0 seen[b] seen b 0 seen[b] = 1 seen[b] seen b 1 todo.append(b) todo.append todo append b d[b] += d[a] + 1 d[b] d b d[a] + 1 d[a] d a 1 prev[b] = a prev[b] prev b a return d, prev return d, prev d prev s s d, prev = bfs(0) d bfs(0) bfs 0 prev order = list(zip(*sorted(enumerate(d), key=lambda x:x[1])))[0] order list(zip(*sorted(enumerate(d), key=lambda x:x[1])))[0] (zip(*sorted(enumerate(d), key=lambda x:x[1]))) list zip(*sorted(enumerate(d), key=lambda x:x[1])) zip *sorted(enumerate(d), key=lambda x:x[1]) sorted(enumerate(d), key=lambda x:x[1]) sorted enumerate(d) enumerate d key=lambda x:x[1] key lambda x:x[1] x[1] x 1 x 0 dp = [1]*N dp [1]*N [1] 1 N for v in order[::-1]:
    if len(G[v])==0:
        dp[v] = 1
    dp[prev[v]] += dp[v]
     v order[::-1] order ::-1 -1 if len(G[v])==0:
        dp[v] = 1
     len(G[v])==0 len(G[v]) len G[v] G v 0 dp[v] = 1 dp[v] dp v 1 dp[prev[v]] += dp[v] dp[prev[v]] dp prev[v] prev v dp[v] dp v sizes=[0]*N sizes [0]*N [0] 0 N for i in range(N):
  if i == 0:
    tmp = max([dp[v] for v in G[i]])
    sizes[i]=tmp
    continue
  tmp = max(dp[i]-1,N-dp[i])
  sizes[i]=tmp
   i range(N) range N if i == 0:
    tmp = max([dp[v] for v in G[i]])
    sizes[i]=tmp
    continue
   i == 0 i 0 dp[v] for v in G[i] for v in G[i] v G[i] G i for v in G[i] dp[v] dp v tmp = max([dp[v] for v in G[i]]) tmp max([dp[v] for v in G[i]]) max [dp[v] for v in G[i]] sizes[i]=tmp sizes[i] sizes i tmp continue tmp = max(dp[i]-1,N-dp[i]) tmp max(dp[i]-1,N-dp[i]) max dp[i]-1 dp[i] dp i 1 N-dp[i] N dp[i] dp i sizes[i]=tmp sizes[i] sizes i tmp MIN=10**20 MIN 10**20 10 20 argmin=-1 argmin -1 for i in range(N):
  if sizes[i]<MIN:
    MIN=sizes[i]
    argmin=i
     i range(N) range N if sizes[i]<MIN:
    MIN=sizes[i]
    argmin=i
     sizes[i]<MIN sizes[i] sizes i MIN MIN=sizes[i] MIN sizes[i] sizes i argmin=i argmin i c = sorted(c,reverse=True) c sorted(c,reverse=True) sorted c reverse=True reverse True score=[0]*N score [0]*N [0] 0 N score[argmin]=c[0] score[argmin] score argmin c[0] c 0 def bfs2(s):
    i = 1
    seen = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          score[b] = c[i]
          i += 1
    return 
   bfs2 i = 1 i 1 seen = [0]*N seen [0]*N [0] 0 N todo = deque() todo deque() deque seen[s]=1 seen[s] seen s 1 todo.append(s) todo.append todo append s while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          score[b] = c[i]
          i += 1
     len(todo) len todo a = todo.popleft() a todo.popleft() todo.popleft todo popleft for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          score[b] = c[i]
          i += 1
     b G[a] G a if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          score[b] = c[i]
          i += 1
     seen[b] == 0 seen[b] seen b 0 seen[b] = 1 seen[b] seen b 1 todo.append(b) todo.append todo append b score[b] = c[i] score[b] score b c[i] c i i += 1 i 1 return s s bfs2(argmin) bfs2 argmin ans=0 ans 0 for i in range(N):
  for j in G[i]:
    if i>j:continue
    ans += min(score[i],score[j])
     i range(N) range N for j in G[i]:
    if i>j:continue
    ans += min(score[i],score[j])
     j G[i] G i if i>j:continue
     i>j i j ans += min(score[i],score[j]) ans min(score[i],score[j]) min score[i] score i score[j] score j print(ans) print ans print(*score) print *score score G=[[] for _ in range(N)] [[] for _ in range(N)] G d, prev = bfs(0) bfs(0) d MIN=10**20 10**20 MIN argmin=i i argmin N=int(input()) int(input()) N ans=0 0 ans ans += min(score[i],score[j]) min(score[i],score[j]) ans c = sorted(c,reverse=True) sorted(c,reverse=True) c prev = bfs(0) bfs(0) prev tmp = max(dp[i]-1,N-dp[i]) max(dp[i]-1,N-dp[i]) tmp argmin=-1 -1 argmin MIN=sizes[i] sizes[i] MIN order = list(zip(*sorted(enumerate(d), key=lambda x:x[1])))[0] list(zip(*sorted(enumerate(d), key=lambda x:x[1])))[0] order tmp = max([dp[v] for v in G[i]]) max([dp[v] for v in G[i]]) tmp def bfs2(s):
    i = 1
    seen = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          score[b] = c[i]
          i += 1
    return 
   def bfs2(s):
    i = 1
    seen = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          score[b] = c[i]
          i += 1
    return 
   bfs2 def bfs(s):
    seen = [0]*N
    d = [0]*N
    prev = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
          prev[b] = a
    return d, prev def bfs(s):
    seen = [0]*N
    d = [0]*N
    prev = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
          prev[b] = a
    return d, prev bfs score=[0]*N [0]*N score a,b=map(int,input().split()) map(int,input().split()) a b=map(int,input().split()) map(int,input().split()) b dp = [1]*N [1]*N dp sizes=[0]*N [0]*N sizes
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,=map(int,input().split())

from collections import deque

def bfs(s):
    seen = [0]*N
    d = [0]*N
    prev = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
          prev[b] = a
    return d, prev

d, prev = bfs(0)
order = list(zip(*sorted(enumerate(d), key=lambda x:x[1])))[0]

dp = [1]*N
for v in order[::-1]:
    if len(G[v])==0:
        dp[v] = 1
    dp[prev[v]] += dp[v]
    
sizes=[0]*N
for i in range(N):
  if i == 0:
    tmp = max([dp[v] for v in G[i]])
    sizes[i]=tmp
    continue
  tmp = max(dp[i]-1,N-dp[i])
  sizes[i]=tmp
  
MIN=10**20
argmin=-1
for i in range(N):
  if sizes[i]<MIN:
    MIN=sizes[i]
    argmin=i
    
c = sorted(c,reverse=True)
score=[0]*N
score[argmin]=c[0]

def bfs2(s):
    i = 1
    seen = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          score[b] = c[i]
          i += 1
    return 
  
bfs2(argmin)

ans=0
for i in range(N):
  for j in G[i]:
    if i>j:continue
    ans += min(score[i],score[j])
    
print(ans)
print(*score)