M-SOLUTIONS プロコンオープン D - Maximum Sum of Minimum

c を降順ソートすると、c [ i ] を新しく頂点に書き込むとき、スコアが c [ i ] になる回数は高々 i 回で、それまでに一つの辺でスコアを c [ i ] 以上獲得している回数は高々 i - 1 回あるので、求める最大値は sum( c [ 1 : ] ) になります。
そして、その構築方法は c の降順に dfs をして、スタートから i 回目にたどり着いた頂点に c [ i ] を書き込めば実現できます。

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()))
d.sort(reverse=True)

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)
      
print(sum(d[1:]) if n > 1 else 0)
print(*ans)