Submission #5733494

---

Source Code Expand

# 最小値が端点でないと、隣接とswapして矛盾。
# 最小値は端点としてよい。
# 端点のどれでもよい。
# あとは帰納的に

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]

# degree1の頂点全体
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] # score
  
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:])))

Submission Info

Judge Result