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):
import heapq
import sys
sys.setrecursionlimit(10**7)
n = int(input())
g = [[] for _ 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 = [-i for i in list(map(int,input().split()))]
heapq.heapify(c)
print(-sum(c)+min(c))

for i in range(n):
    if len(g[i]) == 1:
        start = i
        break

ans = [-1]*n
ans[start] = -heapq.heappop(c)
q = [start]

while q:
    now = q.pop(-1)
    for i in g[now]:
        if ans[i] == -1:
            ans[i] = -heapq.heappop(c)
            q.append(i)

for i in ans:
    print(i)

Solution (Python):
n=int(input())
e=[[]for i in range(n)]
for i in range(n-1):a,b=map(int,input().split());e[a-1].append(b-1);e[b-1].append(a-1)
c,Q,l,i=sorted(list(map(int,input().split())))[::-1],[0],[0]*n,0
print(sum(c[1:]))
while Q:
 a=Q.pop()
 if l[a]!=0:continue
 l[a]=c[i];i+=1
 for j in e[a]:Q.append(j)
print(*l)

Solution (Python):
from collections import deque


def nearlist(N, LIST):  
    NEAR = [set() for _ in range(N)]
    for a, b in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
    return NEAR


def bfs(NEAR, S):  
    ans[S] = c.pop()
    que, frag = deque([S]), set([S])

    while len(que) > 0:
        q = que.popleft()
        for i in NEAR[q]:  
            if i in frag:  
                continue
            ans[i] = c.pop()
            que.append(i), frag.add(i)
    return ans


n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
c = sorted(map(int, input().split()))

ans = [0] * n
near = nearlist(n, ab)
print(sum(c) - max(c))
print(*bfs(near, 0))

Solution (Python):
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))





def main():
    n = ni()
    e = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)
        e[b].append(a)

    c = na()
    c.sort(reverse=True)
    cost = collections.deque(c)

    notvisited = [True for _ in range(n)]
    ans = [-1 for _ in range(n)]

    que = collections.deque(e[0])
    notvisited[0] = False
    ans[0] = cost.popleft()

    while que:
        for _ in range(len(que)):
            q = que.popleft()
            if notvisited[q]:
                ans[q] = cost.popleft()
                notvisited[q] = False
                for ei in e[q]:
                    que.append(ei)

    res = 0
    for i in range(n):
        for ei in e[i]:
            if i < ei:
                res += min(ans[i], ans[ei])

    print(res)
    print(*ans, sep=" ")


if __name__ == '__main__':
    main()

Solution (Python):
class Tree():
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - indexed].append(e[1] - indexed)
            self.tree[e[1] - indexed].append(e[0] - indexed)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        self.size = [1 for _ in range(self.n)]
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)
        for node in self.order[::-1]:
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                self.size[node] += self.size[adj]

import sys
input = sys.stdin.readline

N = int(input())
E = [tuple(map(int, input().split())) for _ in range(N - 1)]

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

res = [None for _ in range(N)]
t = Tree(N, E)
t.setroot(0)

for i in range(N):
    res[t.order[i]] = C[i]

print(sum(C) - max(C))
print(*res)

Solution (Python):
from collections import deque 
n = int(input())
es = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    es[a - 1].append(b - 1)
    es[b - 1].append(a - 1)

c = list(map(int, input().split()))
c.sort()
print(sum(c) - c[-1])

d = [0] * n

q = deque([0])
d[0] = c.pop()

while q:
    v = q.popleft()
    for e in es[v]:
        if d[e]==0:
            d[e] = c.pop()
            q.append(e)
print(*d)

Solution (Python):
from collections import deque

N = int(input())
ki = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ki[a].append(b)
    ki[b].append(a)

c = list(map(int,input().split()))
c.sort()
c.reverse()
point = 1
lis = [0] * N
que = deque([0])
lis[0] = c[0]
while len(que) != 0:
    p = que.popleft()
    
    for i in ki[p]:
        if lis[i] == 0:
            que.append(i)
            lis[i] = c[point]
            point += 1
print(sum(c)-c[0])
print(' '.join(map(str,lis)))

Solution (Python):
import collections
n=int(input())
graph=[]
for i in range(n+1):
  graph.append([])
for i in range(n-1):
  a,b=map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)
c=list(map(int,input().split()))
c.sort()
c.reverse()
ans=['0']*n
pointer=0
queue=collections.deque([[1,1]])
while queue:
  a=queue.popleft()
  ans[a[0]-1]=str(c[pointer])
  for i in graph[a[0]]:
    if i==a[1]:
      continue
    queue.append([i,a[0]])
  pointer+=1
