Problem:
 Score : 500 points    Problem Statement You are given a tree with N vertices 1,2,\ldots,N , and positive integers c_1,c_2,\ldots,c_N .
The i -th edge in the tree (1 \leq i \leq N-1) connects Vertex a_i and Vertex b_i .  We will write a positive integer on each vertex in T and calculate our score as follows:   On each edge, write the smaller of the integers written on the two endpoints.  Let our score be the sum of the integers written on all the edges.   Find the maximum possible score when we write each of c_1,c_2,\ldots,c_N on one vertex in T , and show one way to achieve it. If an integer occurs multiple times in c_1,c_2,\ldots,c_N , we must use it that number of times.      Constraints  1 \leq N \leq 10000  1 \leq a_i,b_i \leq N  1 \leq c_i \leq 10^5  The given graph is a tree.         Input Input is given from Standard Input in the following format:  N  a_1  b_1  :  a_{N-1}  b_{N-1}  c_1  \ldots  c_N       Output Use the following format:  M  d_1  \ldots  d_N   where M is the maximum possible score, and d_i is the integer to write on Vertex i . d_1,d_2,\ldots,d_N must be a permutation of c_1,c_2,\ldots,c_N .
If there are multiple ways to achieve the maximum score, any of them will be accepted.        Sample Input 1 5
1 2
2 3
3 4
4 5
1 2 3 4 5      Sample Output 1 10
1 2 3 4 5  If we write 1,2,3,4,5 on Vertex 1,2,3,4,5 , respectively, the integers written on the four edges will be 1,2,3,4 , for the score of 10 . This is the maximum possible score.       Sample Input 2 5
1 2
1 3
1 4
1 5
3141 59 26 53 59      Sample Output 2 197
59 26 3141 59 53  c_1,c_2,\ldots,c_N may not be pairwise distinct.

Solution (Python):
N = int(input())
AB = [[int(_) for _ in input().split()] for _ in range(N - 1)]
C = sorted([int(_) for _ in input().split()])
Pairs = [set() for _ in range(N)]
for a, b in AB:
    
    a -= 1
    b -= 1
    Pairs[a].add(b)
    Pairs[b].add(a)
visited = [False] * N
visited[0] = True
count = [0] * N
stack = [0]
start = []
parent = [0] * N
while stack:
    fr = stack.pop()
    updated = False
    for to in Pairs[fr]:
        if not visited[to]:
            visited[to] = updated = True
            stack += [to]
            count[fr] += 1
            parent[to] = fr
    if not updated:
        start += [fr]
order = []
while start:
    fr = start.pop()
    if count[fr]:
        continue
    order += [fr]
    to = parent[fr]
    count[to] -= 1
    start += [to]
ans = [0] * N
for i in range(N):
    ans[order[i]] = C[i]
score = 0
for a, b in AB:
    
    a -= 1
    b -= 1
    score += min([ans[a], ans[b]])
print(score)
print(*ans)

Solution (Python):

import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class DGraph:
    def __init__(self, n, edges):
        self._vertice = [{} for _ in range(n)]
        for e in edges:
            self._vertice[e[0]][e[1]] = e[2] if len(e) == 3 else 1

    def __len__(self):
        return len(self._vertice)

    def edges(self, n=None):
        srcs = range(len(self)) if n is None else [n]
        return sum([[(s, d, c) for d, c in self._vertice[s].items()] for s in srcs], [])

    def transpose(self):
        tedges = [(t, f, c) for f, t, c in self.edges()]
        return DGraph(len(self), tedges)

    def cost(self, src, dst):
        return self._vertice[src].get(dst, float('inf'))

class Graph(DGraph):
    def __init__(self, n, edges):
        nd_edges = edges + [(d, s, c) for s, d, c in edges]
        super().__init__(n, nd_edges)

    def transpose(self):
        return self



