Problem:
 Score : 500 points    Problem 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.      Constraints  1 \leq N \leq 10000  1 \leq a_i,b_i \leq N  1 \leq c_i \leq 10^5  The given graph is a tree.         Input 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       Output 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.        Sample Input 1 5
1 2
2 3
3 4
4 5
1 2 3 4 5      Sample Output 1 10
1 2 3 4 5  If we write 1,2,3,4,5 on Vertex 1,2,3,4,5 , respectively, the integers written on the four edges will be 1,2,3,4 , for the score of 10 . This is the maximum possible score.       Sample Input 2 5
1 2
1 3
1 4
1 5
3141 59 26 53 59      Sample Output 2 197
59 26 3141 59 53  c_1,c_2,\ldots,c_N may not be pairwise distinct.

Solution (Python):
n=int(input())
ab=[list(map(int,input().split())) for i in range(n-1)]
c=list(map(int,input().split()))
c.sort(reverse=True)
l=[[] for i in range(n+1)]
ans=[0 for i in range(n+1)]
ans[1]=c[0]
q=[1]
ci=1
for a,b in ab:
    l[a].append(b)
    l[b].append(a)
while(len(q)>0):
    t=q.pop()
    tl=l[t]
    for i in tl:
        if(ans[i]==0):
            ans[i]=c[ci]
            ci+=1
            q.append(i)
print(sum(c[1:]))
print(" ".join(map(str,ans[1:])))

Solution (Python):
from sys import exit, setrecursionlimit, stderr, stdin
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect
import functools

setrecursionlimit(10**7)

def input():
  return stdin.readline().strip()

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
edges = [set() for _ in range(N)]
for _ in range(N-1):
  a, b = reads()
  a, b = a-1, b-1
  edges[a].add(b)
  edges[b].add(a)
c = reads()
c.sort()

M = sum(c[:-1])
visited = [False] * N
idx = 0

result = [0] * N

def dfs(x):
  global idx
  for y in edges[x]:
    edges[y].remove(x)
    dfs(y)
  result[x] = c[idx]
  idx += 1

dfs(0)

print(M)
print(" ".join(str(x) for x in result))

Solution (Python):
from heapq import heappush, heappop

N = int(input())
a, b = (
    zip(*(map(int, input().split()) for _ in range(N - 1))) if N - 1 else
    ((), ())
)
c = list(map(int, input().split()))

INF = 10**10
G = [{} for _ in range(N + 1)]
for x, y in zip(a, b):
    G[x][y] = 1
    G[y][x] = 1


def dijkstra(G, s):
    dp = [INF for _ in range(len(G))]
    q = []
    heappush(q, (0, s))
    while q:
        c, i = heappop(q)
        if dp[i] == INF:
            dp[i] = c
            for j, w in G[i].items():
                heappush(q, (c + w, j))
    return dp


dp = dijkstra(G, 1)
dp2 = dict()

for x, (_, z) in zip(
    sorted(c), sorted(zip(dp[1:], range(1, N + 1)), reverse=True)
):
    dp2[z] = x

ans = 0
for x, y in zip(a, b):
    ans += min(dp2[x], dp2[y])
print(ans)
ans2 = ' '.join(
    str(dp2[i])
    for i in range(1, N + 1)
)
print(ans2)

