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 collections
import sys
input = sys.stdin.readline
n=int(input())
E=[[] for i in range(n)]
EE=[]
P=collections.defaultdict(int)
for i in range(n-1):
  a,b=map(int,input().split())
  E[a-1]+=[b-1]
  E[b-1]+=[a-1]
  EE.append([a,b])
  P[a-1]+=1
  P[b-1]+=1
C=[int(i) for i in input().split()]
C.sort(reverse=True)
P=sorted(P.items(), key=lambda x:x[1],reverse=True)
CC=[0]*n
stack=[P[0][0]]
CC[P[0][0]]=C[0]
ct_p,ct_c=1,1
while stack:
  label=stack.pop(-1)
  for i in E[label]:
    if CC[i]==0:
      CC[i]=C[ct_c]
      ct_c+=1
      stack+=[i]
ans=0
for i in range(n-1):
  a,b=EE[i][0],EE[i][1]
  ans+=min(CC[a-1],CC[b-1])
print(ans)
print(*CC)

Solution (Python):

"""
Created on Sat Jun  1 20:46:37 2019

@author: Yamazaki Kenichi
"""
from collections import deque

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

C.sort(reverse=True)

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

for b in ab:
    T[b[1]].append(b[0])
    T[b[0]].append(b[1])

ans = [-1 for i in range(N+1)]
q = deque(T[1])
ans[1] = C[0]

i = 0
while len(q) > 0:
    tmp = q.pop()
    if ans[tmp] == -1:
        ans[tmp] = C[i+1]
        for c in T[tmp]:
            q.append(c)

        i += 1

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

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

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

if n==1:
    print(0)
    print(c[0])
    exit()

dic = {}
for i in range(n):
    dic[i] = []

cnt = [0]*n
for a,b in ab:
    dic[a].append(b)
    dic[b].append(a)
    cnt[a] += 1
    cnt[b] += 1

c_idx = 0
res = 0
res_arr = [""]*n
used = [0]*n
def f(idx):
    global c_idx, res, used
    used[idx] = 1
    res_arr[idx] = str(c[c_idx])
    for x in dic[idx]:
        if used[x] == 0:
            c_idx += 1
            res += c[c_idx]
            f(x)

f(cnt.index(1))
print(res)
print(" ".join(res_arr))

Solution (Python):
N = int(input())
Node = [[] for _ in range(N+1)]
P = []
for _ in range(N-1):
    a, b = map(int, input().split())
    Node[a].append(b)
    Node[b].append(a)
    P.append((a, b))
C = sorted(list(map(int, input().split())))
check = [0]*(N+1)
value = [0]*(N+1)
Q = [1]
cnt = 0
while Q:
    u = Q.pop()
    check[u] = 1
    value[u] = C[N-1-cnt]
    cnt += 1
    for v in Node[u]:
        if check[v]:
            continue
        else:
            Q.append(v)

ans = 0
for a, b in P:
    ans += min(value[a], value[b])

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

Solution (Python):
def main():
    import sys,heapq
    input = sys.stdin.readline
    n = int(input())
    edge = [[] for i 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)
    
    c2 = list(map(int,input().split()))
    
    c = sorted(c2)
    
    h = []
    for i in range(n):
        heapq.heappush(h,[len(edge[i]),i])
    
    used = [False]*n

    p = [len(edge[i]) for i in range(n)]
    res = 0
    ans = [-1]*n
    for i in range(n):
        q = 0
        while len(h)>0:
            q,ten = heapq.heappop(h)
            if not used[ten]:
                used[ten] = True
                ans[ten] = c[i]
                break
        res += q*c[i]
        for e in edge[ten]:
            if not used[e]:
                p[e]-=1
                heapq.heappush(h,[p[e],e])
    print(res)


    for e in ans:
        print(e,end = ' ')

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict, deque


