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 sys
sys.setrecursionlimit(10000000)
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(int,input().split()))
c.sort()
node = [0]*n
used = [False]*n

def dfs(cur,point):
    used[cur] = True
    for nx in G[cur]:
        if used[nx]: continue
        t = c.pop()
        node[nx] = t
        point += min(node[cur],node[nx])
        point = dfs(nx,point)
    return point
node[0] = c.pop()

print(dfs(0,0))
print(*node)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = mapint()
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

Cs = list(mapint())
Cs.sort(reverse=True)
from collections import deque
Q = deque([0])

checked = [0]*N
checked[0] = Cs[0]
cur = 1
ans = 0
while Q:
    v = Q.pop()
    for nx in graph[v]:
        if checked[nx]:
            continue
        checked[nx] = Cs[cur]
        ans += Cs[cur]
        cur += 1
        Q.append(nx)
print(ans)
print(*checked)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = mapint()
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
Cs = list(mapint())
Cs.sort(reverse=True)

from collections import deque
Q = deque([0])
idx = 1
ans = 0
allocation = [-1]*N
allocation[0] = Cs[0]
while Q:
    v = Q.pop()
    for nx in graph[v]:
        if allocation[nx]==-1:
            ans += Cs[idx]
            allocation[nx] = Cs[idx]
            Q.append(nx)
            idx += 1

print(ans)
print(*allocation)

Solution (Python):
import heapq
from collections import deque
n = int(input())
graph = [set() for _ in range(n)]

for _ in range(n - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    graph[a].add(b)
    graph[b].add(a)

nodes = [False for _ in range(n)]
values = list(map(lambda x: -int(x), input().split()))
print(-sum(values) + min(values))

heapq.heapify(values)
next_nodes = deque()
next_nodes.append(0)
while next_nodes:
    node = next_nodes.popleft()
    nodes[node] = -heapq.heappop(values)
    for g in graph[node]:
        if not (nodes[g]):
            next_nodes.append(g)

print(*nodes)

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  


N = I()
Graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b = MI()
    Graph[a].append(b)
    Graph[b].append(a)
C = LI()
C.sort(reverse=True)
print(sum(C[1:]))

ANS = [-1]*(N+1)
index = 0


def dfs(x,i):
    global index
    ANS[x] = C[i]
    for y in Graph[x]:
        if ANS[y] == -1:
            index += 1
            dfs(y,index)


dfs(1,0)
print(*ANS[1:])

Solution (Python):
import sys

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


def resolve():
    def dfs(v, p):
        global res
        for u in edge[v]:
            if u == p:
                continue
            col[u] = C.pop()
            res += min(col[v], col[u])
            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()

    col = [0] * n
    col[0] = C.pop()
    dfs(0, -1)
    print(res)
    print(*col)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
import resource

sys.setrecursionlimit(20000)
n=int(input())
edges=[list(map(int,input().split())) for i in range(n-1)]
e = [[] for i in range(n)]
for a,b in edges:
  a-=1;b-=1
  e[a].append(b);e[b].append(a)
c=sorted(list(map(int,input().split())))
print(sum(c[:-1]))
visited=[False for i in range(n)]
node=[0]*n
cnt=0
def dfs(pos):
  global cnt,node,c
  if visited[pos]:return
  visited[pos]=True
  for p in e[pos]:
    dfs(p)
  node[pos]=c[cnt]
  cnt+=1
dfs(0)
print(' '.join(map(str,node)))

Solution (Python):
from collections import deque

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

l = [[] for _ in range(n)]
for a, b in ab:
    a, b = a-1, b-1
    l[a].append(b)
    l[b].append(a)
t = [-1]*n
q = deque([0])
w = [0]*n
w[0] = c.pop()
ans = 0
while q:
    v = q.pop()
    for i in l[v]:
        if i == t[v]:
            continue
        t[i] = v
        q.appendleft(i)
        w[i] = c.pop()
        ans += min(w[v], w[i])
print(ans)
print(*w)

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()))
L = [0] * N