print(sum(c)-c[0])
print(' '.join(ans))

Solution (Python):
N = int(input())

Edge = [[]for _ in range(N)]
Num = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)
for _ in range(N):
    Num[len(Edge[_])].append(_)
C = list(map(int, input().split()))
C.sort()
cnt = 0
Ans = [-1] * N
ans = 0
for i in range(1, N):
    if cnt == N:
        break
    while Num[i]:
        if Num[0]:
            Ans[Num[0][0]] = C[cnt]
            cnt += 1
        x = Num[i].pop()
        if Ans[x] != -1:
            continue
        Ans[x] = C[cnt]
        ans += C[cnt] * i
        cnt += 1
        for y in Edge[x]:
            num = len(Edge[y])
            Num[num-1].append(y)
            Edge[x].remove(y)
            Edge[y].remove(x)

print(ans)
for i, a in enumerate(Ans):
    if i == N-1:
        print(a)
    else:
        print(a, end=' ')

Solution (Python):
from collections import deque

n=int(input())

g=[[] for _ in range(n+1)]

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

c=sorted(list(map(int,input().split())))
print(sum(c[:-1]))

q=deque([1])
visit=[0]*(n+1)
ans=['']*(n+1)

while len(q)>0:
    u=q.popleft()

    visit[u]=1

    ans[u]=str(c.pop())

    for v in g[u]:
        if visit[v]:
            continue

        q.append(v)

print(' '.join(ans[1:]))

Solution (Python):
from collections import defaultdict
import sys


sys.setrecursionlimit(10**6)


def main():
    N = int(input())
    adj = defaultdict(list)
    for _ in range(N - 1):
        a, b = list(map(int, input().split()))
        adj[a - 1].append(b - 1)
        adj[b - 1].append(a - 1)
    C = list(map(int, input().split()))

    
    C.sort(reverse=True)
    ans = [0] * N

    def dfs(node=0, parent=None, c_index=0):
        ans[node] = C[c_index]
        next_c_index = c_index + 1
        for child in adj[node]:
            if child == parent:
                continue
            next_c_index = dfs(child, node, next_c_index)
        return next_c_index

    dfs()
    print(sum(C[1:]))
    print(' '.join(map(str, ans)))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    edges[a].append(b)
    edges[b].append(a)


cost = sorted(map(int, input().split()))
m = 0
ans = [None]*n


def dfs(v, parent):
    ans[v] = cost.pop()
    if parent != -1:
        global m
        m += min(ans[v], ans[parent])
    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v)


dfs(0, -1)
print(m)
print(*ans)

Solution (Python):
from collections import deque
N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)
c = list(map(int, input().split()))
c.sort(reverse=True)
score = sum(c) - max(c)
num = [-1] * N
que = deque()
que.append(0)
i = 0
while que:
    v = que.pop()
    if num[v] != -1:
        continue
    num[v] = c[i]
    i += 1
    for nv in adj[v]:
        que.append(nv)
print(score)
print(*num)

Solution (Python):
from collections import deque
N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)
c = list(map(int, input().split()))
c.sort(reverse=True)
score = sum(c) - max(c)
num = [-1] * N
que = deque()
que.append(0)
i = 0
while que:
    v = que.popleft()
    if num[v] != -1:
        continue
    num[v] = c[i]
    i += 1
    for nv in adj[v]:
        que.append(nv)
print(score)
print(*num)

Solution (Python):





from collections import deque

