output_description: Print an integer representing the sum of the interior angles of a regular
  polygon with N sides.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
attempt: from collections import deque
  
  
  def bfs(neighbor, start):
      order = [0 for i in range(N)]
      visited = [0 for i in range(N)]
      visited[start] = 1
      q = deque([start])
      num = 1
      while q:
          path = q.popleft()
          order[path] = num
          visited[path] = 1
          num += 1
          for v in neighbor[path]:
              if visited[v] == 1:
                  continue
              q.append(v)
      order = [[i, order[i]] for i in range(len(neighbor))]
      order.sort(key=lambda x: x[1])
      return [order[i][0] for i in range(len(order))]
  
  
  N = int(input())
  node = [[0, i] for i in range(N)]
  ab = []
  neigh = [[0 for i in range(N)] for j in range(N)]
  for i in range(N - 1):
      ai, bi = map(int, input().split())
      node[ai - 1][0] += 1
      node[bi - 1][0] += 1
      neigh[ai - 1][bi - 1] = 1
      neigh[bi - 1][ai - 1] = 1
      ab.append([ai - 1, bi - 1])
  c = list(map(int, input().split()))
  c.sort(reverse=True)
  node.sort(key=lambda x: x[0], reverse=True)
  m = max([node[i][0] for i in range(N)])
  max_node = [node[i][1] for i in range(N) if node[i][0] == m]
  ans1 = 0
  for nn in max_node:
      can = 0
      bbb = bfs(neigh, nn)
      cn = [[c[i], bbb[i]] for i in range(N)]
      # cn.sort(key=lambda x:x[1])
      for i in range(N - 1):
          can += min(cn[ab[i][0]][0], cn[ab[i][1]][0])
      if can > ans1:
          ans1 = can
          ans2 = " ".join([str(cn[i][0]) for i in range(N)])
  
  
  print(ans1)
  
  print(ans2)
  
problem_description: Statement
  
  Given an integer N not less than 3, find the sum of the interior angles of a
  regular polygon with N sides.
  
  Print the answer in degrees, but do not print units.
samples: [{"input": "3", "output": "180\n    \n\nThe sum of the interior angles of a regular triangle is 180 degrees.\n\n* * *"}, {"input": "100", "output": "17640"}]