c.sort(reverse = True)

def dfs(x, par, index):
    L[x] = c[index]
    for u in edges[x]:
        if u != par:
            index += 1
            index = dfs(u, x, index)
    return index

dfs(0, -1, 0)

print(sum(L[1:]))
print(*L)

Solution (Python):
N = int(input())
D = {i: [0] for i in range(N)}
for i in range(N-1):
  a, b = map(int, input().split())
  D[a-1].append(b-1)
  D[a-1][0] += 1
  D[b-1].append(a-1)
  D[b-1][0] += 1
m = 0
nod = -1
for i in D:
  if m < D[i][0]:
    m = D[i][0]
    nod = i
c = list(map(int, input().split()))
c.sort(reverse=True)
pnt = 0
cnt = 1
p = [nod]
L = [-1 for _ in range(N)]
L[nod] = c[0]
while cnt < N:
  n = cnt
  for i in range(pnt, cnt):
    for j in range(1, D[p[i]][0]+1):
      if L[D[p[i]][j]] == -1:
        L[D[p[i]][j]] = c[cnt]
        cnt += 1
        p.append(D[p[i]][j])
  pnt = n
S = 0
for i in D:
  for j in range(1, D[i][0]+1):
    S += min(L[i], L[D[i][j]])
print(S//2)
for i in range(N):
  print(L[i], end = ' '*(i != N - 1))
print()

Solution (Python):
n=int(input())
e=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(lambda x:int(x)-1,input().split())
  e[a].append(b)
  e[b].append(a)
c=list(map(int,input().split()))
c.sort()
print(sum(c[:-1]))

c.reverse()
ans=[0 for i in range(n)]
ans[0]=c[0]
k=1

s=[0]
while s:
  ns=[]
  for i in s:
    for j in e[i]:
      if ans[j]:
        continue
      ans[j]=c[k]
      k+=1
      ns.append(j)
  s=ns
print(" ".join(map(str,ans)))

Solution (Python):
from collections import deque
import sys

sys.setrecursionlimit(10**7)

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

c.sort(reverse=True)

cd=deque(c)
poi=[0 for _ in range(n)] 
vi=[-1 for _ in range(n)]

vi[0]+=1
def dfs(now):
  vi[now]+=1
  v=cd.popleft()
  poi[now]+=v
  for i in to[now]:
    if vi[i]==-1:
      dfs(i)
  
dfs(0)

ans=0

for u in eda:
  x,y=u
  ans+=min(poi[x],poi[y])
  
print(ans)
for u in range(n):
  poi[u]=str(poi[u])
  
print(' '.join(poi))

Solution (Python):
from collections import deque
N = int(input())
ad_ls = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    ad_ls[a].append(b)
    ad_ls[b].append(a)
c_ls = list(map(int, input().split()))
c_ls.sort(reverse=True)
c_q = deque(c_ls)


d_ls = [0] * N

q = deque()
q.append(0)
d_ls[0] = c_q.popleft()
while q:
    now = q.popleft()
    for nex in ad_ls[now]:
        if d_ls[nex] == 0:
            d_ls[nex] = c_q.popleft()
            q.append(nex)

print(sum(c_ls) - max(c_ls))
print(*d_ls)

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

N = int(readline())
G = [[] for i in range(N)]

for i in range(N - 1):
  a,b = map(int,readline().split())
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)
  
C = list(map(int,readline().split()))

def get_farest(x):
  dist = [-1] * N
  stack = [(x,-1,0)]
  while stack:
    v,parent,c = stack.pop()
    if dist[v] != -1:
      continue
    dist[v] = c
    for child in G[v]:
      if child == parent:
        continue
      stack.append([child, v, c + 1])
  maxv = -1
  maxi = -1
  for i in range(len(dist)):
    if dist[i] > maxv:
      maxv = dist[i]
      maxi = i
  return maxi

