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: # m-solutions2019D - Maximum Sum of Minimum
  def bfs(start: int) -> None:
      q = [start]
      nodes[start] = C.pop()
      while q:
          v = q.pop(0)
          for u in T[v]:
              if not nodes[u]:
                  nodes[u] = C.pop()
                  q.append(u)
  
  
  def main():
      # adjacent edges should have close numbers as much as possible -> sort, bfs
      global T, C, nodes
      N, *ABC = map(int, open(0).read().split())
      AB, C = ABC[:-N], ABC[-N:]
      C.sort()
      T = [[] for _ in range(N + 1)]
      for v, u in zip(*[iter(AB)] * 2):
          T[v].append(u), T[u].append(v)
      score, nodes = sum(C) - C[-1], [0] * (N + 1)  # max of C will not be used
      for i, t in enumerate(T[1:], 1):
          if len(t) == 1:
              start = i  # start from any node with degree 1
              break
      bfs(start)
      print(score)
      print(*nodes[1:])
  
  
  if __name__ == "__main__":
      main()
  
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."}]