N = int(input())
graph = [[] for _ in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
mx = 0
st = -1
for i, g in enumerate(graph):
    if len(g)>mx:
        st = i
        mx = len(g)

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


q = deque()
seen = [False]*N
q.append(st)
seen[st] = c[0]
idx = 1
while len(q)>0:
    cur = q.popleft()
    for i in graph[cur]:
        if seen[i]==False:
            seen[i] = c[idx]
            idx += 1
            q.append(i)
print(sum(c[1:]))
print(' '.join(map(str,seen)))

Solution (Python):
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def dfs(L, v, p, D):
    for w in L[v]:
        if w == p:
            continue
        dfs(L, w, v, D)
    D.append(v)


def main():
    N = int(input())
    L = [set() for _ in range(N)]
    for _ in range(N - 1):
        a, b = read_index()
        L[a].add(b)
        L[b].add(a)
    
    C = read_list()
    C.sort()

    D = []
    dfs(L, 0, -1, D)
    E = [""] * N
    for i, d in enumerate(D):
        E[d] = str(C[i])
    
    print(sum(C[: N - 1]))
    print(" ".join(E))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n = int(input())
ns = defaultdict(set)
uvs = [None]*(n-1)
for i in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
    uvs[i] = (u,v)
c = list(map(int, input().split()))
c.sort()
q = [0]
ans = [None]*n
i = 0
def sub(u, prev):
    global i
    for v in ns[u]:
        if prev==v:
            continue
        sub(v, u)
    ans[u] = c[i]
    i += 1
sub(0, -1)
val = 0
for u,v in uvs:
    val += min(ans[u], ans[v])
print(val)
write(" ".join(map(str, ans)))

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
E = [[] for i in range(n)]

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

c = list(map(int, input().split()))
c.sort()
nums = deque(c)
ans = [0] * n
  
def dfs(cur, pre):
    stack = deque([[cur, pre]])
    while stack:
        cur, pre = stack.pop()
        num = nums.pop()
        ans[cur] = str(num)
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur])

dfs(0, -1)

print(sum(c[:-1]))
print(' '.join(ans))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7
res = 0

def resolve():
    def dfs(v, p):
        global res
        c = C.pop(0)
        T[v] = c
        for u in edge[v]:
            if u == p:
                continue
            else:
                res += min(T[v], C[0])
                dfs(u, v)

    n = int(input())
    edge = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(int, input().split())
        edge[a - 1].append(b - 1)
        edge[b - 1].append(a - 1)
    C = list(map(int, input().split()))
    C.sort(reverse=True)

    T = [0] * n
    dfs(0, -1)
    print(res)
    print(*T)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7
res = 0

def resolve():
    def dfs(v, p):
        global res
        c = C.pop(0)
        T[v] = c
        for u in edge[v]:
            if u == p:
                continue
            else:
                res += min(T[v], C[0])
                dfs(u, v)

    n = int(input())
    edge = [[] for _ in range(n)]
    cnt_edge = [0] * n
    for _ in range(n - 1):
        a, b = map(int, input().split())
        edge[a - 1].append(b - 1)
        edge[b - 1].append(a - 1)
        cnt_edge[a - 1] += 1
        cnt_edge[b - 1] += 1
    C = list(map(int, input().split()))
    C.sort(reverse=True)

    start = cnt_edge.index(max(cnt_edge))

    T = [0] * n
    dfs(start, -1)
    print(res)
    print(*T)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def bfs(N, v0, edge, C):

    search = [0] * N
    C = deque(C)
    search[v0] = C.popleft()
    q = deque()
    q.append(v0)

    while q:
        v = q.popleft()
        for nv in edge[v]:
            if search[nv] == 0:
                q.append(nv)
                search[nv] = C.popleft()

    return search


def main():

    N = in_n()
    ab = in_nl2(N - 1)
    edge = [[] for _ in range(N)]

    for i in range(N - 1):
        a, b = ab[i]
        a, b = a - 1, b - 1
        edge[a].append(b)
        edge[b].append(a)

    C = sorted(in_nl(), reverse=True)
    V = bfs(N, 0, edge, C)

    score = 0
    for i in range(N - 1):
        a, b = ab[i]
        a, b = a - 1, b - 1
        score += min(V[a], V[b])

    print(score)
    print(' '.join(map(str, V)))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

n = int(input())
edges = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
clst = list(map(int, input().split()))
clst.sort(reverse = True)
ans = [0 for _ in range(n)]
ind = 0
total = 0
def dfs(pos, b_pos, b_num):
    global ind, total
    ans[pos] = clst[ind]
    total += min(ans[pos], b_num)
    ind += 1
    for n_pos in edges[pos]:
        if n_pos == b_pos:
            continue
        dfs(n_pos, pos, ans[pos])
        
dfs(0, -1, 0)
print(total)
print(*ans)

Solution (Python):
n = int(input())
if n==1:
  c=int(input())
  print(c)
  print(c)
  quit()
line = [list(map(int, input().split())) for i in range(n-1)]
c = list(map(int, input().split()))
c.sort(reverse=True)
print(sum(c)-c[0])
ans=[0]*n
vis=[True]*n
a, b = line[0]
a-=1
b-=1
ans[a]=c[0]
ans[b]=c[1]
vis[a]=False
vis[b]=False
for i in range(1, n-1):
  for l in line:
    a, b = l
    a-=1
    b-=1
    if (vis[a] and (not vis[b])):
      ans[a]=c[i+1]
      vis[a]=False
      break
    elif (vis[b] and (not vis[a])):
      ans[b]=c[i+1]
      vis[b]=False
      break