def main():
    input = sys.stdin.readline
    d = defaultdict(list)
    N = int(input())
    ans = [0] * N
    for _ in range(N-1):
        a, b = map(int, input().split())
        d[a-1].append(b-1)
        d[b-1].append(a-1)

    C = list(map(int, input().split()))
    C = sorted(C, key=lambda x: -x)
    score = sum(C[1:])

    ans[0] = C[0]
    cnt = 1
    visited = set([0])
    q = deque()
    q.extend(d[0])
    while len(q) > 0:
        a = q.popleft()

        if a in visited:
            continue

        ans[a] = C[cnt]
        visited.add(a)
        cnt += 1

        q.extend(d[a])

    print(score)
    print(*ans, sep=' ')


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque, defaultdict

n = int(raw_input())

edges = []
g = [[] for i in xrange(n)]

d = [0 for i in xrange(n)]
for i in xrange(n - 1):
    (a, b) = map(int, raw_input().split())
    a -= 1
    b -= 1
    edges.append((a, b))
    g[a].append(b)
    g[b].append(a)
    d[a] += 1
    d[b] += 1

vs = sorted(map(int, raw_input().split()))
vidx = 0
ns = [-1 for i in xrange(n)]

q = deque()

for i in xrange(n):
    if d[i] == 1:
        q.append(i)

while q:
    cur = q.popleft()
    
    ns[cur] = vs[vidx]
    vidx += 1

    for nxt in g[cur]:
        d[nxt] -= 1
        
        if d[nxt] == 1:
            q.append(nxt)

ans = 0
for (a, b) in edges:
    ans += min(ns[a], ns[b])
print ans

print ' '.join(map(str, ns))

Solution (Python):
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)]
C = list(map(int, input().split()))
cnt = [[0, i] for i in range(N+1)]
adj = [[] for _ in range(N+1)]
for a, b in AB:
    cnt[a][0] += 1
    cnt[b][0] += 1
    adj[a].append(b)
    adj[b].append(a)
cnt.sort(reverse=True)
C.sort(reverse=True)
D = [0]*N
from collections import deque
used = [False] * (N+1)
n_used = 0
def bfs(s):
    global n_used, used
    q = deque()
    q.append(s)
    while q:
        v = q.pop()
        if used[v]:
            continue
        used[v] = True
        D[v-1] = C[n_used]
        n_used += 1
        for nv in adj[v]:
            if not used[nv]:
                q.append(nv)
    return
bfs(cnt[0][1])
ans = 0
for a, b in AB:
    ans += min(D[a-1], D[b-1])

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

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

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

maxdeg = root = 0
for i,ee in enumerate(es):
    if len(ee) > maxdeg:
        maxdeg = len(ee)
        root = i

hq = [(-maxdeg, root)]
heapq.heapify(hq)

ans = [None] * N
ci = 0
ansval = -C[0]
while hq:
    d,v = heapq.heappop(hq)
    ans[v] = C[ci]
    ansval += C[ci]
    ci += 1
    for to in es[v]:
        if ans[to] is not None: continue
        heapq.heappush(hq, (-len(es[to]),to))

print(ansval)
print(*ans)

Solution (Python):


from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict
import math


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def gcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    ret = math.factorial(x)
    ret = ret // (math.factorial(x - y) * math.factorial(y))

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)





def main():
    n = intin()
    ablist = intinl(n - 1)
    clist = intina()

    clist.sort()
    cidx = 0

    ptocount = defaultdict(int)
    linklist = make_linklist(ablist)

    for a, b in ablist:
        ptocount[a] += 1
        ptocount[b] += 1

    ansdict = {}

    while True:
        ptocount_next = {}
        for p, count in ptocount.items():

            if count <= 1:
                for q in linklist[p]:
                    if q not in ansdict:
                        if q in ptocount_next:
                            ptocount_next[q] -= 1
                        else:
                            ptocount_next[q] = ptocount[q] - 1
                ansdict[p] = clist[cidx]
                cidx += 1
            else:
                if p not in ptocount_next:
                    ptocount_next[p] = count

        if cidx >= n:
            break
        ptocount = ptocount_next

    ans = 0
    for a, b in ablist:
        ans += min(ansdict[a], ansdict[b])

    anslist = []
    for i in range(1, n + 1):
        anslist.append(str(ansdict[i]))

    print(ans)
    print(' '.join(anslist))


if __name__ == '__main__':
    main()

Solution (Python):

import sys
input = sys.stdin.readline
N =int(input())
adj = [set() for i in range(N)]