f = get_farest(0)
start = get_farest(f)

C = sorted(C, reverse = True)
from collections import deque
q = deque([])
q.append([start, -1])
ind = 0
ans = [None] * N
while q:
  v,parent = q.popleft()
  ans[v] = C[ind]
  ind += 1
  for child in G[v]:
    if child == parent:
      continue
    q.append([child, v])
  
print(sum(C[1:]))
print(*ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6
mod = 10 ** 9 + 7 





N = INT()
ab = [LIST() for _ in range(N-1)]
c = sorted(LIST())
print(sum(c)-c[-1])

cnt = [0]*N
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)
	cnt[a-1] += 1
	cnt[b-1] += 1

ans = [0]*N

q = deque([0])
while q:
	p = q.popleft()
	ans[p] = c.pop()
	for i in graph[p]:
		if ans[i] == 0:
			q.append(i)

print(*ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6
mod = 10 ** 9 + 7 





N = INT()
ab = [LIST() for _ in range(N-1)]
c = sorted(LIST())
print(sum(c)-c[-1])

cnt = [0]*N
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)
	cnt[a-1] += 1
	cnt[b-1] += 1

ans = [0]*N

q = deque([cnt.index(max(cnt))])
while q:
	p = q.popleft()
	ans[p] = c.pop()
	for i in graph[p]:
		if ans[i] == 0:
			q.append(i)

print(*ans)

Solution (Python):
from collections import deque


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

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

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


def main():
    ans = [0] * N
    ans[0] = c.pop()
    S = 0

    seen = [0] * N
    seen[0] = 1
    que = deque([0])

    while que:
        v = que.popleft()
        for nv in to[v]:
            if not seen[nv]:
                seen[nv] = 1
                ans[nv] = c.pop()
                S += ans[nv]
                que.append(nv)

    print(S)
    print(*ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def dfs(v,p):
    ans[v]=c.pop()
    for nv in G[v]:
        if nv==p:
            continue
        dfs(nv,v)

N=int(input())
G=[[] for i in range(N)]

for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
c=sorted(map(int,input().split()))
print(sum(c[:-1]))
ans=[-1]*N
dfs(0,-1)
print(*ans)

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd



n=int(input())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(n-1))
c=list(map(int,input().split()))
c.sort(reverse=True)
node=[[] for _ in range(n)]
d=deque()
d.append(0)
seen=[0]*n
seen[0]=1
ans=[0]*n
for pair in v:
    node[pair[0]].append(pair[1])
    node[pair[1]].append(pair[0])

s=0
while d:
    i=d.pop()
    ans[i]=c[s]
    s+=1
    for j in node[i]:
        if seen[j]==0:
            d.appendleft(j)
            seen[j]=1
print(sum(ans)-c[0])
print(*ans)

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd



n=int(input())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(n-1))
c=list(map(int,input().split()))
c.sort(reverse=True)
node=[[] for _ in range(n)]
d=deque()
d.append(0)
seen=[0]*n
seen[0]=1
ans=[0]*n
for pair in v:
    node[pair[0]].append(pair[1])
    node[pair[1]].append(pair[0])

s=0
while d:
    i=d.pop()
    ans[i]=c[s]
    s+=1
    for j in node[i]:
        if seen[j]==0:
            d.append(j)
            seen[j]=1
print(sum(ans)-c[0])
print(*ans)

Solution (Python):
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,=map(int,input().split())

from collections import deque

def bfs(s):
    seen = [0]*N
    d = [0]*N
    prev = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
          prev[b] = a
    return d, prev

d, prev = bfs(0)
order = list(zip(*sorted(enumerate(d), key=lambda x:x[1])))[0]

dp = [1]*N
for v in order[::-1]:
    if len(G[v])==0:
        dp[v] = 1
    dp[prev[v]] += dp[v]
    
sizes=[0]*N
for i in range(N):
  if i == 0:
    tmp = max([dp[v] for v in G[i]])
    sizes[i]=tmp
    continue
  tmp = max(dp[i]-1,N-dp[i])
  sizes[i]=tmp
  
