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):
from collections import deque

def bfs():
    q = deque()
    q.append(1)
    ans = [0] * n
    i = 0
    while q:
        p = q.popleft()
        ans[p - 1] = c[i]
        i += 1
        for j in G[p]:
            if ans[j - 1] == 0:
                q.append(j)
    return ans

n = int(input())
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
c = list(map(int, input().split()))
c.sort(reverse = True)
s = sum(c) - c[0]
ans = bfs()
print(s)
print(*ans)

Solution (Python):
from collections import deque
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)

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

que = deque()
que.append(0)
seen = [False for _ in range(n)]
seen[0] = True
memo = [0]
while que:
    cur = que.popleft()
    for to in edges[cur]:
        if seen[to]:
            continue
        seen[to] = True
        memo.append(to)
        que.append(to)


print(sum(d) - d[0])

ans = [0 for _ in range(n)]
for i in range(n):
    ans[memo[i]] = d[i]

print(*ans)

Solution (Python):




import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

prepare=[]
n=I()
tree=[[] for i in range(n)]
for i in range(n-1):
    a,b=MI()
    a-=1
    b-=1
    prepare.append([a,b])
    tree[a].append(b)
    tree[b].append(a)
lis=sorted(LI(),reverse=True)
answers=[0 for i in range(n)]
Q=deque([0])
answers[0]=lis[0]
count=1
while Q:
    q=Q.popleft()
    for x in tree[q]:
        if answers[x]==0:
            answers[x]=lis[count]
            Q.append(x)
            count+=1

ans=0
for i in range(n-1):
    ans+=min(answers[prepare[i][0]],answers[prepare[i][1]])
print(ans)
print(*answers)

Solution (Python):
from collections import deque

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

C = list(map(int, input().split()))
C.sort()
ans = sum(C[:-1])
dep = [-1] * N
dep[0] = C.pop()
d = deque([[0, -1]])
while d:
  node, par = d.popleft()
  children = tree[node]
  for child in children:
    if child == par:
      continue
    dep[child] = C.pop()
    d.append([child, node])

print(ans)
print(*dep)

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 permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

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






def build_tree(N, edge_list):

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

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

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

    return G, leaves

N = getN()
query = [[] for i in range(N - 1)]
for i in range(N - 1):
    query[i] = getList()

d = list(sorted(getList()))

edges, leaves = build_tree(N, query)

v = leaves[0]


ans = -d[-1]
nodes = [0] * N


def dfs(now):
    global ans
    if nodes[now] > 0:
        return
    nodes[now] = d.pop()
    ans += nodes[now]
    for i in edges[now]:
        if nodes[i] > 0:
            continue
        dfs(i)

dfs(v)
print(ans)
print(*nodes)

Solution (Python):
from collections import deque
from heapq import heapify, heappop, heappush
N = int(input())
edge = [[] for _ in range(N)]
ID = set([i for i in range(N-1)])
popular = [0 for _ in range(N)] 

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


Q = []
C = list(map(int,input().split()))
C.sort(reverse = True)
ans = sum(C) - max(C)
print(ans)







Q = deque([])
Q.append(0)
R = [-1 for _ in range(N)]
num = -1
v = 0
reach = set([])
while Q:
  v = Q.popleft() 
  if v in reach:
    continue
  reach.add(v)
  num += 1
  
  R[v] = C[num]
  for u in edge[v]:
    Q.append(u)


print(*R)

Solution (Python):

def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G
from collections import deque
def bfs(v, p):
    q = deque()
    q.append((v, p))
    rec[v - 1] = c.pop()
    while c:
        V, P = q.popleft()
        for nv in G[V - 1]:
            if nv == P:continue
            rec[nv - 1] = c.pop()
            q.append((nv, V))

n = int(input())
ab = [list(map(int, input().split())) for i in range(n - 1)]
c = list(map(int, input().split()))
c.sort()
G = Graph(ab)
print(sum(c[:-1]))
rec = [0] * n
bfs(1, -1)
print(*rec)

Solution (Python):
from collections import deque

def main():
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edge[a].append(b)
        edge[b].append(a)
    C = list(map(int, input().split()))
    C.sort(reverse=True)
    ans = [0] * N
    Q = deque([0])
    cnt = 0
    ans[0] = C[0]
    while Q:
        s = Q.pop()
        for v in edge[s]:
            if ans[v]:
                continue
            cnt += 1
            ans[v] = C[cnt]
            Q.append(v)

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