lis =[[int(i)-1 for i in input().split()]for _ in range(N-1)]

ans =["" for i in range(N)]

D =[int(i) for i in input().split()]
D.sort()
wa = sum(D[:-1])

que =[]

for (i,j) in lis:
    adj[i].add(j)
    adj[j].add(i)

for i,se in enumerate(adj):
    if len(list(se))==1:
        que.append(i)

for _ in range(N-1):
    i = que.pop(0)
    j = list(adj[i])[0]
    ans[i] = str(D.pop(0))
    adj[j].remove(i)
    if len(list(adj[j]))==1:
        que.append(j)
i =que.pop(0)
ans[i] = str(D.pop(0))

print(wa)
print(" ".join(ans))

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

n = int(input())
edges = [[] for _  in range(n)]

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

height = [None for _ in range(n)]
root = 0
height[root] = 0

def build(node):
    for to in edges[node]:
        if height[to] == None:
            height[to] = height[node] + 1
            build(to)

build(root)

enum = [(-h, i) for i, h in enumerate(height)]
enum.sort()

tree = [None] * n
clst = sorted(map(int, input().split()))

for c, hi in zip(clst, enum):
    h, i = hi
    tree[i] = c

print(sum(clst[:-1]))
print(*tree)

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):
import sys
input=sys.stdin.readline
from collections import deque
n=int(input())
Edges=[[] for _ in range(n)]
Cnt=[0]*n
for _ in range(n-1):
    a,b=map(int,input().split())
    Edges[a-1].append(b-1)
    Edges[b-1].append(a-1)
C=list(map(int,input().split()))
C.sort()
print(sum(C)-C[-1])
Used=[False]*n
for i,e in enumerate(Edges):
    if len(e)==1:
        start=i
        break
Ans=[0]*n
q=deque()
q.append(start)
Used[start]=True
while q:
    v=q.popleft()
    Ans[v]=C.pop()
    for u in Edges[v]:
        if not Used[u]:
            Used[u]=True
            q.append(u)
print(*Ans)

Solution (Python):
n = int(input())
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
graph = defaultdict(list)
edge = []
for i in range(n-1):
  a, b = list(map(int, input().split()))
  edge.append((a, b))
  graph[a].append(b)
  graph[b].append(a)
c = list(map(int, input().split()))
c.sort(reverse=True)
visited = [0 for i in range(n+1)]
ans = [0 for i in range(n+1)]
score = 0

def dfs(x):
  visited[x] = 1
  for next_ in graph[x]:
    if visited[next_]:
      continue
    dfs(next_)
  if all(visited[i] for i in graph[x]):
    ans[x] = c.pop()
    return
  visited[x] = 0

dfs(1)
for a, b in edge:
  score += min(ans[a], ans[b])
print(score)
print(*ans[1:])

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

table = [[] for _ in range(N)]

for ai, bi in ab:
    table[ai - 1].append(bi - 1)
    table[bi - 1].append(ai - 1)


for i_root, row in enumerate(table):
    
    if len(row) > 1: break

from collections import deque

c.sort(key=lambda x: -x)


nodes = [None] * N

q = deque([(i_root, 0)])
nodes[i_root] = c[0]
idx_c = 1
while len(q) > 0:
    src, d = q.popleft()
    for dst in table[src]:
        if nodes[dst] == None:
            q.append((dst, d + 1))
            nodes[dst] = c[idx_c]
            idx_c += 1


print(sum(c) - c[0])
print(' '.join(map(str, nodes)))

Solution (Python):


import sys
sys.setrecursionlimit(1000000) 


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

print(sum(c)-max(c))

ko = [[] for i in [0]*n]

for a,b in ab:
    ko[a].append(b)
    ko[b].append(a)
    
ans = [0]*n
pt=0 
used = [0]*n



def dfs(x):
    global pt 
    used[x]=1
    
    

    ans[x] = c[pt]
    pt+=1
    
    for i in ko[x]:
        if used[i] == 0:
            dfs(i)
        
dfs(0)

print(*ans)

Solution (Python):
N = int(input())
E = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
C = sorted(map(int, input().split()), reverse=True)