MIN=10**20
argmin=-1
for i in range(N):
  if sizes[i]<MIN:
    MIN=sizes[i]
    argmin=i
    
c = sorted(c,reverse=True)
score=[0]*N
score[argmin]=c[0]

def bfs2(s):
    i = 1
    seen = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          score[b] = c[i]
          i += 1
    return 
  
bfs2(argmin)

ans=0
for i in range(N):
  for j in G[i]:
    if i>j:continue
    ans += min(score[i],score[j])
    
print(ans)
print(*score)

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

adj_list = [[] for _ in range(n)]

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

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

from collections import deque

dq = deque()

dq.append(0)
ans = [-1] * n

while len(dq) > 0:
    node = dq.popleft()
    ans[node] = c[idx]
    idx += 1
    for next_node in adj_list[node]:
        if ans[next_node] < 0:
            dq.append(next_node)

print(sum(c[1:]))
print(*ans)

Solution (Python):
from collections import deque

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

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

not_visited = [-1]*N
not_visited[0] = 0
stack = deque()
stack.append(0)

ans = [0]*N
ans[0] = c[0]

cut = 1
while stack:
    now = stack.popleft()
    for nex in lines[now]:
        if not_visited[nex] == -1:
            ans[nex] = c[cut]
            not_visited[nex] =  not_visited[now] + 1
            cut += 1
            stack.append(nex)

print(sum(c[1:]))
print(*ans)

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


def DFS(num,pre):
    global point
    if color[num]=="white":
        A[num]=C.pop()
        point +=min(A[num],pre)
        color[num]="black"
        for i in tree[num]:
            DFS(i,A[num])


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

color=["white" for _ in range(n+1)]
tree=[[] for _ in range(n+1)]
for a,b in AB:
    tree[a].append(b)
    tree[b].append(a)

A=[0 for _ in range(n+1)]
point=0
DFS(1,0)

print(point)
print(*A[1:])

Solution (Python):
from heapq import heappush, heappop, heapify
from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    ai, bi = map(lambda x: int(x) - 1, input().split())
    G[ai].append(bi)
    G[bi].append(ai)



C = list(map(lambda x: -int(x), input().split()))
heapify(C)
score = -sum(C) + min(C)



leaf = -1
for n in range(N):
    if len(G[n]) == 1:
        leaf = n
        break


queue = [leaf]
ans = [-1] * N
while queue:
    node = queue.pop()
    for neighbor in G[node]:
        if ans[neighbor] == -1:
            ans[neighbor] = -heappop(C)
            queue.append(neighbor)

print(score)
print(*ans)

Solution (Python):
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter



input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def solve():
    n = getN()
    g = [[] for i in range(n)]
    ans = [-1 for i in range(n)]
    ji = [0 for i in range(n)]

    for i in range(n-1):
        a, b = getZList()
        g[a].append(b)
        g[b].append(a)
        ji[a] += 1
        ji[b] += 1

    cn = getList()
    cn.sort()
    h = []
    for i, j in enumerate(ji):
        heappush(h, (j, i))

    anss = 0

    for cnn in cn:
        while True:
            cj, ci = heappop(h)
            if ans[ci] == -1:
                ans[ci] = cnn
                anss += cnn * cj
                for gg in g[ci]:
                    ji[gg] -= 1
                    heappush(h, (ji[gg], gg))
                break

    print(anss)
    print(*ans)
def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    
    solve()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    ab = [0] * (N-1)
    num = [0] * N
    l = [[] for _ in range(N)]
    for n in range(N-1):
        a, b = [int(x)-1 for x in input().strip().split()]
        l[a].append(b)
        l[b].append(a)
    C = sorted([int(x) for x in input().strip().split()], reverse=True)
    ans = 0
    q = [0]
    i = 0
    while q:
        c = q.pop()
        num[c] = C[i]
        i += 1
        for n in l[c]:
            if num[n] == 0:
                q.append(n)

    print(sum(num)-C[0])
    print(*num)