ans = list(map(str, ans))
print(" ".join(ans))

Solution (Python):
import heapq

n = int(input())

g = [[] for _ 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(lambda x: -int(x), input().split()))
heapq.heapify(c)
print(min(c) - sum(c))

ans = []
s = [-1] * n
leaf = -1
for i, a in enumerate(g):
    if len(a) == 1:
        leaf = i
        break

que = [leaf]
while que:
    t = que.pop()
    for e in g[t]:
        if s[e] == -1:
            s[e] = -heapq.heappop(c)
            que.append(e)

print(*s)

Solution (Python):
n = int(input())
g = [[] * n for i in range(n)]
for i in range(n-1):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  g[u].append(v)
  g[v].append(u)
  
d = list(map(int,input().split()))
d.sort(reverse=True)

from collections import deque
 
que = deque()
que.append(0)
chk = [False]*n
chk[0] = True
ans = [0]*n
ans[0] = d[0]
cnt = 1
while que:
  now = que.popleft()
  if cnt == n:
    break
  for i in g[now]:
    if not chk[i]:
      chk[i] = True
      ans[i] = d[cnt]
      cnt += 1
      que.append(i)
      
print(sum(d[1:]) if n > 1 else 0)
print(*ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N = I()
graph = [[] for i in range(N)]
for _ in range(N-1):
  a,b = IL()
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
q = deque([0])
f = [0 for i in range(N)]
f[0] = 1
ans = []
while q:
  x = q.pop()
  ans.append(x)
  for y in graph[x]:
    if f[y]: continue
    f[y] = 1
    q.append(y)
A = IL()
A.sort(reverse = True)
ANS = [-1 for i in range(N)]
for i in range(N):
  ANS[ans[i]] = A[i]
print(sum(A[1:]))
print(*ANS)

Solution (Python):
import heapq
import sys
from collections import deque


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


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    N = int(input())
    tree = [[] for _ in range(N)]
    edge = deque([])

    for _ in range(N - 1):
        a, b = map(int, input().split())
        tree[a - 1].append(b - 1)
        tree[b - 1].append(a - 1)
        edge.append((a - 1, b - 1))

    C = list(map(int, input().split()))
    C.sort()
    D = []
    for c in C:
        heapq.heappush(D, -c)

    answer = [0] * N
    a, b = edge.popleft()
    c = heapq.heappop(D) * (-1)
    d = heapq.heappop(D) * (-1)
    if len(tree[a]) == 0:
        answer[a] = c
        answer[b] = d
    else:
        answer[a] = d
        answer[b] = c

    new_node = deque([])
    for n in tree[a]:
        new_node.append(n)
    for n in tree[b]:
        new_node.append(n)

    while new_node:
        s = new_node.popleft()
        if answer[s] == 0:
            answer[s] = heapq.heappop(D) * (-1)
        for n in tree[s]:
            if answer[n] == 0:
                new_node.append(n)

    print(sum(C[:-1]))
    print(*answer)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

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

    s = sum(C[1:])
    ans = [None] * N

    
    q = deque([(0, 0)])
    ans[0] = C[0]
    visited = [False] * N
    visited[0] = True
    used = [False] * N
    used[0] = True

    while q:
        c, node = q.popleft()

        for j in edges[node]:
            if visited[j]:
                continue

            for k in range(c + 1, N):
                if used[k]:
                    continue
                else:
                    next_c = k
                    break

            visited[j] = True
            used[next_c] = True
            ans[j] = C[next_c]
            q.append((next_c, j))

    print(s)
    print(*ans, sep=" ")


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

n = int(input())
ed = [[] for _ in range(n)]
al,be = [],[]
for _ in range(n-1):
    a,b = map(int,input().split())
    al.append(a-1)
    be.append(b-1)
    ed[a-1].append(b-1)
    ed[b-1].append(a-1)
    
c = list(map(int,input().split()))
c.sort(reverse = True)

ans = [0]*n

q = deque()
q.append(0)
used = [False]*n
used[0] = True
ans[0] = c[0]
j = 1
 
while q:
    p = q.popleft()
    for i in ed[p]:
        if not used[i]:
            used[i] = True
            ans[i] = c[j]
            j += 1
            q.append(i)
        
sc = 0
for i in range(n-1):
    sc += min(ans[al[i]],ans[be[i]])
    
print(sc)
print(*ans)

Solution (Python):
n=int(input())
ab=[list(map(int,input().split())) for _ in range(n-1)]
c=list(map(int,input().split()))
c.sort()
print(sum(c)-c[-1])
ki=[[] for _ in range(n)]
ki_ji=[[i,0] for i in range(n)]
for a,b in ab:
  a,b=a-1,b-1
  ki[a].append(b)
  ki[b].append(a)
  ki_ji[a][1]+=1
  ki_ji[b][1]+=1


from collections import deque
ki_ji.sort(key=lambda x:x[1])
seen=[0]*n
t=ki_ji[-1]
todo=deque([t[0]])
seen[t[0]]=c.pop()
while todo:
  t=todo.popleft()
  l=ki[t]
  for li in l:
    if seen[li]==0:
      todo.append(li)
      seen[li]=c.pop()
print(' '.join(map(str,seen)))

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    adj=[[]for _ in range(N)]
    for i in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
    c=LI()
    c.sort(reverse=True)    
    
    import queue
    q=queue.Queue()
    q.put(0)
    ans=[0]*N
    ans[0]=c[0]
    now=0
    
    while not q.empty():
        v=q.get()
        for nv in adj[v]:
            if ans[nv]==0:
                now+=1
                ans[nv]=c[now]
                q.put(nv)
                
    S=sum(c)-c[0]
    print(S)
    print(' '.join(map(str, ans)))
        

    

main()

Solution (Python):
from collections import deque

n = int(input())
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
l = sorted(list(map(int,input().split())),reverse=True)
ans = [-1]*n

q = deque([])
q.append(0)
ans[0] = l[0]
now = 1
while q:
    b = q.popleft()
    for nex in e[b]:
        if ans[nex] == -1:
            ans[nex] = l[now]
            now += 1
            q.append(nex)
count = 0
for j in range(n):
    for k in e[j]:
        count += min(ans[j],ans[k])
print(count//2)
print(*ans)

Solution (Python):
from collections import deque

n = int(input())
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    e[a].append(b)
    e[b].append(a)
l = sorted(list(map(int,input().split())),reverse=True)
ans = [-1]*n
for i in range(n):
    if len(e[i]) == 1:
        q = deque([])
        q.append(i)
        ans[i] = l[0]
        now = 1
        while q:
            b = q.popleft()
            for nex in e[b]:
                if ans[nex] == -1:
                    ans[nex] = l[now]
                    now += 1
                    q.append(nex)
        count = 0
        for j in range(n):
            for k in e[j]:
                count += min(ans[j],ans[k])
        print(count//2)
        print(*ans)
        exit()

Solution (Python):
from collections import deque
n = int(input())
ki = [[] for i in range(n)]
d = [0 for i in range(n)]
for i in range(n-1):
    a , b = map(lambda x: int(x)-1,input().split())
    ki[a].append(b)
    ki[b].append(a)
c = list(map(int,input().split()))
c.sort(reverse=True)
c = deque(c)
ans = 0
d[0] = c.popleft()
q = deque()
q.append(0)
while q:
    now = q.popleft()
    for i in ki[now]:
        if d[i] == 0:
            d[i] = c.popleft()
            q.append(i)
            ans += d[i]
print(ans)
print(*d)

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

N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int,input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
C = list(map(int,input().split()))
C.sort(reverse = True)

D = [0] * N

def dfs(x, parent, index):
    D[x] = C[index]
    index += 1
    for u in edges[x]:
        if u != parent:
            index = dfs(u, x, index)
    return index

dfs(0, -1, 0)

print(sum(C[1:]))
print(*D)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N = getN()
query = [getNM() for i in range(N - 1)]
C = getList()
C.sort()
ans1 = sum(C) - max(C)

dist = [[] for i in range(N)]
for i in range(N - 1):
    a, b = query[i]
    dist[a - 1].append(b - 1)
    dist[b - 1].append(a - 1)

sta = 0

for i in range(N):
    if len(dist[i]) == 1:
        sta = i
        break

point = [-1] * N

def dfs(now):
    u = C.pop()
    point[now] = u
    for i in dist[now]:
        if point[i] >= 0:
            continue
        dfs(i)

dfs(sta)

print(ans1)
print(*point)