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,*t=map(int,open(0).read().split())
c=sorted(t[-n:])
e=[[]for _ in[0]*n]
for a,b in zip(t[:-n:2],t[1:-n:2]):e[a-1]+=b-1,;e[b-1]+=a-1,
q=[0]
f=q*n
while q:
 v=q.pop();n-=1;f[v]=c[n]
 for w in e[v]:q+=[w]*(f[w]<1)
print(sum(c[:-1]),*f)

Solution (Python):
from collections import defaultdict, deque

N = int(input())
adj_list = defaultdict(list)
E = []
V_number = [None]*N
for _ in range(N-1):
    a, b = map(int, input().split())
    E.append((a, b))
    adj_list[a].append(b)
    adj_list[b].append(a)
C = sorted(list(map(int, input().split())), reverse=True)
q = deque([1])
i = 0
while q:
    v = q.popleft()
    V_number[v-1] = C[i]
    i += 1
    for u in adj_list[v]:
        if V_number[u-1] is None:
            q.append(u)

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

Solution (Python):

N = int(input())
g = {i: [] for i in range(N)}
for i in range(N - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
c = list(map(int, input().split()))
c.sort()
print(sum(c[:-1]))
nums = [0] * N
stack = [0]
while stack:
    d = stack.pop()
    nums[d] = c.pop()
    for node in g[d]:
        if nums[node] == 0:
            stack.append(node)
print(' '.join(map(str, nums)))

Solution (Python):
n,*t=map(int,open(0).read().split())
c=sorted(t[-n:])
e=[[]for _ in[0]*n]
for a,b in zip(t[:-n:2],t[1:-n:2]):e[a-1]+=b-1,;e[b-1]+=a-1,
f=[0]*n
q=[0]
while q:
 v=q.pop();n-=1;f[v]=c[n]
 for w in e[v]:q+=[w]*(f[w]<1)
print(sum(c[:-1]),*f)

Solution (Python):
n,*t=map(int,open(0).read().split())
c=sorted(t[-n:])
print(sum(c[:-1]))
e=[[]for _ in[0]*n]
for a,b in zip(t[:-n:2],t[1:-n:2]):e[a-1]+=b-1,;e[b-1]+=a-1,
f=[0]*n
q=[0]
while q:
 v=q.pop();f[v]=c.pop()
 for w in e[v]:q+=[w]*(f[w]<1)
print(*f)

Solution (Python):
n,*t=map(int,open(0).read().split())
c=sorted(t[-n:])
print(sum(c[:-1]))
e={i:[]for i in range(n)}
for a,b in zip(t[:-n:2],t[1:-n:2]):e[a-1]+=b-1,;e[b-1]+=a-1,
f=[0]*n
q=[0]
while q:
 v=q.pop();f[v]=c.pop()
 for w in e[v]:q+=[w]*(f[w]<1)
print(*f)

Solution (Python):
n,*t=map(int,open(0).read().split())
c=sorted(t[-n:])
print(sum(c[:-1]))
e={i:[]for i in range(n)}
for a,b in zip(t[:-n:2],t[1:-n:2]):e[a-1]+=b-1,;e[b-1]+=a-1,
f=[0]*n
q=[0]
while q:
 v=q.pop();f[v]=c.pop()
 for w in e[v]:q+=[w]*(f[w]<1)
print(*f)

Solution (Python):

from collections import defaultdict

N = int(input())

ab = []
for _ in range(N - 1):
    ab.append(tuple(map(int, input().split())))
c = sorted(list(map(int, input().split())), reverse=True)

nodes = defaultdict(set)
for a, b in ab:
    nodes[a].add(b)
    nodes[b].add(a)

d = {}
done = set()
stack = [1]
ci = 0
node = 1
while stack:
    node = stack.pop()
    d[node] = c[ci]
    stack += list(nodes[node] - done)
    done.add(node)
    ci += 1

print(sum(c[1:]))
for i in range(N):
    print(d[i + 1], end=' ')
print()

Solution (Python):
from collections import deque

N = int(input())

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

for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    neighbors[a].append(b)
    neighbors[b].append(a)
c = list(map(int, input().split()))
sorted_c = sorted(c)
max_c = sorted_c[-1]

closed = [0 for _ in range(N)]
use = [0 for _ in range(N)]
q = deque()
q.append(0)
use[0] = sorted_c.pop()
M = 0


while len(q) > 0:
    parent = q.pop()
    closed[parent] = use[parent]
    for neighbor in neighbors[parent]:
        if closed[neighbor] == 0:
            c2 = use[neighbor] = sorted_c.pop()
            c1 = closed[parent]
            w = c1 if c1 < c2 else c2
            M += w
            q.append(neighbor)

print(M)
print(*use)

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
g = [[] for i in range(n)]

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

c = na()
c = sorted(c)

print(sum(c)-c[-1])

ans = [0]*n
st = [0]

while st:
  d = st.pop()
  ans[d] = c.pop()
  for v in g[d]:
    if ans[v] == 0:
      st.append(v)

print(' '.join([str(s) for s in ans]))

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

edge = [[] for i 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()))