Closed = [False] * (N+1)
q = [1]
A = [0] * (N)
Closed[1] = True
for c in C:
    v = q.pop()
    A[v-1] = c
    for u in E[v]:
        if not Closed[u]:
            q.append(u)
            Closed[u] = True
print(sum(C[1:]))

print(*A)

Solution (Python):
import sys
input = sys.stdin.readline
from sys import setrecursionlimit
setrecursionlimit(10**9)

def inpl(): return list(map(int, input().split()))
N = int(input())
D = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = inpl()
    D[a].append(b)
    D[b].append(a)

C = sorted(inpl())
ans = [-1]*(N+1)
ans[1] = C.pop()
score = 0
def dfs(i):
    global score
    for j in D[i]:
        if ans[j] == -1:
            ans[j] = C.pop()
            score += min(ans[i], ans[j])
            dfs(j)

dfs(1)
print(score)
print(*ans[1:])

Solution (Python):
import sys

def main():
    sys.setrecursionlimit(1000000) 
    buf = input()
    N = int(buf)
    edge = dict()
    ab = []
    for i in range(N):
        edge[i] = [] 
    for i in range(N-1):
        buf = input()
        buflist = list(buf.split())
        a = int(buflist[0])-1 
        b = int(buflist[1])-1 
        edge[a].append(b)
        edge[b].append(a)
        ab.append((a, b))
    buf = input()
    buflist = buf.split()
    c = list(map(int, buflist))
    c = list(sorted(c, reverse=True))
    point = 0
    assigned = []
    weight = []
    for i in range(N):
        assigned.append(False)
        weight.append(0)
    start = None
    for k, v in edge.items():
        if len(v) == 1:
            start = k
            break
    recursion_graph(point, start, edge, c, weight, assigned)
    total = 0
    for x in ab:
        total += min(weight[x[0]], weight[x[1]])
    print(total)
    print(' '.join(list(map(str, weight))))

def recursion_graph(point, k, edge, c, weight, assigned):
    weight[k] = c[point]
    assigned[k] = True
    point += 1
    for node in edge[k]:
        if not assigned[node]:
            point = recursion_graph(point, node, edge, c, weight, assigned)
    return point

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

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

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



cs = sorted(c)


ansd=[0]*(n)
score=0

stack = deque()
stack.append(1)
ansd[0]=cs.pop()
visitted=[]

while stack:
    cur = stack.popleft()
    visitted.append(cur)
    for v in tree[cur]:
        if v in visitted:
            continue
        stack.append(v)
        ansd[v-1]=cs.pop()
        score += min(ansd[cur-1], ansd[v-1])

print(score)
print(*ansd, sep=' ')

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N = II()
    edges = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = LI_()
        edges[a].append(b)
        edges[b].append(a)
    C = LI()
    C.sort(reverse=True)
    visited = [0] * N
    D = [0] * N
    def solve(v, i):
        visited[v] = 1
        D[v] = C[i]
        for to in edges[v]:
            if not visited[to]:
                i += 1
                i = solve(to, i)
        return i
    solve(0, 0)
    M = sum(C[1:])
    print(M)
    print(*D)

    return

main()

Solution (Python):

from collections import deque

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

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

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



cs = sorted(c)


ansd=[0]*(n)
score=0

stack = deque()
stack.append(1)
ansd[0]=cs.pop()
visitted=[]

while stack:
    cur = stack.popleft()
    visitted.append(cur)
    for v in tree[cur]:
        if v in visitted:
            continue
        stack.append(v)
        ansd[v-1]=cs.pop()
        score += min(ansd[cur-1], ansd[v-1])

print(score)
print(*ansd, sep=' ')

Solution (Python):
n=int(input())
m = {}
cnt = [0] * (n+1)
edges = []

for i in range(n-1):
    a,b=map(int, input().split())
    edges.append((a, b))
    m[a] = m.get(a, set())
    m[a].add(b)
    m[b] = m.get(b, set())
    m[b].add(a)
    cnt[a] += 1
    cnt[b] += 1

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

from collections import deque

q = deque()
current = 0
ans = [0] * (n+1)
for i in range(1, n+1):
    if cnt[i] == 1:
        q.append(i)