if __name__ == "__main__":
    main()

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


def DFS(num,pre):
    global point
    if color[num]=="white":
        ans[num]=C.pop()
        point +=min(ans[num],pre)
        color[num]="black"
        for i in T[num]:
            DFS(i,ans[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)]

T=[[] for _ in range(n)]
for a,b in AB:
    T[a-1].append(b-1)
    T[b-1].append(a-1)

ans=[0 for _ in range(n)]
point=0
DFS(0,0)

print(point)
print(*ans)

Solution (Python):
from collections import deque
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
c = list(map(int, input().split()))
c.sort(reverse=True)
ans = [None]*n
ans[0] = c[0]
q = deque([0])
i = 1
while q:
    node = q.popleft()
    for c_node in graph[node]:
        if ans[c_node] is not None:
            continue
        ans[c_node] = c[i]
        i += 1
        q.append(c_node)
print(sum(c)-c[0])
print(*ans)

Solution (Python):
from collections import defaultdict, deque

N = int(input())
X = defaultdict(list)
for i in range(N - 1):
    ai, bi = map(lambda s: int(s) - 1, input().split())
    X[ai].append(bi)
    X[bi].append(ai)
c = list(map(int, input().split()))

c.sort(reverse=True)
print(sum(c[1:]))
d = [0] * N
q = deque([0])
i = 0
while len(q) > 0:
    v = q.popleft()
    d[v] = c[i]
    i += 1
    for x in X[v]:
        if d[x] != 0:
            continue
        q.append(x)
print(' '.join(list(map(str, d))))

Solution (Python):
from sys import stdin
from collections import defaultdict,deque
N = int(stdin.readline().rstrip())
adj = defaultdict(set)

for i in range(N-1):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]
    adj[a].add(b)
    adj[b].add(a)
    
C = [int(x) for x in stdin.readline().rstrip().split()]

ans = sum(C) - max(C)
print(ans)

visit_p = deque()
visit_p.append(1)
visited = [False]*(N+1)
visited[1] = True

C.sort(reverse=True)
 
print(C[0],end=" ")
cnt = 1
ans_lst = [0]*(N+1)
while visit_p:
    now_v = visit_p.popleft()
    for v in adj[now_v]:
        if visited[v]:
            continue
        ans_lst[v] = C[cnt]
        cnt += 1
        visited[v] = True
        visit_p.append(v)
for i in ans_lst[2:]:
    print(i,end=" ")