hhh = c.copy()

c.sort(reverse=True)

w = [0] * n

w[0] = c.pop(0)

chk = [i for i in edge[0]]


while chk != []:
    node = chk.pop(0)
    if w[node] == 0:
        w[node] = c.pop(0)
        chk.extend(edge[node])

print(sum(hhh) - max(hhh))

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

Solution (Python):
N=int(input());g={i:[]for i in range(N)}
for i in range(N-1):a,b=map(int,input().split());g[a-1].append(b-1);g[b-1].append(a-1)
c=sorted(list(map(int,input().split())));n=[0]*N;s=[0];print(sum(c[:-1]))
while s:
 d=s.pop()
 n[d]=c.pop()
 for m in g[d]:
  if n[m]==0:
   s.append(m)
print(' '.join(map(str,n)))

Solution (Python):
N = int(input())
es = [[] for idx in range(N)]


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

h = [len(es[i]) for i in range(N)]


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


v = [-1] * N
cur = 0
ans = 0
for _ in range(N - 1):
    for target in range(N):
        
        if h[target] == 1:
            h[target] = 0
            v[target] = c[cur]
            ans += c[cur]
            cur += 1
            for nv in es[target]:
                h[nv] -= 1
            break
for target in range(N):
    if v[target] == -1:
        v[target] = c[cur]
print(ans)
print(*v, sep='\n')

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
 

def A():
    n = II()
    print((n-2)*180)
    return
 

def B():
    b = S()
    kati = b.count("o")
    kati += 15 - len(b)
    if kati >= 8:
        print("YES")
    else:
        print("NO")
    return
 

def C():
    return
 

def D():
    n = II()
    ab = LIR_(n-1)
    C = LI()
    C.sort()
    c = deque(C)
    edg = [[] for i in range(n)]
    for a, b in ab:
        edg[a].append(b)
        edg[b].append(a)
    for num,e in enumerate(edg):
        if len(e) == 1:
            start = num
            break
    q = deque()
    ans = [0 for i in range(n)]
    q.append(start)
    ans[start] = c.pop()

    while q:
        p = q.pop()
        for e in edg[p]:
            if not ans[e]:
                ans[e] = c.pop()
                q.append(e)
    anssum = 0
    for a, b in ab:
        anssum += min(ans[a], ans[b])
    print(anssum)
    ans = list(map(str, ans))
    print(" ".join(ans))
 
 
    return
 

def E():
    return
 

def F():
    return
 

def G():
    return
 

def H():
    return
 

if __name__ == '__main__':
    D()

Solution (Python):
from collections import deque


def main():
    N = int(input())
    ans = [0] * N
    adj = [set() for _ in range(N)]
    edge = [None] * (N-1)
    for i in range(N-1):
        a, b = map(int, input().split())
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)
        edge[i] = (a-1, b-1)
    C = list(map(int, input().split()))
    C.sort()
    q = deque()
    for i in range(N):
        if len(adj[i]) == 1:
            q.append(i)
    x = 0
    while len(q):
        n = q.popleft()
        ans[n] = C[x]
        x += 1
        for a in adj[n]:
            adj[a].remove(n)
            if len(adj[a]) == 1:
                q.append(a)
    total = 0
    for i in range(N-1):
        a, b = edge[i]
        total += min(ans[a], ans[b])
    print(total)
    print(*ans)


if __name__ == "__main__":
    main()

Solution (Python):

n = int(input())
ab = list()
for _ in range(n - 1):
    ab.append(list(map(int, input().split())))

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

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

c.sort(reverse=True)

ans = [-1 for _ in range(n)]
ans[0] = c.pop(0)

q = list()
q.append(0)

