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: def sol(_inp=input):
      n = int(_inp())
      tree = {i + 1: set() for i in range(n)}
      assigned = [0 for _ in range(n)]
      for _ in range(n - 1):
          i, j = map(int, _inp().split())
          tree[i].add(j)
          tree[j].add(i)
      cs = sorted(list(map(int, _inp().split())))
      tree_orig = {i: tree[i].copy() for i in tree}
      for c in cs[:-1]:
          for v in tree:
              if len(tree[v]) == 1:
                  assigned[v - 1] = c
                  w = list(tree[v])[0]
                  tree[v] = set()
                  tree[w].remove(v)
                  break
      else:
          assigned[w - 1] = cs[-1]
      res = (
          sum(
              min(assigned[v - 1], assigned[w - 1])
              for v in tree_orig
              for w in tree_orig[v]
          )
          // 2
      )
      return "{}\n{}".format(res, " ".join(str(c) for c in assigned))
  
  
  print(sol())
  
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."}]