Solution (Python):
n = int(input())
graph = [[] for _ in range(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 = [int(i) for i in input().split()]
c.sort()
c.reverse()
ans_list = [0 for _ in range(n)]
ans = 0
p_list = [0]
ans_list[0] = c.pop(0)
while len(p_list) > 0:
    p = p_list.pop(0)
    for g in graph[p]:
        if ans_list[g] == 0:
            ans_list[g] = c.pop(0)
            ans += ans_list[g]
            p_list.append(g)
print(ans)
print(' '.join([str(i) for i in ans_list]))

Solution (Python):
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
cl = list(map(int, input().split()))
cl.sort(reverse=True)

e = [set() for _ in range(n)]
for a,b in ab:
    a -= 1
    b -= 1
    e[a].add(b)
    e[b].add(a)

used = [False]*n
q = [0]

res = [0]*n
i = 0
while len(q)>0:
    u = q.pop()
    res[u] = cl[i]
    used[u] = True
    i += 1
    for v in e[u]:
        if not used[v]:
            q.append(v)

r = 0
for a,b in ab:
    r += min(res[a-1], res[b-1])
print(r)
print(*res)

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    way = [[] for _ in [0]*n]
    for i in [0]*(n-1):
        a,b = map(int,ipt().split())
        way[a-1].append(b-1)
        way[b-1].append(a-1)
    c = [int(i) for i in ipt().split()]
    c.sort(reverse=True)
    ans = [0]*n
    q = queue.Queue()
    ans[0] = c[0]
    ni = 1
    q.put(0)
    sum = 0
    while ni < n:
        qi = q.get()
        for i in way[qi]:
            if ans[i] == 0:
                ans[i] = c[ni]
                sum += c[ni]
                ni += 1
                q.put(i)

    print(sum)
    print(" ".join(map(str,ans)))



    return

if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
edge=[[] for _ in range(N)]
for _ in range(N-1):
    a,b=map(int1,input().split())
    edge[a].append(b)
    edge[b].append(a)
C=list(map(int,input().split()))
C.sort()
print(sum(C)-C[-1])
que=deque([0])
ans=[-1]*N
while que:
    v=que.popleft()
    ans[v]=C.pop()
    for nv in edge[v]:
        if ans[nv]==-1:
            que.append(nv)
print(*ans)

Solution (Python):
from collections import deque
n = int(input())
path = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path[a].append(b)
    path[b].append(a)
C = sorted(list(map(int,input().split())),reverse = True)
M = sum(C[1:])
ans = [-1]*n
que = deque([0])
i = 0
while que:
    p = que.popleft()
    ans[p] = C[i]
    i += 1
    for nxt in path[p]:
        if ans[nxt] >= 0:continue
        que.append(nxt)
print(M)
print(' '.join(str(i) for i in ans))

Solution (Python):

"""
問題：
木が与えられる。
リストCが与えられるので、各頂点に割り当てる。
全ての辺において、その辺をつなぐ2頂点をa,bとした時、min(Ca,Cb)をスコアとする。
これを最大化するスコアを求め、そのような頂点への数値の割り振りを出力せよ。
考察：
シュミレーションしてみると、
1.辺数が多い頂点に大きい数字を割り当てると良さそう
2.複数あっても適当に選んで良い
3.大きい数字は隣り合ったほうが良い
4.よって、辺数が多い頂点をrootとして、そこから幅を優先して
大きい数字を順に割り当てるのが良さそう。
5.この時には別に子の辺数を気にする必要はない。(これは、その"子"がスコアとして使用
されるのは必ず1回であることから言える)
解法：
接続する辺が最も多い頂点をrootとして、幅優先でそこから大きい値を割り振っていく。
全ての子は必ず1回づつ使われるので、実はスコアの最大値は
all(C)-(rootの値)となる。
"""
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
g = [[] for _ in range(n)]
edges = [0]*n
for i in range(n-1):
    a,b = map(int,readline().split())
    a,b = a-1,b-1
    edges[a] += 1
    edges[b] += 1
    g[a].append(b)
    g[b].append(a)
C = list(map(int,readline().split()))
C.sort(reverse=True)
C = deque(C)
root = 0
res = 0
for i in range(n):
    if res < edges[i]:
        root = i
        res = edges[i]

ans = [-1]*n
ans[root] = C.popleft()
deq = deque([root])
while deq:
    fr = deq.popleft() 
    for go in g[fr]:
        if ans[go] != -1:
            continue
        ans[go] = C.popleft()
        deq.append(go)

print(sum(ans)-ans[root])
print(*ans)

Solution (Python):
from collections import deque
N = int(input())
G = [[] for i in range(N+1)]
for i in range(N-1):
  a,b = map(int,input().split())
  G[a].append(b)
  G[b].append(a)
c = list(map(int,input().split()))
c.sort()
M = sum(c)-c[-1]

score = [0 for i in range(N+1)]

seen = [False for i in range(N+1)]
seen[1] = True
score[1] = c.pop()
d = deque([1])
while len(d)>0:
  v = d.pop()
  for i in G[v]:
    if seen[i] == False:
      seen[i] = True
      score[i] = c.pop()
      d.append(i)

print(M)
print(*score[1:])

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

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

c = deque(sorted(list(map(int, input().split())), reverse=True))
visit = [-1 for _i in range(n)]
visit[0] = c.popleft()

def solve(p):
    r = 0
    for i in tree[p]:
        if visit[i] < 0:
            visit[i] = c.popleft()
            r += visit[i]
            r += solve(i)
    return r
x = solve(0)
print(x)
print(*visit)

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

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

c = deque(sorted(list(map(int, input().split())), reverse=True))
visit = [-1 for _i in range(n)]
visit[0] = c.popleft()

def solve(p):
    r = 0
    for i in tree[p]:
        if visit[i] < 0:
            visit[i] = c.popleft()
            r += visit[i]
            r += solve(i)
    return r
x = solve(0)
print(x)
print(*visit)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n=int(input())
    graph=[[]for _ in range(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)
    C=list(map(int,input().split()))
    C.sort(reverse=True)
    node_c=[0]*n 
    node_c[0]=C[0]
    queue=deque([0])
    i=1
    while queue:
        node=queue.popleft()
        for xnode in graph[node]:
            if node_c[xnode]>0:continue
            node_c[xnode]=C[i]
            i+=1
            queue.append(xnode)
    print(sum(C[1:]))
    print(' '.join(map(str,node_c)))

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n=int(input())
    graph=[[]for _ in range(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)
    C=list(map(int,input().split()))
    C.sort(reverse=True)
    node_c=[0]*n 
    node_c[0]=C[0]
    queue=deque([0])
    i=1
    while queue:
        node=queue.popleft()
        for xnode in graph[node]:
            if node_c[xnode]>0:continue
            node_c[xnode]=C[i]
            i+=1
            queue.append(xnode)
    print(sum(C[1:]))
    print(' '.join(map(str,node_c)))

if __name__=='__main__':
    main()

Solution (Python):

def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G


from collections import deque
def bfs(G, v, p):
    point = [0] * n
    q=deque()
    q.append((v, p))
    point[0] = c.pop(0)

    score = 0
    while q:
        
        V, P = q.popleft()
        for next_v in G[V - 1]:
            if next_v == P:continue
            q.append((next_v, V))
            temp = c.pop(0)
            score += temp
            point[next_v - 1] = temp

    return point, score

n = int(input())
ab = [list(map(int,input().split())) for i in range(n - 1)]
c = list(map(int,input().split()))
c = sorted(c, reverse=True)
G = Graph(ab)

point, score = bfs(G, 1, -1)
print(score)
print(*point)

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

from collections import deque

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

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

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

d = deque([0])
ans = [c[0]] + [0]*(N-1)
M = 0
c_idx = 1

while d:
    p = d.popleft()
    for n in neighbor[p]:
        if not ans[n]:
            ans[n] = c[c_idx]
            M += c[c_idx]
            c_idx += 1
            d.append(n)

print(M)
print(*ans)

Solution (Python):
from collections import deque
N = int(input())
T = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(lambda x:int(x)-1,input().split())
    T[a].append(b)
    T[b].append(a)
P = list(map(int,input().split()))
P.sort(reverse=True)
A = [-1]*N
v = -1
for i in range(N):
    if len(T[i])==1:
        v = i
        break
Q = deque([v])
p_index = 0
while Q:
    v = Q.pop()
    A[v] = P[p_index]
    p_index+=1
    for c in T[v]:
        if A[c]==-1:
            Q.append(c)
print(sum(P[1:]))
print(*A)

Solution (Python):
from collections import deque
N=int(input())
G=[[]for _ in range(N)]
cnt=[0]*N
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
    cnt[a]+=1
    cnt[b]+=1

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

root=0
v=0
for i in range(N):
    if v>cnt[i]:
        root=i
        v=cnt[i]

def bfs(s):
    que=deque()
    que.append(s)
    nodes=[-1]*N
    k=0
    ans=0
    while len(que)>0:
        q=que.pop()
        nodes[q]=C[k]
        k+=1

        for v in G[q]:
            if nodes[v]<0:
                que.append(v)
    print(sum(C[1:]))
    print(*nodes)

bfs(root)

Solution (Python):
from collections import deque
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 = [int(x) for x in input().split()]
c = sorted(c, reverse=True)

q = deque([0])
visited = [False]*n
ans = [-1]*n
ans[0] = c[0]
i = 1

while q:
    v = q.popleft()
    visited[v] = True
    for w in g[v]:
        if not visited[w]:
            ans[w] = c[i]
            i += 1
            q.append(w)

print(sum(c[1:]))
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(reverse = True)
edges = [[] for _ in range(n)]
ans = [-1]*n
ans[0] = c[0]
count = 1

for a,b in ab:
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

q = [0]

while q:
    l = q.pop(-1)
    for l1 in edges[l]:
        if ans[l1] == -1:
            q.append(l1)
            ans[l1] = c[count]
            count += 1

print(sum(c[1:]))
for i in ans:
    print(i, end = ' ')

Solution (Python):
from collections import Counter
from collections import deque
n = int(input())

counter = [0]*n
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)
  counter[a-1] += 1
  counter[b-1] += 1
  
C = sorted(list(map(int,input().split())))[::-1]


root = 0
v = 0
for i in range(n):
  if v > counter[i]:
    root = i
    v = counter[i]


def bfs(s):
  que = deque()
  que.append(s)
  nodes = [-1]*n
  k = 0
  ans = 0
  while len(que)>0:    
    q = que.pop()    
    nodes[q] = C[k]    
    k += 1
    
    for v in G[q]:
      if nodes[v]<0:
        que.append(v)
  
  print(sum(C[1:]))
  print(*nodes)                

bfs(root)

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

nodes = [set() for _ in range(N+1)]

for _ in range(N-1):
    a, b = [int(x) for x in input().split()]
    cnt[a-1] = cnt.get(a-1,0) + 1
    cnt[b-1] = cnt.get(b-1,0) + 1
    nodes[a-1].add(b-1)
    nodes[b-1].add(a-1)


C = [int(x) for x in input().split()]
C = sorted(C, reverse=True)

Z = cnt.items()
Z = sorted(Z, key=lambda x:x[1], reverse=True)


opennodes = {Z[0][0]}
closednodes = set()

ans = [-1] * N


for i in range(N):
    n = opennodes.pop()
    closednodes.add(n)
    ans[n] = C[i]

    for nn in nodes[n]:
        if not nn in closednodes:
            opennodes.add(nn)

print(sum(C) - max(C))
print(" ".join([str(x) for x in ans]))

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

deg = [0 for i in range(n)]

from collections import defaultdict
G = defaultdict(list)


abl = []
for _ in range(n-1):
    a,b = map(int,input().split())
    deg[a-1] += 1
    deg[b-1] += 1
    abl.append((a-1, b-1))
    G[a-1].append(b-1)
    G[b-1].append(a-1)

cl = list(map(int,input().split()))
cl = sorted(cl)
ansl = [0 for _ in range(n)]
for c in cl:
    for idx, d in enumerate(deg):
        if d == 1:
            ansl[idx] = c
            deg[idx] -= 1
            for j in G[idx]:
                deg[j] -= 1
            break
for idx, a in enumerate(ansl):
    if a == 0:
        ansl[idx] = cl[-1]

print(sum(cl[:-1]))
print(*ansl)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque

n = int(readline())
graph = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, readline().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
c = list(map(int, readline().split()))
c.sort()
print(sum(c[:-1]))
q = deque([0])
d = [-1] * n

while q:
    x = q.popleft()
    d[x] = c.pop()
    for next in graph[x]:
        if d[next] < 0:
            q.appendleft(next)

print(*d)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
s=[[]for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x: int(x)-1,input().split())
    s[a].append(b)
    s[b].append(a)
sys.setrecursionlimit(20000)
l=[None]*N
def hu(n):
    for i in s[n]:
        if l[i]==None:
            l[i]=c.pop()
            hu(i)
c=list(map(int,input().split()))
c.sort()
print(sum(c[:-1]))
l[0]=c.pop()
hu(0)
print(*l)

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 = sorted(list(map(int,input().split())))[::-1]

ans = [-1 for i in range(N)] 
point = sum(C[1:])

from collections import deque
q = deque([])
q.append(0)
ind = 0
while q:
  v = q.popleft()
  if ans[v] != -1:
    
    continue
  ans[v] = C[ind]
  ind += 1
  if ind == len(C):
    break
  children = E[v]
  for child in children:
    q.append(child)
  
print(point)  
print(*ans)

Solution (Python):
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 = [int(i) for i in input().split()]

C.sort()

M = sum(C[:-1])
d = [-1] * N

from collections import deque

que = deque([0])
while que:
    v = que.popleft()
    d[v] = C.pop()
    for w in edge[v]:
        if d[w] < 0:
            que.append(w)

print(M)
print(*d)

Solution (Python):
N=int(input())
G=[[] for _ in range(N)]
for _ in range(N-1):
    a,b=map(int, input().split())
    a,b=a-1,b-1
    G[a].append(b)
    G[b].append(a)
*C,=map(int, input().split())

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

stk=[0]
ans[0]=C[0]
idx=1
while stk:
    v=stk.pop()
    for to in G[v]:
        if ans[to]>0: continue
        ans[to]=C[idx]
        idx+=1
        stk.append(to)

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

Solution (Python):
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    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 = [int(c) for c in input().split()]
    C.sort(reverse  = True)
    Color = [None] * N
    Color[0] = C[0]
    q = deque()
    for e in Edge[0]:
        q.append((e, 0))
    ans = 0
    for i in range(1, N):
        nowN, preN = q.popleft()
        ans += C[i]
        Color[nowN] = C[i]
        for e in Edge[nowN]:
            if e != preN: q.append((e, nowN))
    print(ans)
    print(" ".join(map(str, Color)))

    return 0

if __name__ == "__main__":
    solve()

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

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

s = []
parent = [-1]*n
order = []
s.append(0)
while s:
    v = s.pop()
    order.append(v)
    for u in g[v]:
        if parent[v] == u:
            continue
        parent[u] = v
        s.append(u)

order.reverse()
ans = 0
D = [0]*n
for i in range(n):
    v = order[i]
    D[v] = C[i]
    if i != n-1:
        ans += C[i]
print(ans)
print(*D)

Solution (Python):
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
C = list(map(int,input().split()))
C.sort()
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

stack = [0]
ans = [-1] * N
ans[0] = C.pop()
m = 0
while stack:
    v = stack.pop()
    for to in es[v]:
        if ans[to] >= 0: continue
        ans[to] = C.pop()
        m += ans[to]
        stack.append(to)
print(m)
print(*ans)

Solution (Python):
n=int(input())
edge=[[]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)
c=list(map(int,input().split()))
c.sort(reverse=1)
print(sum(c)-c[0])
d=[-1]*n
d[0]=c[0]
Q=[0]
visited={0}
ind=1
while Q:
  P=[]
  for i in Q:
    for j in edge[i]:
      if j in visited:continue
      visited.add(j)
      d[j]=c[ind]
      ind+=1
      P.append(j)
  Q=P
print(*d)

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

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)
C = list(map(int, input().split()))
A = sum(C) - max(C)
C.sort()

ans = [None] * N
ans[0] = C.pop()
st = [0]
while st:
    now = st.pop()
    for to in edges[now]:
        if ans[to] == None:
            ans[to] = C.pop()
            st.append(to)

print(A)
print(*ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**5*5)
n=int(input())
ab=[[]for _ in range(n)]
for _ in range(n-1):
	a,b=map(int,input().split())
	ab[a-1].append(b-1)
	ab[b-1].append(a-1)
c=list(map(int,input().split()))
c.sort()
print(sum(c)-c[-1])
ans=[-1]*n
cnt=0
node=[]
visited=[0]*n
ans=[-1]*n
def dfs(x):
	global cnt
	ans[x]=c[-cnt-1]
	visited[x]=1
	for next in ab[x]:
		if visited[next]==0:
			cnt+=1
			dfs(next)
dfs(0)
print(*ans)

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

from collections import deque
Q = deque()
Q.append(0)
visited=[-1]*n
visited[0]=0

ind=1
while Q:
    now = Q.popleft()
    for nxt in link[now]:
        if visited[nxt]!=-1:
            continue
        visited[nxt]=ind
        ind+=1
        Q.append(nxt)
for i in visited:
    print(c[i],end=" ")

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

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)
    
    color = [-1] * n
    s = deque([0])
    i = 0
    while len(s):
        v = s.pop()
        color[v] = c[i]
        for e in G[v]:
            if color[e] != -1:
                continue
            s.append(e)
        i += 1
    
    print(sum(c) - c[0])
    print(*color)
if __name__ =='__main__':
    main()

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

MAXN = 10000
G = [[] for _ in range(MAXN)]
color = [-1] * MAXN

def dfs(i,idx,c):
    color[i] = c[idx]
    for e in G[i]:
        if color[e] != -1:
            continue
        idx = dfs(e,idx + 1,c)
    return idx

def main():
    n = int(input())
    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)

    dfs(0,0,c)
    ans = sum(c) - c[0]
    print(ans)
    print(*color[:n])

if __name__ =='__main__':
    main()