while(len(q) != 0):
    v = q.pop(0)
    for u in tree[v]:
        if ans[u] != -1:
            continue
        ans[u] = c.pop(0)
        q.append(u)

print(sum(ans[1:]))
print(" ".join([str(a) for a in ans]))

Solution (Python):
import heapq
import sys
sys.setrecursionlimit(10000000)
n=int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
c=sorted(list(map(lambda x:-int(x), input().split())))
print(-sum(c[1:]))
heapq.heapify(c)
mat = [[] for _ in range(n+1)]
ans=[0]*n
for i in range(n-1):
    a, b = ab[i]
    mat[a].append(b)
    mat[b].append(a)
def dp(x, y):
    ans[y-1]=-heapq.heappop(c)
    if y>1 and len(mat[y])==1:
        return
    for i in mat[y]:
        if i!=x:
            dp(y, i)
dp(0, 1)
print(' '.join(map(str, ans)))

Solution (Python):
import sys
import numpy as np
sys.setrecursionlimit(100000)
n = int(input())

edges=[[] for i in range(n+1)]
d=[-1 for i in range(n+1)]
for i in range(1,n):
	a, b=[int(i) for i in input().split()]
	edges[a].append([b,1])
	edges[b].append([a,1])
def kyori(u):
	for v,w in edges[u]:
		if d[v]==-1:
			d[v]=d[u]+w
			kyori(v)

d[1]=0
kyori(1)

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

ans_lst = [0] * n
ans = sum(D[1:])

ans_lst[0] = D[0]
now_kyori = 1
idx = 1
m = 1
idx_lst = [i for i in range(n)]

d.pop(0)

lst = np.array([d, idx_lst]).T.tolist()
lst.sort()
d = np.array(lst).T.tolist()[0]
idx_lst = np.array(lst).T.tolist()[1]

for i in range(n):
    ans_lst[idx_lst[i]] = D[i]

ans_lst = list(map(str, ans_lst))
mojiretu = ' '.join(ans_lst)
print(ans)
print(mojiretu)

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

def intinput(): return map(int,input().split())

def ab(i):
    global c,l,x
    while len(l[i])>0:
        x[l[i][0]] = c.pop(0)
        l[l[i][0]].remove(i)
        ab(l[i][0])
        l[i].pop(0)
    return

n=int(input())
l = [[] for _ in range(n+1)]
for i in range(n-1):
    a,b=intinput()
    l[a].append(b)
    l[b].append(a)
c = list(intinput())
c.sort(reverse=1)
x = [0 for _ in range(n+1)]
x[1]=c.pop(0)
for i in range(1,n+1):
    ab(i)
print(sum(x[2:]))
f = ""
q= len(x[1:])
for i in range(q):
    if i != q-1:
        f += str(x[i+1])+" "
    else:
        f += str(x[i+1])
print(f)

Solution (Python):


