output_description: 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.
  
  * * *
input_description: 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
attempt: # ナイーブに書く
  N = int(input())
  conn = [[0, 0] for _ in range(N)]  # 加算していくので、list内包表記で定義
  edge = []
  write = [0] * N
  score = [0] * (N - 1)
  
  # edgeの受け取り
  for i in range(N - 1):
      conn[i][0] = i
      a, b = map(int, input().split())
      edge.append((a - 1, b - 1))
      conn[a - 1][1] += 1
      conn[b - 1][1] += 1
  conn[N - 1][0] += N - 1
  
  # 整数の格納、降順ソート
  num = list(map(int, input().split()))
  num.sort(reverse=True)
  
  # 接続数で降順ソート
  conn.sort(key=lambda x: x[1], reverse=True)
  
  # 接続数の多い順に値を格納
  for i, c in enumerate(conn):
      write[c[0]] = num[i]
  
  # スコア計算
  for i, (a, b) in enumerate(edge):
      score[i] = min(write[a], write[b])
  
  # 結果の出力
  print(sum(score))
  print(" ".join([str(i) for i in write]))
  
problem_description: 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.
samples: [{"input": "5\n    1 2\n    2 3\n    3 4\n    4 5\n    1 2 3 4 5", "output": "10\n    1 2 3 4 5\n    \n\nIf we write 1,2,3,4,5 on Vertex 1,2,3,4,5, respectively, the integers written\non the four edges will be 1,2,3,4, for the score of 10. This is the maximum\npossible score.\n\n* * *"}, {"input": "5\n    1 2\n    1 3\n    1 4\n    1 5\n    3141 59 26 53 59", "output": "197\n    59 26 3141 59 53\n    \n\nc_1,c_2,\\ldots,c_N may not be pairwise distinct."}]