if __name__ == '__main__':
    main()

Solution (Python):
def msol19_d():
    n = int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        graph[a].append(b)
        graph[b].append(a)
    C = sorted(map(int, input().split()), reverse=True)

    score = sum(C[1:])
    label = [-1]*n
    from collections import deque
    que = deque([0])
    idx = 0
    while que:
        u = que.popleft()
        label[u] = C[idx]
        idx += 1
        for v in graph[u]:
            if label[v] != -1: continue
            que.append(v)
    print(score)
    print(*label, sep=' ')

if __name__ == '__main__':
    msol19_d()

Solution (Python):
from collections import deque


def main():
    n = int(input())
    ans = [0 for _ in range(n)]
    graph = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        graph[a].append(b)
        graph[b].append(a)
    c = list(map(int, input().split()))
    c.sort(reverse=True)
    root = 0
    max_deg = 0
    for i in range(n):
        if max_deg < len(graph[i]):
            root = i
            max_deg = len(graph[i])
    q = deque([root])
    ans[root] = c[0]
    idx = 1
    while q:
        now_v = q.pop()
        for next_v in graph[now_v]:
            if ans[next_v] == 0:
                ans[next_v] = c[idx]
                idx += 1
                q.append(next_v)
    print(sum(c[1:]))
    print(" ".join(map(str, ans)))


if __name__ == '__main__':
    main()

Solution (Python):
import sys,math,collections,itertools
input = sys.stdin.readline





N = int(input())
road = [[] for _ in range(N+1)]
number = [0]*(N+1)
for _ in range(N-1):
    a,b=map(int,input().split())
    road[a].append(b)
    road[b].append(a)
c = list(map(int,input().split()))

q = collections.deque([])
cSort=sorted(c)
number[1]=cSort.pop()
q.append(1)

while q:
    now = q.popleft()
    for idx in road[now]:
        if number[idx]==0:
            q.append(idx)
            number[idx]=cSort.pop()
print(sum(number[2:]))
print(*number[1:])