Solution (Python):
N = int(input())
g = {i: [] for i in range(N)}
for i in range(N - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
c = list(map(int, input().split()))
c.sort()
print(sum(c[:-1]))
nums = [0] * N
stack = [0]
while stack:
    d = stack.pop()
    nums[d] = c.pop()
    for node in g[d]:
        if nums[node] == 0:
            stack.append(node)
print(' '.join(map(str, nums)))

Solution (Python):
N=int(input())
A=[[] for i in range(N+1)]
B=[0 for i in range(N+1)]
for i in range(N-1):
    a,b=[int(x) for x in input().split()]
    A[a].append(b)
    A[b].append(a)
    B[a]+=1
    B[b]+=1
C=sorted( [int(x) for x in input().split()] )
D=[-1 for i in range(N+1)]
M=sum(C) - C[-1]
isEnd=[]
for i in range(1,N+1):
    if B[i]==1:
        isEnd.append(i)

for c in C:
    d=isEnd.pop()
    D[d]=c
    B[d]=0
    
    for k in A[d]:
        A[k].remove(d)
        B[k]-=1
        if B[k]==1:
            isEnd.append(k)
print (M)
print (' '.join([str(x) for x in D[1:]]) )

Solution (Python):
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
c = list(map(int, input().split()))

R = {}
for a, b in ab:
  if a - 1 in R:
    R[a - 1].append(b - 1)
  else:
    R[a - 1] = [b - 1]
  if b - 1 in R:
    R[b - 1].append(a - 1)
  else:
    R[b - 1] = [a - 1]

L = [0] * N
L[0] = 1
F = []
RL = {}
RL[1] = [0]
RL[2] = []
for i in R[0]:
  F.append(i)
  L[i] = 2
  RL[2].append(i)

k = 2
while F != []:
  k += 1
  Ft = []
  RL[k] = []
  for i in F:
    for j in R[i]:
      if L[j] == 0:
        L[j] = k
        Ft.append(j)
        RL[k].append(j)
  F = Ft

Ans = [0] * N
c.sort()
cnt = 0
for i in range(k - 1, 0, -1):
  for j in RL[i]:
    Ans[j] = c[cnt]
    cnt += 1
print(sum(c) - max(c))
s = str(Ans[0])
for i in range(1, N):
  s += " " + str(Ans[i])
print(s)

Solution (Python):
import sys
sys.setrecursionlimit(100000)

n = int(input())

graph = [[] for i in range(n)]
edge_cnt = [0] * n
for i in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    edge_cnt[a-1] += 1
    edge_cnt[b-1] += 1


c = list(map(int, input().split()))
c.sort()

v = 0
for i in range(n):
    if edge_cnt[i] == 1:
        v = i
        break

nodes = [0] * n
total_score = -c[-1]


def dfs(v):
    global total_score
    if nodes[v] > 0:
        return
    nodes[v] = c.pop()
    total_score += nodes[v]
    for nv in graph[v]:
        if nodes[nv] > 0:
            continue
        dfs(nv)


dfs(v)
print(total_score)
print(*nodes, sep=' ')

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    n = I()
    print(180*(n-2))
    return


def B():
    s = S()
    res = 15-len(s)
    k = s.count("o")
    if k+res >= 8:
        print("YES")
    else:
        print("NO")
    return


def C():
    n,a,b,c = LI()
    return


def D():
    n = I()
    v = [[] for i in range(n)]
    f = [[0,i] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        f[a][0] += 1
        f[b][0] += 1
    f.sort(key = lambda x:-x[0])
    s = f[0][1]
    c = LI()
    c.sort(key = lambda x:-x)
    f[0][0] = c[0]
    q = deque()
    q.append(s)
    bfs = [1 for i in range(n)]
    f.sort(key = lambda x:x[1])
    bfs[s] = 0
    k = 1
    while q:
        x = q.popleft()
        for y in v[x]:
            if bfs[y]:
                bfs[y] = 0
                f[y][0] = c[k]
                k += 1
                q.append(y)
    ans = 0
    q.append(s)
    bfs = [1 for i in range(n)]
    bfs[s] = 0
    while q:
        x = q.popleft()
        for y in v[x]:
            ans += min(f[x][0],f[y][0])
            if bfs[y]:
                bfs[y] = 0
                q.append(y)
    print(ans//2)
    for i, j in f[:-1]:
        print(i,end = " ")
    print(f[-1][0])
    return


def E():
    n = I()
    return


def F():
    n = I()
    return


if __name__ == "__main__":
    D()

Solution (Python):
n = int(input())
ab = [list(map(int,input().split())) for _ in range(n-1)]
c = list(map(int,input().split()))
c = sorted(c)[::-1]
g = {}
for i in range(1,n+1):
    g[i] = []
for a,b in ab:
    g[a].append(b)
    g[b].append(a)
from collections import deque
q = deque([g[1]])
done = [0]*(n+1)
done[1] = 1
ans = [0]*n
ans[0] = c[0]
cnt = 1
while q:
    v = q.popleft()
    for v_ in v:
        if done[v_]==0:
            done[v_] = 1
            ans[v_-1] = c[cnt]
            cnt += 1
            q.append(g[v_])
print(sum(c[1:]))
for i in ans:
    print(i,end=' ')
print()

Solution (Python):
def build_tree(N, edge_list):

    G = dict()
    for i in range(1, N+1):
        G[i] = dict()

    for i in range(N-1):
        a, b = edge_list[i]
        G[a][b] = 1
        G[b][a] = 1

    leaves = []
    for i in range(1, N+1):
        if len(G[i].keys()) == 1:
            leaves.append(i)

    return G, leaves


def pop_leaf_loop(G, leaves, c_list):

    res_list = [""]*N

    for i in range(N):
        leaf = leaves[i]
        res_list[leaf-1] = str(c_list[i])
        for j in G[leaf]:
            del G[j][leaf]
            if len(G[j].keys()) == 1:
                leaves.append(j)

    return res_list


if __name__ == "__main__":
    N = int(input())
    edge_list = [[] for _ in range(N-1)]
    for i in range(N-1):
        edge_list[i] = list(map(int, input().split()))
    c_list = list(sorted(list(map(int, input().split()))))
    G, leaves = build_tree(N, edge_list)
    res_list = pop_leaf_loop(G, leaves, c_list)
    print(sum(c_list) - max(c_list))
    print(" ".join(res_list))

Solution (Python):


import collections


class Node(object):

  def __init__(self):
    self.value = 0
    self.edges = []


def main():
  n = int(input())
  nodes = [Node() for _ in range(n)]

  for _ in range(n - 1):
    a, b = map(int, input().split())
    nodes[a - 1].edges.append(nodes[b - 1])
    nodes[b - 1].edges.append(nodes[a - 1])

  values = list(map(int, input().split()))
  values.sort(reverse=True)

  print(sum(values[1:]))

  queue = collections.deque()
  queue.append(nodes[0])
  index = 0

  while len(queue) != 0:
    node = queue.popleft()
    node.value = values[index]
    index += 1

    queue.extend(n for n in node.edges if n.value == 0)

  print(' '.join(str(n.value) for n in nodes))


if __name__ == '__main__':
  main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)


def main():
    n = I()
    aa = [LI_() for _ in range(n-1)]
    c = sorted(LI(), reverse=True)
    e = collections.defaultdict(set)
    for a,b in aa:
        e[a].add(b)
        e[b].add(a)

    ci = 0
    q = [0]
    v = set([0])
    r = [0] * n
    while q:
        nq = []
        for t in q:
            r[t] = c[ci]
            ci += 1
            for nt in e[t]:
                if nt in v:
                    continue
                v.add(nt)
                nq.append(nt)
        q = nq

    return '{}\n{}'.format(sum(c[1:]), ' '.join(map(str, r)))


print(main())