while q:
    node = q.pop()
    ans[node] = c[current]
    current += 1
    for i in m[node]:
        cnt[i] -= 1
        if cnt[i] == 1:
            q.append(i)

print(sum(min([ans[i[0]], ans[i[1]]]) for i in edges))
for i in range(1, n+1):
    print(ans[i])

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

n = int(input())

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

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

value = 0
ans = [0] * n
memo = [0] * n
q = deque([0])
i = 0

while q:
    v = q.popleft()
    ans[v] = c[i]
    memo[v] = 1
    if i > 0:
        value += c[i]
    i += 1
    for nv in graph[v]:
        if memo[nv] == 1:
            continue
        memo[nv] = 1
        q.append(nv)

print(value)
print(*ans)

Solution (Python):
import os
import sys
import numpy as np

sys.setrecursionlimit(2147483647)
INF = float('inf')

if os.getenv('LOCAL'):
    sys.stdin = open('_in.txt')

N = int(sys.stdin.readline())
A, B = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N - 1)]))
C = list(map(int, sys.stdin.readline().split()))


def shortest_path(start, graph):
    stack = [(start, 0)]
    dists = [INF] * (N + 1)
    dists[start] = 0
    while stack:
        v, vw = stack.pop()
        for u, w in graph[v]:
            if dists[u] == INF:
                dists[u] = vw + w
                stack.append((u, vw + w))
    return dists



graph = [[] for _ in range(N + 1)]
for a, b in zip(A, B):
    graph[a].append((b, 1))
    graph[b].append((a, 1))


root = 1
distances = shortest_path(root, graph)[1:]


ans = np.zeros(N, dtype=int)
C.sort(reverse=True)
for i, di in enumerate(np.argsort(distances)):
    ans[di] = C[i]

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

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, AB, C):
    def s(C):
        ret = 0
        for a, b in AB:
            ret += min(C[a-1], C[b-1])
        return ret

    vc = Counter()
    g = defaultdict(list)
    for a, b in AB:
        vc[a] += 1
        vc[b] += 1
        g[a].append(b)
        g[b].append(a)
    v = sorted(list(vc.items()), key=lambda x: x[1])[0]
    C.sort()
    ans = [-1] * (N+1)
    ans[v[0]] = C.pop()

    q = deque([v[0]])
    while q:
        v = q.popleft()
        for u in g[v]:
            if ans[u] == -1:
                ans[u] = C.pop()
                q.append(u)
    ans = ans[1:]
    print(s(ans))
    print(' '.join(map(str, ans)))


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N-1)]
    C = read_int_n()
    (slv(N, AB, C))


if __name__ == '__main__':
    main()

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
nodes=[[] for i in range(N)]
for i in range(N-1):
    a,b=MAP()
    nodes[a-1].append(b-1)
    nodes[b-1].append(a-1)
C=LIST()

C.sort(reverse=True)

ans=[0]*N
cnt=0
def rec(cur):
    global cnt
    if ans[cur]:
        return
    ans[cur]=C[cnt]
    cnt+=1
    for nxt in nodes[cur]:
        rec(nxt)
rec(0)

if N==1:
    print(0)
else:
    print(sum(C[1:]))
print(*ans)

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

tree = [[] for i in range(n)]
connect = [0 for i in range(n)]

inf = float('inf')

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

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

c.sort()

m = 0
d = [0 for i in range(n)]

for i in range(n):
    ind = connect.index(min(connect))
    m += max(connect[ind] * c[i], 0)
    d[ind]=c[i]
    connect[ind] = inf
    for j in range(len(tree[ind])):
        connect[tree[ind][j]]-=1
        if connect[j]==0:
            connect[j] = inf

print(m)
print(' '.join(map(str,d)))

Solution (Python):
def main():

    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**5)
    from collections import deque


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

    C = deque(sorted(map(int,input().split()), reverse=True))

    nodes = [-1]*N

    def dfs(v=0,pv=-1):
        for nv in ad[v]:
            if nv == pv:
                continue
            dfs(nv,v)
        nodes[v] = C.pop()

    dfs()
    ans = 0

    for a,b in edges:
        ans += min(nodes[a],nodes[b])

    print(ans)
    print(*nodes)