Solution (Python):
n=int(input())
e=[[i] for i in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
c=sorted(list(map(int,input().split())))
q=[1]
vis=[0]*(n+1)
ans=0
while q:
  now=q.pop()
  vis[now]=c.pop()
  for to in e[now]:
    if vis[to]:continue
    q+=[to]
print(sum(vis[2:]))
print(*vis[1:])

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)
    c = LI()
    c.sort()

    
    
    
    ans = [0] * N
    def dfs(cur):
        ans[cur] = c.pop()
        for nxt in G[cur]:
            if ans[nxt] == 0:
                dfs(nxt)

    dfs(0)

    print(sum(ans[1:]))
    print(*ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
n = int(input())
graph = [[] for _ in range(n)]
cnt = [0] * (n)
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

C = list(map(int, input().split()))
C.sort(reverse=True)
num = sum(C[1:])

ans = [0] * (n)

start = 0
par = [-1] * n
stack = [start]
idx = 0
ans[0] = C[idx]
idx += 1
while stack:
    v = stack.pop()
    for u in graph[v]:
        if u == par[v]:
            continue
        par[u] = v
        ans[u] = C[idx]
        idx += 1
        stack.append(u)
    

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

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque, defaultdict
    n = int(readline())
    edge = defaultdict(list)

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

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

    nums = [0] * (n + 1)

    que = deque()
    que.append((1, 0))

    cnt = 0
    m = 0

    while que:
        cur, prev_num = que.popleft()
        num = c[cnt]
        nums[cur] = num
        m += min(num, prev_num)
        cnt += 1
        for nx in edge[cur]:
            if nums[nx] == 0:
                que.append((nx, num))

    print(m)
    print(*nums[1:])


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

n = int(input())
V = [[] for i in range(n+1)]

a = [0]*(n-1)
for i in range(n-1):
    A,B = map(int,input().split())
    V[A].append(B)
    V[B].append(A)

c = list(map(int,input().split()))
c = sorted(c, reverse=True)
ans = sum(c[1:])


L = [0]*n
for i in range(1,n+1):
    L[i-1] = [i, len(V[i])]
    
L.sort(key= lambda val : val[1], reverse=True)

q = deque([])
d = [-1] + [0]*n
j = 0

q.append(L[0][0])
d[L[0][0]] = c[0]
j += 1

while q:
    x = q.popleft()
    for y in V[x]:
        if d[y] <= 0:
            q.append(y)
            d[y] = c[j]
            j += 1

print(ans)
for i in range(1,n+1):
    print(d[i],end="")
    print(" ",end="")

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline


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

    M = sum(C[1:])
    d = [0] * N
    i = 0
    queue = deque([(i, -1)])
    while queue:
        u, p = queue.popleft()
        d[u] = C[i]
        i += 1
        for v in G[u]:
            if v == p: continue
            queue.append((v, u))

    print(M)
    print(" ".join(map(str, d)))


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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

queue = deque([0])
ans = [0 for i in range(n)]
num = n - 1
while queue:
    cur_node = queue.popleft()
    if ans[cur_node] > 0:
        continue
    ans[cur_node] = c[num]
    num -= 1
    for i in t[cur_node]:
        queue.append(i)
print(sum(c) - max(c))
print(*ans)

Solution (Python):
from collections import deque

N = int(input())

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

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

stack=deque([0])
check = [-1]*N
check[0] = 0

while len(stack)>0:
    v = stack.popleft()
    for i in root[v]:
        if check[i] == -1:
            check[i]=check[v]+1
            stack.append(i)

keyCheck = [(i,check[i]) for i in range(N)]
keyCheck.sort(key=lambda t:t[1])

ans = [-1]*N
for i in range(N):
    ans[keyCheck[i][0]] = c[i]

print(sum(c[1:]))
print(*ans)

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

def bfs():
    q = deque([0])
    dist = [-1]*N
    dist[0] = 0
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
    
    return dist

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

for _ 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(reverse=True)
dist = bfs()
idist = [(i, dist[i]) for i in range(N)]
idist.sort(key=lambda t: t[1])
ans = [-1]*N

for i in range(N):
    ans[idist[i][0]] = c[i]

print(sum(c[1:]))
print(*ans)

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

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

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

C = list(map(int, input().split()))
C.sort(reverse=True)
nodes = [0] * N


cidx = -1
ans = []
def dfs(v, pv, w):
    global cidx
    cidx += 1
    nodes[v] = C[cidx]
    ans.append(min(w, C[cidx]))
    for nv in edge[v]:
        if pv == nv: continue
        dfs(nv, v, C[cidx])

dfs(0, 0, 0)
print(sum(ans))
print(*nodes, sep=" ")

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

N = int(input())
edge = [[] for _ in range(N)]
cnt = [[0,i] for i in range(N)]

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


cnt.sort(reverse=True)
start = cnt[0][1]
C = list(map(int, input().split()))
C.sort(reverse=True)
nodes = [0] * N


cidx = -1
ans = []
def dfs(v, pv, w):
    global cidx
    cidx += 1
    nodes[v] = C[cidx]
    ans.append(min(w, C[cidx]))
    for nv in edge[v]:
        if pv == nv: continue
        dfs(nv, v, C[cidx])

dfs(start, 0, 0)
print(sum(ans))
print(*nodes, sep=" ")

Solution (Python):
N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
C = sorted(list(map(int, input().split())))
M = sum(C[:-1])
import sys
sys.setrecursionlimit(10**8)

def dfs(v):
  for u in edge[v]:
    if nums[u]==-1:
      nums[u]=C.pop(-1)
      dfs(u)
  return 0

nums = [-1]*N
nums[0] = C.pop(-1)
dfs(0)

print(M)
print(*nums)

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)