N = int(input())
p = [list(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
c = list(map(int,input().split()))

def dfs(v,gen,node):
    Stack = []
    visit[v] = True
    Stack.append(v)
    while Stack:
        v = Stack.pop()
        node[v] = gen.__next__()
        for i in nextl[v]:
            if not visit[i]:
                visit[i] = True
                Stack.append(i)

def list2gen(l):
    for e in l:
        yield e

node = [0]*N
visit = [False]*N
nextl = [[] for i in range(N)]
for a, b in p:
    nextl[a].append(b)
    nextl[b].append(a)
c.sort(reverse=True)
gen = list2gen(c)
dfs(0,gen,node)
anssum = sum(c[1:])
print(anssum)
for e in node:
    print(e,end=" ")

Solution (Python):
class Queue(object):

    def __init__(self):
        self.queue_list = []

    def enqueue(self, value):
        self.queue_list.append(value)

    def dequeue(self):
        try:
            value = self.queue_list.pop(0)
        except IndexError:
            value = None

        return value

N = int(input())

pair = []
tree = {}

for _ in range(N-1):
    a, b = list(map(int, input().split(" "))) 
    if a in tree.keys():
        tree[a].append(b)
    else:
        tree[a] = [b]
        
    if b in tree.keys():
        tree[b].append(a)
    else:
        tree[b] = [a]
    pair.append([a,b])
    
c = list(map(int, input().split(" ")))
c.sort(reverse=True)
c = c[:N+2]


queue = Queue()
tree_l = {}
for key in tree.keys():
    tree_l[key] = len(tree[key])

ans = {}
max_node = max((v, k) for k, v in tree_l.items())[1]
ans[max_node] = c[0]
used = [max_node]
cnt = 0

candi = {}
for i in tree[max_node]:
    candi[i] = tree_l[i]

for k, v in sorted(candi.items(), key=lambda x: -x[1]):
    queue.enqueue(k)
    used.append(k)

while True:
    node = queue.dequeue()
    cnt += 1
    ans[node] = c[cnt]
    
    if cnt == N-1:
        break
    
    candi = {}
    for i in tree[node]:
        candi[i] = tree_l[i]
    for k, v in sorted(candi.items(), key=lambda x: -x[1]):
        if k not in used:
            queue.enqueue(k)
            used.append(k)
total = 0
for a, b in pair:
    if ans[a] > ans[b]:
        total += ans[b]
    else:
        total += ans[a]
        
print(total)
for i in range(1, N, 1):
    print(ans[i], end=" ")

print(ans[N])

Solution (Python):

n = int(input())
g = [[] for _ in range(n)]
for i in range(n - 1):
    u, v = map(int, input().split())
    g[u - 1].append((v - 1))
    g[v - 1].append((u - 1))

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


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


q = list()
 

ans[0] = c_list[0]
c_list.pop(0)

q.append(0)


while(len(q) != 0):
    v = q[0]
    q.pop(0)
    for u in g[v]:
        
        if ans[u] != -1:
            continue
        
        ans[u] = c_list[0]
        c_list.pop(0)
        
        q.append(u)
    


print(sum(ans[1:]))
print(" ".join([str(a) for a in ans]))

Solution (Python):
class Queue(object):

    def __init__(self):
        self.queue_list = []

    def enqueue(self, value):
        self.queue_list.append(value)

    def dequeue(self):
        try:
            
            value = self.queue_list.pop(0)
        except IndexError:
            value = None

        return value
N = int(input())

pair = []
tree = {}

for _ in range(N-1):
    a, b = list(map(int, input().split(" "))) 
    if a in tree.keys():
        tree[a].append(b)
    else:
        tree[a] = [b]
        
    if b in tree.keys():
        tree[b].append(a)
    else:
        tree[b] = [a]
    pair.append([a,b])
    
c = list(map(int, input().split(" ")))
c.sort(reverse=True)
c = c[:N+2]


queue = Queue()
tree_l = {}
for key in tree.keys():
    tree_l[key] = len(tree[key])

ans = {}
max_node = max((v, k) for k, v in tree_l.items())[1]
ans[max_node] = c[0]
used = [max_node]
cnt = 0

candi = {}
for i in tree[max_node]:
    candi[i] = tree_l[i]

for k, v in sorted(candi.items(), key=lambda x: -x[1]):
    queue.enqueue(k)
    used.append(k)

while True:
    node = queue.dequeue()
    cnt += 1
    ans[node] = c[cnt]
    
    if cnt == N-1:
        break
    
    candi = {}
    for i in tree[node]:
        candi[i] = tree_l[i]
    for k, v in sorted(candi.items(), key=lambda x: -x[1]):
        if k not in used:
            queue.enqueue(k)
            used.append(k)
total = 0
for a, b in pair:
    if ans[a] > ans[b]:
        total += ans[b]
    else:
        total += ans[a]
        
print(total)
for i in range(1, N, 1):
    print(ans[i], end=" ")

print(ans[N])

Solution (Python):
class Queue(object):

    def __init__(self):
        self.queue_list = []

    def enqueue(self, value):
        self.queue_list.append(value)

    def dequeue(self):
        try:
            
            value = self.queue_list.pop(0)
        except IndexError:
            value = None

        return value
N = int(input())

pair = []
tree = {}

for _ in range(N-1):
    a, b = list(map(int, input().split(" "))) 
    if a in tree.keys():
        tree[a].append(b)
    else:
        tree[a] = [b]
        
    if b in tree.keys():
        tree[b].append(a)
    else:
        tree[b] = [a]
    pair.append([a,b])
    
c = list(map(int, input().split(" ")))
c.sort(reverse=True)
c = c[:N+2]


queue = Queue()
tree_l = {}
for key in tree.keys():
    tree_l[key] = len(tree[key])

ans = {}
max_node = max((v, k) for k, v in tree_l.items())[1]
ans[max_node] = c[0]
used = [max_node]
cnt = 0

candi = {}
for i in tree[max_node]:
    candi[i] = tree_l[i]

for k, v in sorted(candi.items(), key=lambda x: -x[1]):
    queue.enqueue(k)
    used.append(k)

while True:
    node = queue.dequeue()
    cnt += 1
    ans[node] = c[cnt]
    
    if cnt == N-1:
        break
    
    candi = {}
    for i in tree[node]:
        candi[i] = tree_l[i]
    for k, v in sorted(candi.items(), key=lambda x: -x[1]):
        if k not in used:
            queue.enqueue(k)
            used.append(k)
total = 0
for a, b in pair:
    if ans[a] > ans[b]:
        total += ans[b]
    else:
        total += ans[a]
        
print(total)
for i in range(1, N, 1):
    print(ans[i], end=" ")

print(ans[N])

Solution (Python):
class Queue(object):

    def __init__(self):
        self.queue_list = []

    def enqueue(self, value):
        self.queue_list.append(value)

    def dequeue(self):
        try:
            
            value = self.queue_list.pop(0)
        except IndexError:
            value = None

        return value
N = int(input())

pair = []
tree = {}

for _ in range(N-1):
    a, b = list(map(int, input().split(" "))) 
    if a in tree.keys():
        tree[a].append(b)
    else:
        tree[a] = [b]
        
    if b in tree.keys():
        tree[b].append(a)
    else:
        tree[b] = [a]
    pair.append([a,b])
    
c = list(map(int, input().split(" ")))
c.sort(reverse=True)
c = c[:N+2]


queue = Queue()
tree_l = {}
for key in tree.keys():
    tree_l[key] = len(tree[key])

ans = {}
max_node = max((v, k) for k, v in tree_l.items())[1]
ans[max_node] = c[0]
used = [max_node]
cnt = 0

candi = {}
for i in tree[max_node]:
    candi[i] = tree_l[i]

for k, v in sorted(candi.items(), key=lambda x: -x[1]):
    queue.enqueue(k)
    used.append(k)

while True:
    node = queue.dequeue()
    cnt += 1
    ans[node] = c[cnt]
    
    if cnt == N-1:
        break
    
    candi = {}
    for i in tree[node]:
        candi[i] = tree_l[i]
    for k, v in sorted(candi.items(), key=lambda x: -x[1]):
        if k not in used:
            queue.enqueue(k)
            used.append(k)
total = 0
for a, b in pair:
    if ans[a] > ans[b]:
        total += ans[b]
    else:
        total += ans[a]
        
print(total)
for i in range(1, N, 1):
    print(ans[i], end=" ")

print(ans[N])

Solution (Python):


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

C2 = []
for i in range(n):
    C2.append([C[i],i])

C2.sort()

ans = sum(C)-C2[-1][0]

T = [[] for i in range(n)]
for i in range(len(A)):
    T[A[i][0]-1].append(A[i][1]-1)
    T[A[i][1]-1].append(A[i][0]-1)



E = [[0,i] for i in range(n)]
E[0][0]=1














holist=[0]
hot = 0

def ho(u):
    p = E[u][0]
    for j in range(len(T[u])):
        if E[T[u][j]][0] == 0:
            E[T[u][j]][0] = p+1
            holist.append(T[u][j])

while hot < len(holist):
    ho(holist[hot])
    hot += 1

E.sort(reverse=1)




D = [0 for i in range(n)]
for i in range(n):
    D[E[i][1]] = C2[i][0]

print(ans)
s = ""
for i in range(n):
    s += str(D[i])
    s += " "

print(s)

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

edge = [[] for i 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)

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

c = sorted(cost, reverse=True)

w = [0] * n

w[0] = c.pop(0)

chk = [i for i in edge[0]]

while chk != []:
    node = chk.pop(0)
    if w[node] == 0:
        w[node] = c.pop(0)
        chk.extend(edge[node])

print(sum(cost) - max(cost))

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

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

n = input()
g = [[] for i in xrange(n + 1)]
inp = stdin.readlines()

idx = 0
c = []
for line in inp:
    if idx < n - 1:
        u, v = map(int, line.strip().split())
        g[u].append([v, idx])
        g[v].append([u, idx])
        idx += 1
    else:
        c = map(int, line.strip().split())

num = [0] * (n + 1)
ans = [0] * (n - 1)
c.sort(reverse = True)

vis = [0] * (n + 1)
def bfs(root):
    global vis
    
    vis[root] = 1
    q = deque([root])
    ctr = 0
    num[root] = c[ctr]
    ctr += 1
    while q:
        u = q.popleft()
        for v, idx in g[u]:
            if not vis[v]:
                vis[v] = 1
                q.append(v)
                num[v] = c[ctr]
                ans[idx] = c[ctr]
                ctr += 1

bfs(1)
print sum(c) - c[0]
print ' '.join(map(str, num[1:]))

Solution (Python):
INF=-10**10
N=int(input())
v=[0]*N
dic=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    dic[a-1].append(b-1)
    dic[b-1].append(a-1)
    v[a-1]+=1
    v[b-1]+=1

a=[[] for i in range(N)]
for i in range(N):
    a[v[i]].append(i)

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

ans=[-1]*N

answer=0
tmp=0
while tmp<N:

    if a[tmp]==[]:
        tmp+=1
        continue
    j=a[tmp][0]
    ans[j]=c.pop(0)
    itiji=INF
    for k in dic[j]:
        if v[k]>0:
            answer+=ans[j]
            a[v[k]].remove(k)
            a[v[k]-1].append(k)
            v[k]-=1
            if v[k]<tmp: itiji=tmp-1
    a[tmp].pop(0)
    v[j]=-1
    if itiji>INF: tmp-=1
    elif a[tmp]==[]: tmp+=1
      
print(answer)
for i in range(N):
    print(ans[i],end=" ")

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

adj = [[] for i in range(n)]
ans = [0 for i in range(n)]
anum = 0
depth = [0 for i in range(n)]

for i in range(n-1):
    aa,ba = map(int,input().split())
    adj[aa-1].append(ba-1)
    adj[ba-1].append(aa-1)

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

sh = []

def delete(edges):
    sh.append(edges)

    for i in range(len(edges)):
        la = adj[edges[i]][0]
        adj[la].remove(edges[i])
        if len(adj[la]) == 0:
            sh.append([la])
        adj[edges[i]] = []
    return

def search(adj):
    k = []
    for i in range(len(adj)):
        if len(adj[i]) == 1:
            k.append(i)
    return k

ed = search(adj)

while len(ed):
    delete(ed)
    ed = search(adj)
    if len(ed) == 1:
        sh.append(ed)
        break
    if len(ed) == 2:
        if adj[ed[0]] and adj[ed[0]][0] == ed[1]:
            sh.append(ed)
            break

sug = []
for i in range(len(sh)):
    for m in sh[i]:
        sug.append(m)


for i in range(len(sug)):
    ans[sug[i]] = c[i]



for i in range(n-1):
    anum += c[i]
print(anum)

las = ""
for num in ans:
    las += str(num)+ " "
print(las)

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=" ")

Solution (Python):
import sys

sys.setrecursionlimit(10000000)

N = int(input())
M = [[] for _ in range(N)]
P = [0] * N
V = [0] * N
for _ in range(N - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    M[a].append(b)
    M[b].append(a)
C = sorted(map(int, input().split()), reverse=True)

def dfs(n, cur):
    if V[n] == 1:
        return cur
    P[n] = C[cur]
    V[n] = 1
    cur += 1
    for c in M[n]:
        cur = dfs(c, cur)
    return cur

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

Solution (Python):
import copy
import heapq


class Node:
    def __init__(self):
        self.value = -1

    def __repr__(self):
        return "<v: {}>".format(self.value)


N = int(input())

adjs = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = [int(i) for i in input().split()]
    adjs[a-1].append(b-1)
    adjs[b-1].append(a-1)
adjs_copy = [copy.copy(adj) for adj in adjs]

C = [int(i) for i in input().split()]

cq = []
for c in C:
    heapq.heappush(cq, c)


nodes = [Node() for _ in range(N)]
changed = True
while changed:
    changed = False
    for i in range(N):
        if len(adjs[i]) == 1:
            nodes[i].value = heapq.heappop(cq)

            neighbor = adjs[i][0]
            adjs[i] = []
            adjs[neighbor].remove(i)

            changed = True
for node in nodes:
    if node.value == -1:
        node.value = heapq.heappop(cq)
        break


score = 0
for i in range(N):
    adj = adjs_copy[i]
    for ad in adj:
        score += min(nodes[i].value, nodes[ad].value)
score = score // 2

print(score)
print(*[str(node.value) for node in nodes])

Solution (Python):
from sys import stdin

def main():
    n = int(stdin.readline())
    e = [tuple(map(int,stdin.readline().split())) for x in range(n-1)]
    c = [int(x) for x in stdin.readline().split()]    

    c.sort(reverse=True)

    edge = {(i+1):[] for i in range(n)}
    for a,b in e:
        edge[a].append(b)
        edge[b].append(a)

    node = [0]*n
    root = 1

    node[0] = c[0]
    yet = edge[1]
    consume = 1

    while consume < n:
        x = yet[consume-1]
        node[x-1] = c[consume]
        consume += 1
        for y in edge[x]:
            if node[y-1] == 0:
                yet.append(y)

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

if __name__=='__main__':
    main()

Solution (Python):
n=int(input())
graph=[]
ans=[0]*n
zisuu={}
for i in range(n):
    graph.append([])
for i in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
from collections import deque
zisuu_1=deque([])
for i in range(n):
    zisuu[i]=len(graph[i])
    if len(graph[i])==1:
        zisuu_1.append(i)
c=list(map(int,input().split()))
c.sort()
if n==1:
    ans[0]=c[0]
else:
    for i in range(n):
        x=zisuu_1.popleft()
        ans[x]=c[i]
        for j in graph[x]:
            zisuu[j]=zisuu[j]-1
            if zisuu[j]==1:
                zisuu_1.append(j)
print(sum(c[:n-1]))
for i in ans:
    print(i)

Solution (Python):
import copy
import queue


def read():
    N = int(input().strip())
    edge = [-1 for _ in range(N+1)]
    for i in range(1, N+1):
        edge[i] = list()
    for _ in range(N-1):
        a, b = list(map(int, input().strip().split()))
        edge[a].append(b)
        edge[b].append(a)
    C = list(map(int, input().strip().split()))
    return N, edge, C


def center_of_tree(N, edge):
    
    n = N
    previous_parent = -1
    e = copy.deepcopy(edge)
    while n > 1:
        for child in range(1, N+1):
            if len(e[child]) == 1:
                parent = e[child][0]
                e[parent].remove(child)
                e[child].remove(parent)
                n -= 1
                previous_parent = parent
    return previous_parent


def write_node_weights(N, parent, edge, C):
    C = list(sorted(C))
    node_weight = [-1 for _ in range(N+1)]
    node_weight[parent] = C.pop()
    q = queue.Queue()
    q.put(parent)
    while len(C) > 0:
        parent = q.get()
        for child in edge[parent]:
            if node_weight[child] == -1:
                node_weight[child] = C.pop()
                q.put(child)
    return node_weight


def sum_of_edge_weights(N, node_weight, edge):
    sum_of_edge_weights = 0
    for a in range(1, N+1):
        for b in edge[a]:
            if a < b:
                sum_of_edge_weights += min(node_weight[a], node_weight[b])
    return sum_of_edge_weights


def solve(N, edge, C):
    center = center_of_tree(N, edge)
    node_weight = write_node_weights(N, center, edge, C)
    edge_weights = sum_of_edge_weights(N, node_weight, edge)
    return edge_weights, node_weight[1:]


if __name__ == '__main__':
    inputs = read()
    edge_weights, node_weight = solve(*inputs)
    print(edge_weights)
    print(' '.join(map(str, node_weight)))

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

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

num = 0
def point(x, prev, turn=0):
    global num
    if turn > n:
        return
    dp[x] = c[num]
    num += 1
    for i in edge[x]:
        if dp[i] != 0:
            continue
        if i == prev:
            continue
        else:
            point(i, x, turn + 1)
    return

for i in range(n):
    if len(edge[i]) > 1:
        continue
    else:
        dp = [0] * n
        point(i, -1)
        break

ans = sum(c) - max(c)

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

Solution (Python):

n = int(input())
ab = list()
for _ in range(n - 1):
    ab.append(list(map(int, input().split())))

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

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

c.sort(reverse=True)

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

ans[0] = c[0]
c.pop(0)
q = list()
q.append(0)

while(len(q) != 0):
    v = q[0]
    q.pop(0)
    for u in tree[v]:
        if ans[u] != -1:
            continue
        ans[u] = c[0]
        c.pop(0)
        q.append(u)

print(sum(ans[1:]))
print(" ".join([str(a) for a in ans]))