if __name__ == "__main__":
    main()

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

def dfs(v):
    vs.append(v)
    useds[v] = True
    for v2 in adjL[v]:
        if not useds[v2]:
            dfs(v2)

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

cs.sort(reverse=True)

vs = []
useds = [False] * N
dfs(0)

anss = [0] * N
for v, c in zip(vs, cs):
    anss[v] = c

score = 0
for A, B in ABs:
    score += min(anss[A], anss[B])

print(score)
print(*anss)

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

n = int(input())
ab = [[int(item) for item in input().split()] for _ in range(n-1)]
c = [int(item) for item in input().split()]
c.sort()
c.reverse()
sum_score = sum(c[1:])

edge = [[] for _ in range(n)]
score = [0] * n

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

it = 0
def dfs(f ,n):
    global it
    score[n] = c[it]
    it += 1
    for item in edge[n]:
        if item == f:
            continue
        dfs(n, item)
    return True

dfs(-1, 0)
print(sum_score)
print(" ".join([str(item) for item in score]))

Solution (Python):
N = int(input())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]
*C, = map(int,input().split())

connect = [[] for _ in [0]*N]
for a,b in AB:
    connect[a-1].append(b-1)
    connect[b-1].append(a-1)
d = [-1]*N
d[0] = 0
q = [0]
while q:
    qq = []
    for i in q:
        for j in connect[i]:
            if d[j] == -1:
                d[j] = d[i]+1
                qq.append(j)
    q = qq

o = sorted(zip(d,range(N)),key =lambda x:-x[0])
C.sort()
ans = [0]*N
for j,tmp in enumerate(o):
    d,i = tmp
    ans[i] = C[j]
print(sum(C)-C[-1])
print(*ans)

Solution (Python):
from collections import deque
import heapq
N = int(input())
T = [[] for i in range(N)]
Edge = []
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append(b)
    T[b].append(a)
    Edge.append((a, b))
C = sorted(list(map(int, input().split())))

out = [(len(T[i]), i) for i in range(N)]
out.sort(reverse=True)

P = [-1] * N
que = [out[0]]
while que:
    u, n = heapq.heappop(que)
    P[n] = C.pop()
    for to in T[n]:
        if not P[to] < 0:
            continue
        heapq.heappush(que, [len(T[to]), to])

ans = 0
for a, b in Edge:
    ans += min(P[a], P[b])

print(ans)
print(*P, sep=' ')

Solution (Python):
import sys

n = int(input())
lines = sys.stdin.readlines()
links = [set() for _ in [0] * n]
for line in lines[:n - 1]:
    a, b = list(map(int, line.split()))
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

ccc = list(map(int, lines[-1].split()))
ccc.sort(reverse=True)
ans = [-1] * n
ans_sum = 0
leaves = {i for i, l in enumerate(links) if len(l) == 1}

while leaves:
    v = leaves.pop()
    c = ccc.pop()
    ans[v] = c
    if not ccc:
        break
    ans_sum += c
    for u in links[v]:
        lu = links[u]
        lu.remove(v)
        if len(lu) == 1:
            leaves.add(u)

print(ans_sum)
print(*ans)

Solution (Python):
from heapq import heappush, heappop, heapify, heapreplace
from collections import defaultdict

class Solution:
    def main(self):
        N = int(input())
        A = []
        B = []
        path =  defaultdict(set)
        for _ in range(N-1):
            a, b = map(int, input().split())
            path[a-1].add(b-1)
            path[b-1].add(a-1)
            A.append(a-1)
            B.append(b-1)
        c = sorted(list(map(int, input().split())))

        cnt = [None] * N
        max_idx = 0
        max_val = 0
        for i in range(N):
            cnt[i] = len(path[i])
            if max_val < cnt[i]:
                max_val = cnt[i]
                max_idx = i

        stack = [max_val]
        res = [None] * N
        while stack:
            p = stack.pop(0)
            if res[p] == None:
                res[p] = c.pop()
                for n in path[p]:
                    stack.append(n)

        score = 0
        for a, b in zip(A, B):
            score += min(res[a], res[b])

        print(score)
        print(' '.join([str(v) for v in res]))


if __name__ == '__main__':
    Solution().main()