def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    edges = [(ca - 1, cb - 1, 0) for ca, cb in zip(a, b)]
    g = Graph(N, edges)
    s = [-1] * N

    c = deque(sorted(c, reverse=True))
    q = deque([0])
    while 0 < len(q):
        n = q.popleft()
        if s[n] != -1:
            continue
        s[n] = c.popleft()
        for _, d, _ in g.edges(n):
            q.append(d)

    ret = 0
    for b, e, _ in g.edges():
        ret += min(s[b], s[e])
    ret //= 2
    return '\n'.join([str(ret), ' '.join([str(n) for n in s])])

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int()] * (N-1)  
    b = [int()] * (N-1)  
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    c = [ int(next(tokens)) for _ in range(N) ]  
    result = solve(N, a, b, c)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
N=int(input())
ab=list(list(map(int,input().split()))for _ in range(N-1))
c=list(map(int,input().split()))
c.sort(reverse=True)
graph=[[] for _ in range(N+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
queue=deque([1])
ans=[[] for _ in range(N+1)]
sumans=-c[0]
c=deque(c)
while len(queue)>0:
    x=queue.popleft()
    y=c.popleft()
    ans[x].append(y)
    sumans+=y
    for i in graph[x]:
        if ans[i]==[]:
            queue.append(i)
print(sumans)
for j in ans[1:]:
    print(*j,end=' ')

Solution (Python):
from heapq import heappush, heappop
from operator import itemgetter


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



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


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


dp = dijkstra(G, 1)
x = sorted(c)
ans = '{}\n{}'.format(
    sum(x[:-1]),
    ' '.join(
        str(d)
        for (_, _), d in sorted(
            zip(
                sorted(
                    enumerate(dp[1:]),
                    key=itemgetter(1),
                    reverse=True
                ),
                x
            )
        )
    )
)


print(ans)

Solution (Python):
from collections import deque
N=int(input())
G=[[] for i in range(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)
j=0
c=sorted([int(i) for i in input().split()])
M=sum(c)-max(c)
d=[-1 for i in range(N)]
q=deque([j])
while(len(q)>0):
    r=q.popleft()
    d[r]=c.pop()
    for p in G[r]:
        if d[p]==-1:
            q.appendleft(p)
print(M)
print(" ".join([str(i) for i in d]))

Solution (Python):
import sys

sys.setrecursionlimit(110000)


def inpl():
    return list(map(int, input().split()))


class UnionFind:
    def __init__(self, N):
        
        self.par = [i for i in range(N)]
        self.N = N
        self.hop = {i: -1 for i in range(N)}
        self.adj = [[] for i in range(N)]
        return

    def root(self, x):
        if self.par[x] == x:
            return (x)
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def same(self, x, y):
        return (self.root(x) == self.root(y))

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if (x == y):
            return False

        self.par[x] = min(x, y)
        self.par[y] = min(x, y)
        return True

    def find_root(self):
        for i in range(self.N):
            if i == self.root(i):
                return i
        return

    def dfs(self, i):
        for nh in self.adj[i]:
            if self.hop[nh] != -1:
                continue
            else:
                self.hop[nh] = self.hop[i] + 1
                self.dfs(nh)
        return


N = int(input())
uf = UnionFind(N)
AB = [[0, 0] for i in range(N - 1)]

for i in range(N - 1):
    a, b = inpl()
    a -= 1
    b -= 1
    AB[i][0] = a
    AB[i][1] = b
    uf.adj[a].append(b)
    uf.adj[b].append(a)

C = inpl()

for a, b in AB:
    uf.union(a, b)

root_num = uf.find_root()
uf.hop[root_num] = 0
uf.dfs(root_num)

dic2 = sorted(uf.hop.items(), key=lambda x: x[1], reverse=True)

ans = [0 for i in range(N)]
for i, k in enumerate(dic2):
    ans[k[0]] = i

C.sort()

print(sum(C[:-1]))
for i in range(N):
    if i != 0:
        print(" ", end="")
    print(C[ans[i]], end="")
print("")

Solution (Python):
inpl = lambda: list(map(int,input().split()))
N = int(input())
partners = []
for i in range(N):
    partners.append(set())
for i in range(N-1):
    a, b = inpl()
    a -= 1
    b -= 1
    partners[a].add(b)
    partners[b].add(a)
C = sorted(inpl())

def goto_leaf(k):
    prev_k = None
    while len(partners[k]) > 1:
        for p in partners[k]:
            if p != prev_k:
                break
        prev_k = k
        k = p
    return k

def delete_leaf(k):
    for stem in partners[k]:
        break
    partners[stem].remove(k)
    return stem

M = sum(C[:-1])
D = [0]*N
k = 0
for i in range(N-1):
    k = goto_leaf(k)
    D[k] = C[i]
    k = delete_leaf(k)
D[k] = C[N-1]

print(M)
print(' '.join(map(str,D)))

Solution (Python):
N = int(input())
E=[list(map(int,input().split())) for i in range(N-1)]
C=list(map(int,input().split()))
C.sort(reverse=True)

print(sum(C[1:]))

ELIST = [[] for i in range(N+1)]
for a,b in E:
  ELIST[a].append(b)
  ELIST[b].append(a)


from collections import deque
QUE =deque([1])

i=0
ANS=[-1]*(N+1)
while QUE:
  x=QUE.pop()
  ANS[x]=C[i]
  i+=1
  for to in ELIST[x]:
    if ANS[to]==-1: 
      QUE.append(to)
      ANS[to]=0
      
print(*ANS[1:])

Solution (Python):
inpl = lambda: list(map(int,input().split()))
class SegmentTree:
    def __init__(self, value, N=0, comp=lambda x,y: x<=y):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.get_value(left_i), self.get_value(right_i)
            if self.comp(left_v, right_v):
                self.node[i] = left_i
            else:
                self.node[i] = right_i

    def set_value(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.get_value(left_i), self.get_value(right_i)
            if self.comp(left_v, right_v):
                new_i = left_i
            else:
                new_i = right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def get_value(self, n):
        return self.value[n]

    def get_min(self, a=0, b=-1):
        return self.value[self.get_min_index(a,b)]

    def get_min_index(self,
                     a=0, b=-1,
                     k=0, l=0, r=-1):
        if b < 0:
            b = self.N
        if r < 0:
            r = self.N
        if a <= l and r <= b:
            return self.node[k]
        elif r <= a or b <= l:
            return None
        else:
            left_i = self.get_min_index(a,b,2*k+1,l,(l+r)//2)
            right_i = self.get_min_index(a,b,2*k+2,(l+r)//2,r)
            left_v, right_v = self.get_value(left_i), self.get_value(right_i)
            if self.comp(left_v, right_v):
                return left_i
            else:
                return right_i

N = int(input())
partners = []
orders = [0]*N
for i in range(N):
    partners.append(set())
for i in range(N-1):
    a, b = inpl()
    a -= 1
    b -= 1
    partners[a].add(b)
    partners[b].add(a)
    orders[a] += 1
    orders[b] += 1
sg = SegmentTree(orders)
C = sorted(inpl())
D = [0]*N
M = 0

for i in range(N-1):
    k = sg.get_min_index()
    D[k] = C[i]
    M += C[i]
    for p in partners[k]:
        partners[p].remove(k)
        sg.set_value(p, sg.get_value(p)-1)
        
    sg.set_value(k, None)
    
k = sg.get_min_index()
D[k] = C[N-1]

print(M)
print(' '.join(map(str,D)))

Solution (Python):
from collections import defaultdict
N = int(input())
dic = defaultdict(list)
for n in range(N - 1):
    a, b = map(int, input().split())
    dic[a].append(b)
    dic[b].append(a)
c_list = sorted(map(int, input().split()))
M = sum(c_list[:-1])
d_list = [False] * N
for i in range(1, N + 1):
    if len(dic[i]) == 1:
        break
blank = N
q = [i]
while blank:
    i = q.pop(0)
    if not d_list[i - 1]:
        q += dic[i]
        d_list[i - 1] = c_list[blank - 1]
        blank -= 1
print(M)
print(' '.join(map(str, d_list)))

Solution (Python):
N=int(input())
E=[list(map(int,input().split())) for i in range(N-1)]
C=list(map(int,input().split()))
C.sort(reverse=True)

print(sum(C[1:]))

ELIST=[[] for i in range(N+1)]
for a,b in E:
    ELIST[a].append(b)
    ELIST[b].append(a)

from collections import deque
QUE=deque([1])
i=0
ANS=[-1]*(N+1)
while QUE:
    x=QUE.pop()
    ANS[x]=C[i]
    i+=1

    for to in ELIST[x]:
        if ANS[to]==-1:
            QUE.append(to)
            ANS[to]=0

print(*ANS[1:])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

n = int(input())
e = []
tree = [[] for i in range(n)]
w = [-1] * n
for i in range(n-1):
    a, b = lmi()
    a -= 1; b -= 1
    e.append([a, b])
    tree[a].append(b)
    tree[b].append(a)

c = lmi()
c.sort()

def dfs(x):
    if len(c) == 0:
        return
    if w[x] == -1:
        w[x] = c.pop()
        for i in tree[x]:
            dfs(i)

dfs(0)

print(sum([min(w[i],w[j]) for i, j in e]))
print(' '.join(map(str, w)))

Solution (Python):


import itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

def main():
    N = int(input())

    edges = defaultdict(list)
    edges_l = []
    for _ in range(N-1):
        a, b = map(int, input().split())

        edges_l.append((a-1, b-1))
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)

    C = list(map(int, input().split()))
    C.sort(reverse=True)
    
    
    used = [False] * N
    ans = [0] * N
    count = 0
    que = list()
    que.append(0)
    while que:
        index = que.pop()
        if not used[index]:
            
            ans[index] = C[count]
            used[index] = True
            count += 1

        
        for nei in edges[index]:
            if not used[nei]:
                que.append(nei)

    val = 0
    for a, b in edges_l:
        node_val = min(ans[a], ans[b])
        val += node_val

    print(val)
    print(' '.join(map(str, ans)))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

n = int(input())
A = [[int(i) for i in input().split()] for j in range(n - 1)]
C = [int(i) for i in input().split()]
C.sort(reverse=True)

E = [[] for i in range(n + 1)]
V = [0] * (n + 1)

for a, b in A:
    E[a].append(b)
    E[b].append(a)

t = 0
ma = 0

for i, e in enumerate(E):
    if len(e) > ma:
        t = i
        ma = len(e)

Q = deque()
Q.append((t, 0))
i = 0
visited = [False] * (n + 1)
ans = 0

while Q:
    v, c = Q.popleft()
    if visited[v]:
        continue
    visited[v] = True
    V[v] = C[i]
    ans += min(c, C[i])
    for e in E[v]:
        Q.append((e, C[i]))
    i += 1

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

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

d = [0]*N
d[0] = str(c.pop())
while e:
    a,b = e.popleft()
    if d[a] != 0 and d[b] == 0:
        d[b] = str(c.pop())
    elif d[a] == 0 and d[b] != 0:
        d[a] = str(c.pop())
    else:
        e.append((a,b))

print(' '.join(d))

Solution (Python):
from collections import deque

n = int(input())
tree = {i:[] for i in range(1, n+1)}
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
c = list(map(int, input().split()))

c = sorted(c, reverse = True)
d = [-1]*(n+1)
que = deque([1])
ic = 0
while len(que) > 0:
    x = que.pop()
    d[x] = c[ic]
    ic += 1
    for y in tree[x]:
        if d[y] < 0:
            que.append(y)
print(sum(c[1:]))
print(*d[1:])

Solution (Python):
from collections import deque

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)

ans=0 
used=[0]*(N+1)
number=[0]*(N+1)
que=deque([1])

ccount=0
while que:
  v=que.popleft()
  if number[v]==0:
    number[v]=c[ccount]
    ccount+=1
  for e in G[v]:
    if used[e]:
      continue
    if number[e]==0:
      number[e]=c[ccount]
      ccount+=1
    ans+=min(number[v],number[e])
    que.append(e)
    used[v]=1
print(ans)
print(*number[1:])

Solution (Python):
from collections import deque

n = int(input())
tree = {i:[] for i in range(1, n+1)}
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
c = list(map(int, input().split()))

c = sorted(c, reverse = True)
d = [-1]*(n+1)
que = deque([1])
ic = 0
while len(que) > 0:
    x = que.popleft()
    d[x] = c[ic]
    ic += 1
    for y in tree[x]:
        if d[y] < 0:
            que.append(y)
print(sum(c[1:]))
print(*d[1:])

Solution (Python):
def d_maximum_sum_of_minimum(N, Nodes, C):
    
    import sys
    sys.setrecursionlimit(10**6)

    int_list = list(sorted(C))
    graph = [[] for _ in range(N)]
    for u, v in Nodes:  
        graph[u - 1].append(v - 1)
        graph[v - 1].append(u - 1)

    def traverse_tree(parent, current, ret=[0] * N):
        """各頂点にCの値が大きなもの順に書き込んでいく"""
        def dfs(p, c):
            ret[c] = int_list.pop()
            for next_edge in graph[c]:
                if next_edge != p:  
                    dfs(c, next_edge)
        dfs(parent, current)
        return ret
    tmp = traverse_tree(-1, 0)
    return str(sum(tmp[1:])) + '\n' + ' '.join(map(str, tmp))

N = int(input())
Nodes = [[int(i) for i in input().split()] for j in range(N - 1)]
C = [int(i) for i in input().split()]
print(d_maximum_sum_of_minimum(N, Nodes, C))

Solution (Python):
import collections
 
 
class Node(object):
 
  def __init__(self):
    self.value = 0
    self.edges = [] 
 
def main():
  n = int(input())
  nodes = [Node() for _ in range(n)]
 
  for _ in range(n - 1):
    a, b = map(int, input().split())
    nodes[a - 1].edges.append(nodes[b - 1])
    nodes[b - 1].edges.append(nodes[a - 1])
 
  values = list(map(int, input().split()))
  values.sort(reverse=True)
 
  print(sum(values[1:]))
 
  queue = collections.deque()
  queue.append(nodes[0])
  index = 0
 
  while len(queue) != 0:
    node = queue.popleft()
    node.value = values[index]
    index += 1
 
    queue.extend(n for n in node.edges if n.value == 0)
 
  print(' '.join(str(n.value) for n in nodes))
 
 
if __name__ == '__main__':
  main()

Solution (Python):
from collections import deque
ov = deque([0])
n = int(input())
e = [[int(_)-1 for _ in input().split()] for __ in range(n-1)]
c = sorted([int(_) for _ in input().split()])
m = sum(c[:-1])
d = [0 for _ in range(n)]
adv = [[] for _ in range(n)]
for i in range(n-1):
    adv[e[i][0]].append(e[i][1])
    adv[e[i][1]].append(e[i][0])
while len(ov) > 0:
    i = ov.popleft()
    d[i] = c.pop()
    for j in range(len(adv[i])):
        if d[adv[i][j]] == 0:
            ov.append(adv[i][j])
print(m); print(' '.join([str(_) for _ in d]))

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

def add_node_2_tree_dic(tree_dic, x, y):
    if x not in tree_dic:
        tree_dic[x] = [y]
    else:
        tree_dic[x].append(y)



N = int(input())
tree_dic = {}
for _ in range(N-1):
    a, b = map(int, input().split())
    add_node_2_tree_dic(tree_dic, a, b)
    add_node_2_tree_dic(tree_dic, b, a)

c_lst = list(map(int, input().split()))
c_lst.sort()
ans_lst = [0]*N

def search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst):
    next_node_lst = tree_dic[current_node][:]

    for next_node in next_node_lst:
        c = c_lst.pop()
        ans += c
        ans_lst[next_node - 1] = c

        tree_dic[current_node].remove(next_node)    
        tree_dic[next_node].remove(current_node)

        if len(tree_dic[current_node]) == 0:
            del tree_dic[current_node]
        if len(tree_dic[next_node]) == 0:
            del tree_dic[next_node]
        else:   
            ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)

    return ans


ans = 0
current_node = 1
ans_lst[0] = c_lst.pop()
ans = search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst)


ans_str = ""
for i in range(N):
    ans_str += str(ans_lst[i])
    if i != N - 1:
        ans_str += " "


print(ans)
print(ans_str)

Solution (Python):
from collections import deque
N=int(input())
G=[[] for i in range(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)
j=0
for i in range(N):
    if len(G[i])>len(G[j]):
        j=i
c=sorted([int(i) for i in input().split()])
M=sum(c)-max(c)
d=[-1 for i in range(N)]
q=deque([j])
while(len(q)>0):
    r=q.popleft()
    d[r]=c.pop()
    for p in G[r]:
        if d[p]==-1:
            q.appendleft(p)
print(M)
print(" ".join([str(i) for i in d]))

Solution (Python):
from collections import deque
N=int(input())
G=[[] for i in range(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)
j=0
for i in range(N):
    if len(G[i])>len(G[j]):
        j=i
c=sorted([int(i) for i in input().split()])
M=sum(c)-max(c)
d=[-1 for i in range(N)]
q=deque([j])
while(len(q)>0):
    r=q.popleft()
    d[r]=c.pop()
    for p in G[r]:
        if d[p]==-1:
            q.appendleft(p)
print(M)
print(" ".join([str(i) for i in d]))

Solution (Python):
from collections import deque
N=int(input())
A=[0 for i in range(N-1)]
B=[0 for i in range(N-1)]
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    A[i],B[i]=a,b
    G[a].append(b)
    G[b].append(a)
j=0
for i in range(N):
    if len(G[i])>len(G[j]):
        j=i
c=sorted([int(i) for i in input().split()])
M=sum(c)-max(c)
d=[-1 for i in range(N)]
q=deque([j])
while(len(q)>0):
    r=q.popleft()
    d[r]=c.pop()
    for p in G[r]:
        if d[p]==-1:
            q.appendleft(p)
print(M)
print(" ".join([str(i) for i in d]))

Solution (Python):
from collections import deque
N=int(input())
A=[0 for i in range(N-1)]
B=[0 for i in range(N-1)]
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    A[i],B[i]=a,b
    G[a].append(b)
    G[b].append(a)
j=0
for i in range(N):
    if len(G[i])>len(G[j]):
        j=i
c=sorted([int(i) for i in input().split()])
d=[-1 for i in range(N)]
q=deque([j])
while(len(q)>0):
    r=q.popleft()
    d[r]=c.pop()
    for p in G[r]:
        if d[p]==-1:
            q.appendleft(p)
M=0
for i in range(N-1):
    M+=min(d[A[i]],d[B[i]])
print(M)
print(" ".join([str(i) for i in d]))

Solution (Python):
import heapq

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


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

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


L = list(map(lambda x: -int(x), input().split()))
heapq.heapify(L)


score = -sum(L)+min(L)



node = [-1]*N


leaf = -1
for i, a in enumerate(adj):
    if len(a) == 1:
        leaf = i
        break


Q = [leaf]
while Q:
    cur = Q.pop()
    for a in adj[cur]:
        if node[a] == -1:  
            node[a] = - heapq.heappop(L)
            Q.append(a)
print(score)
print("\n".join(map(str, node)))

Solution (Python):
import heapq

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


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

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

L = list(map(lambda x: -int(x), input().split()))
heapq.heapify(L)
print(-sum(L[1:]))


node = [-1]*N


leaf = -1
for i, a in enumerate(adj):
    if len(a) == 1:
        leaf = i
        break

Q = [leaf]
while Q:
    cur = Q.pop()
    for a in adj[cur]:
        if node[a] == -1:
            node[a] = - heapq.heappop(L)
            Q.append(a)
print("\n".join(map(str, node)))

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

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

score = sum(C) - max(C)
C.sort(reverse=True)
C = deque(C)
con = [[] for _ in range(N + 1)]
ans = [0 for i in range(N + 1)]

for ab in AB:
    a, b = ab
    con[a].append(b)
    con[b].append(a)


def dfs(x):
    if len(C) == 0:
        return
    if ans[x] == 0:
        ans[x] = C[0]
        C.popleft()
        for c in con[x]:
            dfs(c)


dfs(1)
ans = list(map(str, ans))
print(score)
print(' '.join(ans[1:]))

Solution (Python):
*D, = open(0)
n = int(D[0])

edge = [[] for _ in range(n+1)]
v_val = [0 for _ in range(n+1)]

dist = {}

for i in range(1, n):
    a, b = map(int, D[i].split())
    edge[a].append(b)
    edge[b].append(a)
c = list(map(int, D[n].split()))
c = sorted(c, reverse=True)

start = None
for i in range(1,len(edge)):
    if len(edge[i])==1:
        start = i
        break

        
import sys
sys.setrecursionlimit(10**7)


def visit(edge, start, visited, order):
    visited[start] = True
    order.append(start)
    
    for node in edge[start]:
        if not visited[node]:
            visit(edge, node, visited, order)
    
    return 

visited = [False for _ in range(len(edge))]
order = []
visit(edge, start, visited, order)


v_val = [0 for _ in range(len(c)+1)]
for i, it in enumerate(order):
    v_val[it] = c[i]
    
print(sum(c[1:]))
print(' '.join(map(str, v_val[1:])))

Solution (Python):
*D, = open(0)
n = int(D[0])
 
edge = [[] for _ in range(n+1)]
v_val = [0 for _ in range(n+1)]
 
dist = {}
 
for i in range(1, n):
    a, b = map(int, D[i].split())
    edge[a].append(b)
    edge[b].append(a)
c = list(map(int, D[n].split()))
 
c = sorted(c, reverse=True)
 

def findLeaf(edge, start=1):
    visited = [False for _ in range(len(edge))]
    next_v = edge[start]
    visited[start] = True
    count = 0
    
    while len(next_v) > 0:
        new_v = []
        for it in next_v:
    
            leaf = it
            for v in edge[it]:
                if not visited[v]:
                    new_v.append(v)
            visited[it] = True
        next_v = new_v
        count += 1
 
    return leaf, count
 
 

def findD(edge):
    leaf, _ = findLeaf(edge, 1)
    leaf, count = findLeaf(edge, leaf)
    return count
 

def findCenter(edge):
    leaf, _ = findLeaf(edge, 1)
    leaf, d = findLeaf(edge, leaf)
    r = d//2
 
    visited = [False for _ in range(len(edge))]
    start = leaf
    next_v = edge[start]
    
    visited[start] = True
    count = 0
 
    while not r == count+1:
        new_v = []
        for it in next_v:
    
            leaf = it
            for v in edge[it]:
                if not visited[v]:
                    new_v.append(v)
            visited[it] = True
        next_v = new_v
        count += 1
        
    center = []
    for it in next_v:
        if len(edge[it]) > 1:
            center.append(it)
    return center
 
 
def calcCost(D, v_val):
    total = 0
    
    n = int(D[0])
    for i in range(1, n):
        a, b = map(int, D[i].split())
        total += min(v_val[a], v_val[b])
        
    return total
 
 
max_val = 0
max_v = 0
l, _ = findLeaf(edge)
for center in [l]:
    order = []
    start = center
    visited = [False for _ in range(len(edge))]
    next_v = edge[start]
    visited[start] = True
    order.append(center)
 
    
    while len(next_v) > 0:
        new_v = []
        for it in next_v:
    
            leaf = it
            for v in edge[it]:
                if not visited[v]:
                    new_v.append(v)
            visited[it] = True
            order.append(it)
        next_v = new_v
        
    
    v_val = [0 for _ in range(len(c)+1)]
    for i, it in enumerate(order):
        v_val[it] = c[i]
 
    val = calcCost(D, v_val)
    if val > max_val:
        max_val = val
        max_v = v_val
 
        
print(max_val)
print(' '.join(map(str, max_v[1:])))

Solution (Python):
*D, = open(0)
n = int(D[0])

edge = [[] for _ in range(n+1)]
v_val = [0 for _ in range(n+1)]

dist = {}

for i in range(1, n):
    a, b = map(int, D[i].split())
    edge[a].append(b)
    edge[b].append(a)
c = list(map(int, D[n].split()))
c = sorted(c, reverse=True)

from collections import deque
visited = [False for _ in range(len(edge))]
start = 1
que = deque()
que.append(start)
order = []
order.append(start)
visited[start] = True

while que:
    node = que.popleft()
    for it in edge[node]:
        if not visited[it]:
            order.append(it)
            visited[it] = True
            que.append(it)

v_val = [0 for _ in range(len(c)+1)]
for i, it in enumerate(order):
    v_val[it] = c[i]

print(sum(c[1:]))
print(' '.join(map(str, v_val[1:])))

Solution (Python):
from collections import deque, defaultdict

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

c_list = list(map(int, input().split()))
c_list.sort()
c_que = deque(c_list)

cnt = defaultdict(int)
outs = defaultdict(list)
for a, b in ab:
    cnt[a - 1] += 1
    cnt[b - 1] += 1
    outs[a - 1].append(b - 1)
    outs[b - 1].append(a - 1)

top = 0
tar = defaultdict(lambda: 0)

import sys

sys.setrecursionlimit(10 ** 9)
visit = [False] * N


def dfs(start):
    tmp = []
    visit[start] = True
    for v2 in outs[start]:
        if visit[v2]:
            continue
        q = c_que.pop()
        tar[v2] = q
        tmp.append(v2)
    for v2 in tmp:
        if visit[v2]:
            continue
        dfs(v2)


tar[top] = c_que.pop()
dfs(top)
ans = 0
for a, b in ab:
    a -= 1
    b -= 1
    ans += min(tar[a], tar[b])
print(ans)
for i in range(N):
    print(tar[i], end=" ")

Solution (Python):
from collections import deque, defaultdict

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

c_list = list(map(int, input().split()))
c_list.sort()
c_que = deque(c_list)

cnt = defaultdict(int)
outs = defaultdict(list)
for a, b in ab:
    cnt[a - 1] += 1
    cnt[b - 1] += 1
    outs[a - 1].append(b - 1)
    outs[b - 1].append(a - 1)

cnt = sorted(cnt.items(), key=lambda x: x[1])
top = cnt[0][0]
tar = defaultdict(lambda: 0)

import sys

sys.setrecursionlimit(10 ** 9)
visit = [False] * N


def dfs(start):
    tmp = []
    visit[start] = True
    for v2 in outs[start]:
        if visit[v2]:
            continue
        q = c_que.pop()
        tar[v2] = q
        tmp.append(v2)
    for v2 in tmp:
        if visit[v2]:
            continue
        dfs(v2)


tar[top] = c_que.pop()
dfs(top)
ans = 0
for a, b in ab:
    a -= 1
    b -= 1
    ans += min(tar[a], tar[b])
print(ans)
for i in range(N):
    print(tar[i], end=" ")