M-SOLUTIONS Programming Contest - Maximum Sum of Minimum

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.

Examples

Input

5
1 2
2 3
3 4
4 5
1 2 3 4 5


Output

10
1 2 3 4 5


Input

5
1 2
1 3
1 4
1 5
3141 59 26 53 59


Output

197
59 26 3141 59 53

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
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)))


n = int(input())
g = [[] for i in range(n)]
ro = [0] * n
for i in range(n - 1):
	(a, b) = map(int, input().split())
	ro[a - 1] += 1
	ro[b - 1] += 1
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
c = list(map(int, input().split()))
c.sort(reverse=True)
m = max(ro)
mi = ro.index(m)
q = [mi]
ans = [0] * n
v = [0] * n
v[mi] = 1
ans[mi] = c.pop(0)
while len(q) > 0:
	s = q.pop()
	for i in g[s]:
		if v[i] == 0:
			v[i] = 1
			ans[i] = c.pop(0)
			q.append(i)
print(sum(ans) - max(ans))
print(*ans)


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:]))


N = int(input())
A = [[] for i in range(N + 1)]
B = [0 for i in range(N + 1)]
for i in range(N - 1):
	(a, b) = [int(x) for x in input().split()]
	A[a].append(b)
	A[b].append(a)
	B[a] += 1
	B[b] += 1
C = sorted([int(x) for x in input().split()])
D = [-1 for i in range(N + 1)]
M = sum(C) - C[-1]
isEnd = []
for i in range(1, N + 1):
	if B[i] == 1:
		isEnd.append(i)
for c in C:
	d = isEnd.pop()
	D[d] = c
	B[d] = 0
	for k in A[d]:
		A[k].remove(d)
		B[k] -= 1
		if B[k] == 1:
			isEnd.append(k)
print(M)
print(' '.join([str(x) for x in D[1:]]))


from collections import deque
N = int(input())
g = [set() for i in range(N + 1)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	g[a].add(b)
	g[b].add(a)
c = list(map(int, input().split()))
c.sort(reverse=True)
print(sum(c) - c[0])
q = deque()
nums = [0] * (N + 1)
q.appendleft(1)
while q:
	d = q.popleft()
	nums[d] = c.pop(0)
	for node in g[d]:
		if nums[node] == 0:
			q.appendleft(node)
print(*nums[1:])


import sys
readline = sys.stdin.readline
write = sys.stdout.write
N = int(input())
edges = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = map(int, readline().split())
	edges[a - 1].append(b - 1)
	edges[b - 1].append(a - 1)
C = list(map(int, readline().split()))
C.sort()
print(str(sum(C) - C[-1]))
queue = [0]
D = ['x' for i in range(N)]
while queue:
	op = queue.pop(0)
	if D[op] != 'x':
		continue
	D[op] = str(C.pop(-1))
	numchild = len(edges[op])
	for i in range(numchild):
		queue.append(edges[op][i])
print(' '.join(D))


N = int(input())
E = [set() for i in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	E[a].add(b)
	E[b].add(a)
cs = list(map(int, input().split()))
cs.sort()
M = sum(cs[:-1])
ds = [-1] * N
ds[0] = cs.pop()
q = [0]
while q:
	c = q.pop()
	ns = E[c]
	for n in ns:
		if ds[n] < 0:
			ds[n] = cs.pop()
			q.append(n)
print(M)
print(' '.join(map(str, ds)))


(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)


import heapq
N = int(input())
AB = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	AB[a].append(b)
	AB[b].append(a)
C = list(map(int, input().split()))
C.sort(reverse=True)
var = [0 for i in range(N)]
var[0] = C[0]
Q = []
heapq.heappush(Q, 0)
ind = 1
for i in range(N - 1):
	q = heapq.heappop(Q)
	for j in AB[q]:
		if var[j] == 0:
			var[j] = C[ind]
			ind += 1
			heapq.heappush(Q, j)
print(sum(C) - C[0])
for v in var:
	print(v, end=' ')


n = int(input())
graph = [[] for _ in range(n)]
cnt = [0] * n
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	graph[a].append(b)
	graph[b].append(a)
C = list(map(int, input().split()))
C.sort(reverse=True)
num = sum(C[1:])
ans = [0] * n
start = 0
par = [-1] * n
stack = [start]
idx = 0
ans[0] = C[idx]
idx += 1
while stack:
	v = stack.pop()
	for u in graph[v]:
		if u == par[v]:
			continue
		par[u] = v
		ans[u] = C[idx]
		idx += 1
		stack.append(u)
print(num)
print(*ans, sep=' ')


import sys
from heapq import heappush, heappop
sys.setrecursionlimit(10 ** 6)
n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	adj[a - 1].append(b - 1)
	adj[b - 1].append(a - 1)
num = [0 for _ in range(n)]
c = list(map(int, input().split()))
h = []
for i in range(n):
	heappush(h, -c[i])

def dfs(x):
	global h
	for v in adj[x]:
		if num[v] != 0:
			continue
		num[v] = -heappop(h)
		dfs(v)
	return
num[0] = -heappop(h)
dfs(0)
print(sum(c) - max(c))
print(*num)


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


from collections import deque
n = int(input())
ans = [0 for i in range(n)]
l = [[] for i in range(n + 1)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	l[a].append(b)
	l[b].append(a)
l1 = sorted(list(map(int, input().split())))
l1 = l1[::-1]
sum = 0
for i in range(1, n):
	sum += l1[i]
q = deque(l1)
q1 = deque([[1]])
while q:
	l2 = q1.popleft()
	for i in l2:
		if ans[i - 1] != 0:
			pass
		else:
			n2 = q.popleft()
			ans[i - 1] = n2
			q1.append(l[i])
print(sum)
answ = ''
for i in range(n):
	answ += str(ans[i]) + ' '
print(answ)


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


from heapq import heappush, heappop
(N, *L) = map(int, open(0).read().split())
dic = [[] for i in range(N)]
ans = [-1] * N
cnt = [0] * N
hq = []
for (a, b) in zip(*[iter(L[:2 * (N - 1)])] * 2):
	a -= 1
	b -= 1
	dic[a] += [b]
	dic[b] += [a]
	cnt[a] += 1
	cnt[b] += 1
C = L[2 * (N - 1):]
C.sort()
for i in range(N):
	heappush(hq, (cnt[i], i))
arg = 0
m = 0
while True:
	(c, i) = heappop(hq)
	if ans[i] != -1:
		continue
	m += C[arg] * cnt[i]
	ans[i] = C[arg]
	arg += 1
	if arg == N:
		break
	for v in dic[i]:
		cnt[v] -= 1
		heappush(hq, (cnt[v], v))
print(m)
print(*ans)


n = int(input())
pair = {}
nodes = [0] * n
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	pair.setdefault(a, [])
	pair.setdefault(b, [])
	pair[a] += [b]
	pair[b] += [a]
c = list(map(int, input().split()))
c.sort()
kei = sum(c[:-1])
cnt = 0
nodes[0] = c.pop()
tugi = pair[1]
while c:
	ntugi = []
	for i in tugi:
		nodes[i - 1] = c.pop()
		for ii in pair[i]:
			if nodes[ii - 1] > 0:
				continue
			ntugi += [ii]
	tugi = ntugi
print(kei)
print(*nodes)


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]))


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)


N = int(input())
G = [[] for i in range(N + 1)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	G[a].append(b)
	G[b].append(a)
c = list(map(int, input().split()))
c.sort()
ans = sum(c) - max(c)
F = []
for i in range(1, N + 1):
	n = len(G[i])
	if n == 1:
		F.append(i)
d = {}
i = 0
while i < N:
	x = F.pop(0)
	d[x] = c[i]
	i += 1
	if len(G[x]) > 0:
		y = G[x][0]
		G[y].remove(x)
		if len(G[y]) == 1:
			F.append(y)
ANS = []
for i in range(1, N + 1):
	ANS.append(d[i])
print(ans)
print(*ANS)


import sys
input = sys.stdin.readline
n = int(input())
l = [[] for _ in range(n)]
ab = []
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	l[a].append(b)
	l[b].append(a)
	ab.append((a, b))
ans = [0] * n
from collections import deque
c = list(map(int, input().split()))
c.sort(reverse=True)
c = deque(c)
q = deque()
q.append([0])
while q:
	ll = q.popleft()
	for v in ll:
		if ans[v] != 0:
			continue
		ans[v] = c.popleft()
		q.append(l[v])
x = 0
for (a, b) in ab:
	x += min(ans[a], ans[b])
print(x)
print(*ans)


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()


from collections import deque
n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
c = [int(x) for x in input().split()]
c = sorted(c, reverse=True)
q = deque([0])
visited = [False] * n
ans = [-1] * n
ans[0] = c[0]
i = 1
while q:
	v = q.popleft()
	visited[v] = True
	for w in g[v]:
		if not visited[w]:
			ans[w] = c[i]
			i += 1
			q.append(w)
print(sum(c[1:]))
print(*ans)


N = int(input())
E = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	E[a - 1].append(b - 1)
	E[b - 1].append(a - 1)
C = [int(c) for c in input().split()]
C.sort(reverse=True)
M = sum(C) - C[0]
from collections import deque
q = deque([0])
ans = [0] * N
ans[0] = C[0]
i = 1
while q:
	u = q.popleft()
	for v in E[u]:
		if ans[v] > 0:
			continue
		ans[v] = C[i]
		i += 1
		q.append(v)
print(M)
print(*ans)


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:])


from collections import deque
N = int(input())
ad_ls = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	ad_ls[a].append(b)
	ad_ls[b].append(a)
c_ls = list(map(int, input().split()))
c_ls.sort(reverse=True)
c_q = deque(c_ls)
d_ls = [0] * N
q = deque()
q.append(0)
d_ls[0] = c_q.popleft()
while q:
	now = q.popleft()
	for nex in ad_ls[now]:
		if d_ls[nex] == 0:
			d_ls[nex] = c_q.popleft()
			q.append(nex)
print(sum(c_ls) - max(c_ls))
print(*d_ls)


from collections import deque
N = int(input())
s = [set() for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	s[a - 1].add(b - 1)
	s[b - 1].add(a - 1)
c = list(map(int, input().split()))
c.sort(reverse=True)
ans = [0] * N
ans[0] = c[0]
cp = 1
i = 0
pre = -1
dq = deque()
while True:
	for x in s[i]:
		if x != pre:
			ans[x] = c[cp]
			cp += 1
			dq.appendleft((x, i))
	if dq:
		(i, pre) = dq.pop()
	else:
		break
print(sum(c[1:]))
print(' '.join(map(str, ans)))


import sys
sys.setrecursionlimit(10 ** 7)

def I():
	return int(sys.stdin.readline().rstrip())

def MI():
	return map(int, sys.stdin.readline().rstrip().split())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))
N = I()
Graph = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b) = MI()
	Graph[a].append(b)
	Graph[b].append(a)
C = LI()
C.sort(reverse=True)
print(sum(C[1:]))
ANS = [-1] * (N + 1)
index = 0

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


import sys
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)
data = [[] for i in range(N + 1)]
for (a, b) in ab:
	data[a].append(b)
	data[b].append(a)
flag = [0] * (N + 1)
ans = [0] * (N + 1)
flag[1] = 1
k = 0
que = [1]
while que:
	for u in que:
		ans[u] = c[k]
		k += 1
	if k > N:
		break
	h = []
	for u in que:
		for v in data[u]:
			if flag[v] == 0:
				flag[v] = 1
				h.append(v)
	que = h
print(sum(ans[2:]))
print(*ans[1:])


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


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


from collections import deque
N = int(input())
lines = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	lines[a - 1].append(b - 1)
	lines[b - 1].append(a - 1)
c = list(map(int, input().split()))
c.sort(reverse=True)
not_visited = [-1] * N
not_visited[0] = 0
stack = deque()
stack.append(0)
ans = [0] * N
ans[0] = c[0]
cut = 1
while stack:
	now = stack.popleft()
	for nex in lines[now]:
		if not_visited[nex] == -1:
			ans[nex] = c[cut]
			not_visited[nex] = not_visited[now] + 1
			cut += 1
			stack.append(nex)
print(sum(c[1:]))
print(*ans)


n = int(input())
adj_list = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	adj_list[a].append(b)
	adj_list[b].append(a)
c = list(map(int, input().split()))
c.sort(reverse=True)
idx = 0
from collections import deque
dq = deque()
dq.append(0)
ans = [-1] * n
while len(dq) > 0:
	node = dq.popleft()
	ans[node] = c[idx]
	idx += 1
	for next_node in adj_list[node]:
		if ans[next_node] < 0:
			dq.append(next_node)
print(sum(c[1:]))
print(*ans)


from collections import deque
n = int(input())
edge = []
graph = [[] for i in range(n)]
point = [-1] * n
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	edge.append([a, b])
	graph[a].append(b)
	graph[b].append(a)
num = list(map(int, input().split()))
num.sort()
start = 0
for i in range(n):
	if len(graph[i]) == 1:
		start = i
		break
dfs = deque([start])
while dfs:
	v = dfs.popleft()
	point[v] = num.pop()
	for i in graph[v]:
		if point[i] != -1:
			continue
		dfs.appendleft(i)
ans = 0
for i in edge:
	ans += min(point[i[0]], point[i[1]])
print(ans)
print(*point)


from collections import deque
N = int(input())
tree = [set() for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	tree[a - 1].add(b - 1)
	tree[b - 1].add(a - 1)
C = sorted(list(map(int, input().split())))
ans = [0] * N
print(sum(C[:-1]))
ans[0] = C.pop()
n = min(tree[0])
ans[n] = C.pop()
d = deque([0, n])
visited = set(d)
while d:
	x = d.pop()
	for new_x in tree[x]:
		if new_x not in visited:
			ans[new_x] = C.pop()
			d.append(new_x)
			visited.add(new_x)
print(*ans)


from collections import deque
N = int(input())
tree = {i: set() for i in range(1, N + 1)}
for i in range(N - 1):
	(a, b) = map(int, input().split())
	tree[a].add(b)
	tree[b].add(a)
inl = list(map(int, input().split()))
inl.sort()
res = [0] * (N + 1)
qu = deque([1])
res[1] = inl.pop()
while qu:
	i = qu.popleft()
	for j in tree[i]:
		if res[j] == 0:
			res[j] = inl.pop()
			qu.append(j)
print(sum(res[2:]))
for i in res[1:]:
	print(i, end=' ')
print('')


from collections import deque
N = int(input())
G = {k: [] for k in range(N + 1)}
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	G[a].append(b)
	G[b].append(a)
c = sorted([int(i) for i in input().split()], reverse=True)
visited = [-1] * N
cnt = 0
que = deque([1])
while que:
	i = que.popleft()
	visited[i - 1] = c[cnt]
	cnt += 1
	for j in G[i]:
		if visited[j - 1] == -1:
			que.append(j)
print(sum(c[1:]))
print(*visited)


N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
c = list(map(int, input().split()))
c.sort(reverse=True)
al = [[] for _ in range(N + 1)]
for (a, b) in ab:
	al[a].append(b)
	al[b].append(a)
d = [0] * N
d[ab[0][0] - 1] = c[0]
cnt = 1
child = al[ab[0][0]]
ans = 0
Check = [True] * (N + 1)
Check[ab[0][0]] = False
while child and cnt < N:
	pi = int(child.pop())
	Check[pi] = False
	d[pi - 1] = c[cnt]
	ans += c[cnt]
	for i in al[pi]:
		if Check[i]:
			child.append(i)
	cnt += 1
print(ans)
print(' '.join(map(str, d)))


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:])


import sys
sys.setrecursionlimit(2000000)
N = int(input())
ab = list((list(map(int, input().split())) for i in range(N - 1)))
c = list(map(int, input().split()))
c.sort(reverse=True)
print(sum(c) - c[0])
tree = [[-1] for i in range(N)]
for (a, b) in ab:
	tree[a - 1].append(b)
	tree[b - 1].append(a)

def func(l):
	if tree[l - 1][0] != -1:
		return
	tree[l - 1][0] = c.pop(0)
	for i in tree[l - 1][1:]:
		func(i)
func(1)
for i in tree:
	print(i[0], end=' ')


import sys
input = sys.stdin.buffer.readline
from collections import deque
N = int(input())
neighbor = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	neighbor[a - 1].append(b - 1)
	neighbor[b - 1].append(a - 1)
c = list(map(int, input().split()))
c.sort(reverse=True)
d = deque([0])
ans = [c[0]] + [0] * (N - 1)
M = 0
c_idx = 1
while d:
	p = d.popleft()
	for n in neighbor[p]:
		if not ans[n]:
			ans[n] = c[c_idx]
			M += c[c_idx]
			c_idx += 1
			d.append(n)
print(M)
print(*ans)


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


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]))


N = int(input())
ab = []
abn = [0] * N
abw = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = list(map(int, input().split()))
	ab.append([a, b])
	abw[a - 1].append(b)
	abw[b - 1].append(a)
	abn[a - 1] += 1
	abn[b - 1] += 1
c = sorted(list(map(int, input().split())))
cn = 0
d = [0] * N
s = [i for i in range(N)]
while cn < N:
	cut = []
	for i in s:
		if abn[i] == 1 and cn < N or len(s) == 1:
			d[i] = c[cn]
			cn += 1
			cut.append(i)
			abn[i] -= 1
			s.remove(i)
	for j in cut:
		for k in abw[j]:
			abn[k - 1] -= 1
print(sum(c) - max(c))
print(' '.join(map(str, d)))


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)
graph = [[] for i in range(n + 1)]
parent = [0 for i in range(n + 1)]
root = 1
order = []
que = deque([root])
for (a, b) in ab:
	graph[a].append(b)
	graph[b].append(a)
while que:
	x = que.popleft()
	order.append(x)
	for y in graph[x]:
		if parent[x] == y:
			continue
		parent[y] = x
		que.append(y)
ans = []
for i in range(n):
	ans.append((order[i], c[i]))
ans.sort()
print(sum(c[1:]))
for i in ans:
	print(i[1], end=' ')


from collections import deque
N = int(input())
E = [[] for _ in range(N)]
for (a, b) in [[int(i) - 1 for i in input().split()] for _ in range(N - 1)]:
	E[a].append(b)
	E[b].append(a)
C = [int(i) for i in input().split()]
C.sort(reverse=True)
ans = [0] * N

def bfs(i):
	cur = 0
	Q = deque()
	Q.append(0)
	visited = [False] * N
	while Q:
		v = Q.popleft()
		visited[v] = True
		ans[v] = C[cur]
		cur += 1
		for e in E[v]:
			if visited[e]:
				continue
			Q.append(e)
bfs(0)
print(sum(C[1:]))
print(*ans)


from collections import deque
N = int(input())
G = [[] for i in range(N + 1)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	G[a].append(b)
	G[b].append(a)
c = list(map(int, input().split()))
c.sort()
M = sum(c) - c[-1]
score = [0 for i in range(N + 1)]
seen = [False for i in range(N + 1)]
seen[1] = True
score[1] = c.pop()
d = deque([1])
while len(d) > 0:
	v = d.pop()
	for i in G[v]:
		if seen[i] == False:
			seen[i] = True
			score[i] = c.pop()
			d.append(i)
print(M)
print(*score[1:])


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]))


n = int(input())
g = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	g[a].append(b)
	g[b].append(a)
C = list(map(int, input().split()))
C.sort(reverse=True)
order = []
par = [-1] * n
s = []
visit = [-1] * n
s.append(0)
visit[0] = 0
while s:
	v = s.pop()
	order.append(v)
	for u in g[v]:
		if u == par[v]:
			continue
		par[u] = v
		s.append(u)
order.reverse()
ans = [0] * n
m = 0
for v in order:
	ans[v] = C.pop()
	if par[v] != -1:
		m += ans[v]
print(m)
print(*ans)


from collections import deque
import sys
sys.setrecursionlimit(100000)
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]
C = deque(sorted(map(int, input().split())))
edges = [[] for _ in range(N)]
for (a, b) in AB:
	edges[a - 1].append(b - 1)
	edges[b - 1].append(a - 1)
ps = [0] * N

def dfs(prev, curr):
	ps[curr] = C.pop()
	for dst in edges[curr]:
		if prev == dst:
			continue
		dfs(curr, dst)
dfs(-1, 0)
ans = 0
for (a, b) in AB:
	ans += min(ps[a - 1], ps[b - 1])
print(ans)
print(' '.join([str(p) for p in ps]))


n = int(input())
g = [[] * n for i in range(n)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	g[u].append(v)
	g[v].append(u)
d = list(map(int, input().split()))
d.sort(reverse=True)
from collections import deque
que = deque()
que.append(0)
chk = [False] * n
chk[0] = True
ans = [0] * n
ans[0] = d[0]
cnt = 1
while que:
	now = que.popleft()
	if cnt == n:
		break
	for i in g[now]:
		if not chk[i]:
			chk[i] = True
			ans[i] = d[cnt]
			cnt += 1
			que.append(i)
print(sum(d[1:]) if n > 1 else 0)
print(*ans)


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)
data = [[] for i in range(N + 1)]
num = [-1 for i in range(N + 1)]
num[1] = C[0]
for (a, b) in AB:
	data[a].append(b)
	data[b].append(a)
sumc = sum(C[1:])
stack = [1]
visited = set()
visited.add(1)
idx = 1
while stack:
	a = stack.pop()
	for p in data[a]:
		if not p in visited:
			visited.add(p)
			num[p] = C[idx]
			idx += 1
			stack.append(p)
print(sumc)
print(' '.join([str(num[i]) for i in range(1, N + 1)]))


from collections import defaultdict, deque
N = int(input())
X = defaultdict(list)
for i in range(N - 1):
	(ai, bi) = map(lambda s: int(s) - 1, input().split())
	X[ai].append(bi)
	X[bi].append(ai)
c = list(map(int, input().split()))
c.sort(reverse=True)
print(sum(c[1:]))
d = [0] * N
q = deque([0])
i = 0
while len(q) > 0:
	v = q.popleft()
	d[v] = c[i]
	i += 1
	for x in X[v]:
		if d[x] != 0:
			continue
		q.append(x)
print(' '.join(list(map(str, d))))


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


N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N - 1):
	(fr, to) = map(lambda a: int(a) - 1, input().split())
	edges[fr].append(to)
	edges[to].append(fr)
C = list(map(int, input().split()))
A = sum(C) - max(C)
C.sort()
ans = [None] * N
ans[0] = C.pop()
st = [0]
while st:
	now = st.pop()
	for to in edges[now]:
		if ans[to] == None:
			ans[to] = C.pop()
			st.append(to)
print(A)
print(*ans)


from collections import deque, _heapq
N = int(input())
g = [{'num': 0, 'neighber': []} for _ in range(N + 1)]
for _ in range(N - 1):
	(x, y) = map(int, input().split())
	g[x]['neighber'].append(y)
	g[y]['neighber'].append(x)
c = sorted(map(int, input().split()))
print(sum(c[:-1]))
i = 0
s = [(0, 1)]
while i < len(s):
	(pre, cur) = s[i]
	i += 1
	g[cur]['num'] = c.pop()
	for x in g[cur]['neighber']:
		if x == pre:
			continue
		s.append((cur, x))
print(' '.join((str(g[i]['num']) for i in range(1, N + 1))))


N = int(input())
import collections
Ls = [collections.deque() for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	Ls[a - 1].append(b - 1)
	Ls[b - 1].append(a - 1)
Cs = sorted(map(int, input().split()), reverse=True)
print(sum(Cs) - Cs[0])
sw = [-1] * N
sw[0] = Cs[0]
ct = 1
stk = collections.deque()
stk.appendleft(0)
while len(stk) > 0:
	crN = stk[0]
	if len(Ls[crN]) == 0:
		stk.popleft()
		continue
	nxN = Ls[crN].popleft()
	if sw[nxN] > 0:
		continue
	sw[nxN] = Cs[ct]
	ct += 1
	stk.append(nxN)
print(' '.join(map(str, sw)))


import sys
sys.setrecursionlimit(10 ** 8)
N = int(input())
AB = [tuple(map(int, input().split())) for i in range(N - 1)]
C = list(map(int, input().split()))
C.sort()
es = [[] for i in range(N)]
for (a, b) in AB:
	(a, b) = (a - 1, b - 1)
	es[a].append(b)
	es[b].append(a)
score = 0
vscore = [-1] * N
vscore[0] = C.pop()

def dfs(v, p=-1):
	global score
	for to in es[v]:
		if to == p:
			continue
		vscore[to] = C.pop()
		score += min(vscore[v], vscore[to])
		dfs(to, v)
dfs(0)
print(score)
print(*vscore)


import sys
input = sys.stdin.buffer.readline
n = int(input())
g = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	g[a].append(b)
	g[b].append(a)
C = list(map(int, input().split()))
C.sort()
s = []
parent = [-1] * n
order = []
s.append(0)
while s:
	v = s.pop()
	order.append(v)
	for u in g[v]:
		if parent[v] == u:
			continue
		parent[u] = v
		s.append(u)
order.reverse()
ans = 0
D = [0] * n
for i in range(n):
	v = order[i]
	D[v] = C[i]
	if i != n - 1:
		ans += C[i]
print(ans)
print(*D)


import sys
sys.setrecursionlimit(4100000)
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	edges[a - 1].append(b - 1)
	edges[b - 1].append(a - 1)
c = list(map(int, input().split()))
L = [0] * N
c.sort(reverse=True)

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


N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	edge[a - 1].append(b - 1)
	edge[b - 1].append(a - 1)
C = [int(i) for i in input().split()]
C.sort()
M = sum(C[:-1])
d = [-1] * N
from collections import deque
que = deque([0])
while que:
	v = que.popleft()
	d[v] = C.pop()
	for w in edge[v]:
		if d[w] < 0:
			que.append(w)
print(M)
print(*d)


import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
g = [[] for _ in range(n + 1)]
v = [0 for _ in range(n + 1)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	g[a].append(b)
	g[b].append(a)
c = sorted([int(i) for i in input().split()])[::-1]

def bfs(x):
	p = []
	q = [x]
	while q:
		y = q.pop()
		v[y] = 1
		p.append(y)
		for nb in g[y]:
			if v[nb] != 1:
				q.append(nb)
	return p
l = bfs(1)
ans = [0] * n
for i in range(n):
	ans[l[i] - 1] = c[i]
print(sum(c[1:]))
print(*ans)


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


N = int(input())
G = [[] for i in range(N + 1)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	G[a].append(b)
	G[b].append(a)
C = list(map(int, input().split()))
C.sort(reverse=True)
S = sum(C[1:])
num = [0 for i in range(N + 1)]
un_used = [True for i in range(N + 1)]
q = []
q.append(1)
un_used[1] = False
while q:
	node = q.pop(0)
	num[node] = C.pop(0)
	for i in range(len(G[node])):
		if un_used[G[node][i]]:
			un_used[G[node][i]] = False
			q.append(G[node][i])
print(S)
print(' '.join(map(str, num[1:])))


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:])


import heapq as hq
N = int(input())
adj = [set() for _ in range(N)]
assignment = [None] * N
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	adj[a - 1].add(b - 1)
	adj[b - 1].add(a - 1)
C = sorted(map(int, input().split()))
score = sum(C[:-1])
stack = [0]
assignment = [None] * N
while stack:
	v = stack.pop()
	if assignment[v] is not None:
		continue
	assignment[v] = C.pop()
	for u in adj[v]:
		stack.append(u)
print(score)
print(*assignment)


N = int(input())
AB = [list(map(int, input().split())) for _ in [0] * (N - 1)]
(*C,) = sorted(map(int, input().split()))
print(sum(C[:-1]))
E = [[] for _ in [0] * N]
d = [0] * N
for (a, b) in AB:
	E[a - 1].append(b - 1)
	E[b - 1].append(a - 1)
for i in range(N):
	if len(E[i]) > 1:
		break
q = [i]
while q:
	i = q.pop()
	d[i] = C.pop()
	for j in E[i]:
		if d[j] != 0:
			continue
		q.append(j)
print(*d)


n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
c = list(map(int, input().split()))
c = sorted(c)[::-1]
g = {}
for i in range(1, n + 1):
	g[i] = []
for (a, b) in ab:
	g[a].append(b)
	g[b].append(a)
from collections import deque
q = deque([g[1]])
done = [0] * (n + 1)
done[1] = 1
ans = [0] * n
ans[0] = c[0]
cnt = 1
while q:
	v = q.popleft()
	for v_ in v:
		if done[v_] == 0:
			done[v_] = 1
			ans[v_ - 1] = c[cnt]
			cnt += 1
			q.append(g[v_])
print(sum(c[1:]))
for i in ans:
	print(i, end=' ')
print()


from collections import deque
N = int(input())
E = [[] for _ in range(N)]
V = [0] * N
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	E[a].append(b)
	E[b].append(a)
	V[a] += 1
	V[b] += 1
C = list(map(int, input().split()))
C.sort(reverse=True)
for i in range(N):
	if V[i] == 1:
		s = i
		break
q = deque([s])
V = [0] * N
l = 0
for l in range(N):
	t = q.popleft()
	V[t] = C[l]
	for v in E[t]:
		if V[v] == 0:
			q.append(v)
print(sum(C) - C[0])
print(' '.join(map(str, V)))


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

def dfs(x):
	global cnt
	ans[x] = c[-cnt - 1]
	visited[x] = 1
	for next in ab[x]:
		if visited[next] == 0:
			cnt += 1
			dfs(next)
dfs(0)
print(*ans)


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


n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	edge[a].append(b)
	edge[b].append(a)
c = list(map(int, input().split()))
c.sort(reverse=1)
print(sum(c) - c[0])
d = [-1] * n
d[0] = c[0]
Q = [0]
visited = {0}
ind = 1
while Q:
	P = []
	for i in Q:
		for j in edge[i]:
			if j in visited:
				continue
			visited.add(j)
			d[j] = c[ind]
			ind += 1
			P.append(j)
	Q = P
print(*d)


from collections import deque
n = int(input())
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(a, b) = list(map(int, input().split()))
	g[a].append(b)
	g[b].append(a)
c = sorted(list(map(int, input().split())))
print(sum(c[:-1]))
q = deque([1])
visit = [0] * (n + 1)
ans = [''] * (n + 1)
while len(q) > 0:
	u = q.popleft()
	visit[u] = 1
	ans[u] = str(c.pop())
	for v in g[u]:
		if visit[v]:
			continue
		q.append(v)
print(' '.join(ans[1:]))


N = int(input())
E = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	E[a].append(b)
	E[b].append(a)
C = list(map(int, input().split()))
C.sort(reverse=True)
ans = [0] * N
stack = [0]
ans[0] = C[0]
k = 1
while stack:
	n = stack.pop()
	for to in E[n]:
		if ans[to] != 0:
			continue
		ans[to] = C[k]
		k += 1
		stack.append(to)
print(sum(C[1:]))
print(' '.join(map(str, ans)))


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


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:])


from collections import deque
N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	adj[a].append(b)
	adj[b].append(a)
c = list(map(int, input().split()))
c.sort(reverse=True)
score = sum(c) - max(c)
num = [-1] * N
que = deque()
que.append(0)
i = 0
while que:
	v = que.pop()
	if num[v] != -1:
		continue
	num[v] = c[i]
	i += 1
	for nv in adj[v]:
		que.append(nv)
print(score)
print(*num)


from collections import deque
N = int(input())
edges = [[] for _ in range(N)]
edgeList = []
for _ in range(N - 1):
	(fr, to) = map(int, input().split())
	fr -= 1
	to -= 1
	edges[fr].append(to)
	edges[to].append(fr)
	edgeList.append((fr, to))
C = list(map(int, input().split()))
C.sort()
M = sum(C) - C[-1]
values = [-1] * N
que = deque([0])
while que:
	now = que.popleft()
	values[now] = C.pop()
	for to in edges[now]:
		if values[to] == -1:
			que.append(to)
print(M)
print(*values)


n = int(input())
tree = [set() for i in range(n)]
con = [0] * n
ans = [0] * n
scr = 0
for _ in range(n - 1):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	tree[a].add(b)
	tree[b].add(a)
	con[a] += 1
	con[b] += 1
st = []
for i in range(n):
	if con[i] == 1:
		st.append(i)
c = list(map(int, input().split()))
c.sort(reverse=True)
while st:
	v = st.pop()
	if ans[v]:
		continue
	ans[v] = c.pop()
	scr += ans[v] * con[v]
	con[v] = 0
	for x in tree[v]:
		if ans[x]:
			continue
		con[x] -= 1
		if con[x] <= 1:
			st.append(x)
print(scr)
print(' '.join(map(str, ans)))


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


import sys
from collections import defaultdict as dd
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = int(input())
e = dd(list)
for _ in range(N - 1):
	(u, v) = map(int, input().split())
	e[u].append(v)
	e[v].append(u)
c = list(map(int, input().split()))
c.sort()
sm = sum(c) - c[-1]
res = [0] * (N + 1)

def dfs(x):
	global res
	res[x] = c.pop()
	for y in e[x]:
		if res[y]:
			continue
		dfs(y)
dfs(1)
print(sm)
print(*res[1:])


import sys
sys.setrecursionlimit(10 ** 6)

def DFS(num, pre):
	global point
	if color[num] == 'white':
		A[num] = C.pop()
		point += min(A[num], pre)
		color[num] = 'black'
		for i in tree[num]:
			DFS(i, A[num])
n = int(input())
AB = [list(map(int, input().split())) for _ in range(n - 1)]
C = sorted(list(map(int, input().split())))
color = ['white' for _ in range(n + 1)]
tree = [[] for _ in range(n + 1)]
for (a, b) in AB:
	tree[a].append(b)
	tree[b].append(a)
A = [0 for _ in range(n + 1)]
point = 0
DFS(1, 0)
print(point)
print(*A[1:])


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


from collections import deque
N = int(input())
ki = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	ki[a].append(b)
	ki[b].append(a)
c = list(map(int, input().split()))
c.sort()
c.reverse()
point = 1
lis = [0] * N
que = deque([0])
lis[0] = c[0]
while len(que) != 0:
	p = que.popleft()
	for i in ki[p]:
		if lis[i] == 0:
			que.append(i)
			lis[i] = c[point]
			point += 1
print(sum(c) - c[0])
print(' '.join(map(str, lis)))


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]))


import sys
sys.setrecursionlimit(10 ** 9)
import heapq
N = int(input())
E = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N - 1)]
C = sorted(list(map(lambda x: int(x) * -1, input().split())))
m = -sum(C[1:])
heapq.heapify(C)
V = [set() for _ in range(N)]
for (u, v) in E:
	V[u].add(v)
	V[v].add(u)
A = [0 for _ in range(N)]

def dfs(v, s):
	A[v] = -heapq.heappop(C)
	for u in V[v]:
		if u != s:
			dfs(u, v)
dfs(0, -1)
print(m)
print(*A)


N = int(input())
E = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	E[a - 1].append(b - 1)
	E[b - 1].append(a - 1)
C = sorted(list(map(int, input().split())))[::-1]
ans = [-1 for i in range(N)]
point = sum(C[1:])
from collections import deque
q = deque([])
q.append(0)
ind = 0
while q:
	v = q.popleft()
	if ans[v] != -1:
		continue
	ans[v] = C[ind]
	ind += 1
	if ind == len(C):
		break
	children = E[v]
	for child in children:
		q.append(child)
print(point)
print(*ans)


from collections import deque
n = int(input())
e = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	e[a].append(b)
	e[b].append(a)
l = sorted(list(map(int, input().split())), reverse=True)
ans = [-1] * n
q = deque([])
q.append(0)
ans[0] = l[0]
now = 1
while q:
	b = q.popleft()
	for nex in e[b]:
		if ans[nex] == -1:
			ans[nex] = l[now]
			now += 1
			q.append(nex)
count = 0
for j in range(n):
	for k in e[j]:
		count += min(ans[j], ans[k])
print(count // 2)
print(*ans)


import sys
sys.setrecursionlimit(10000000)
n = int(input())
G = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	G[a - 1].append(b - 1)
	G[b - 1].append(a - 1)
c = list(map(int, input().split()))
c.sort()
node = [0] * n
used = [False] * n

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


import sys
read = sys.stdin.read
readline = sys.stdin.readline
(N, *abc) = map(int, read().split())
c = abc[2 * (N - 1):]
c.sort()
graph = [[] for _ in range(N + 1)]
for (a, b) in zip(*[iter(abc[:2 * (N - 1)])] * 2):
	graph[a].append(b)
	graph[b].append(a)
nodes = [0] * (N + 1)
score = sum(c) - c[-1]
start = 1
nodes[start] = c.pop()
queue = [start]
while queue:
	V = queue.pop()
	for v in graph[V]:
		if nodes[v] == 0:
			nodes[v] = c.pop()
			queue.append(v)
print(score)
print(' '.join(map(str, nodes[1:])))


from collections import deque
N = int(input())
X = [[] for i in range(N)]
Y = [-1] * N
for i in range(N - 1):
	(x, y) = map(int, input().split())
	X[x - 1].append(y - 1)
	X[y - 1].append(x - 1)
C = sorted([int(a) for a in input().split()])
print(sum(C) - max(C))
que = deque([0])
while que:
	i = deque.popleft(que)
	if Y[i] < 0:
		Y[i] = C.pop()
		for a in X[i]:
			deque.append(que, a)
print(*Y)


import collections
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 = sorted(c, reverse=True)
m = sum(c) - c[0]
ans = [0] * (n + 1)
ans[1] = c[0]
q = collections.deque()
q.append(1)
checked = [0] * (n + 1)
checked[1] = 1
cnt = 1
while len(q):
	tmp = q.popleft()
	for v in g[tmp]:
		if checked[v] == 0:
			checked[v] = 1
			q.append(v)
			ans[v] = c[cnt]
			cnt += 1
print(m)
print(*ans[1:])


N = int(input())
edge = [list(map(int, input().split())) for i in range(N - 1)]
C = list(map(int, input().split()))
from heapq import heapify, heappop
for i in range(N):
	C[i] = -C[i]
heapify(C)
c = [[] for i in range(N)]
for (i, j) in edge:
	c[i - 1].append(j - 1)
	c[j - 1].append(i - 1)
d = [-1] * N
d[0] = -heappop(C)
v = [0] * N
v[0] = 1
SUM = d[0]
import sys
sys.setrecursionlimit(10 ** 5)

def dfs(p, v, d):
	global SUM
	for n in c[p]:
		if v[n] == 0:
			d[n] = -heappop(C)
			SUM += d[n]
			v[n] = 1
			dfs(n, v, d)
dfs(0, v, d)
print(SUM - d[0])
for i in range(N - 1):
	print(d[i], end=' ')
print(d[N - 1])


from collections import deque
n = int(input())
ki = [[] for i in range(n)]
d = [0 for i in range(n)]
for i in range(n - 1):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	ki[a].append(b)
	ki[b].append(a)
c = list(map(int, input().split()))
c.sort(reverse=True)
c = deque(c)
ans = 0
d[0] = c.popleft()
q = deque()
q.append(0)
while q:
	now = q.popleft()
	for i in ki[now]:
		if d[i] == 0:
			d[i] = c.popleft()
			q.append(i)
			ans += d[i]
print(ans)
print(*d)


from collections import Counter
import sys
sys.setrecursionlimit(10 ** 7)
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N - 1):
	(fr, to) = map(int, input().split())
	fr -= 1
	to -= 1
	edges[fr].append(to)
	edges[to].append(fr)
A = list(map(int, input().split()))
A.sort()
S = sum(A) - A[-1]
print(S)
ans = [0] * N
st = [(0, -1)]
while st:
	(now, pr) = st.pop()
	ans[now] = A.pop()
	for to in edges[now]:
		if to == pr:
			continue
		st.append((to, now))
print(*ans)


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


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)
l = [[] for i in range(n + 1)]
ans = [0 for i in range(n + 1)]
ans[1] = c[0]
q = [1]
ci = 1
for (a, b) in ab:
	l[a].append(b)
	l[b].append(a)
while len(q) > 0:
	t = q.pop()
	tl = l[t]
	for i in tl:
		if ans[i] == 0:
			ans[i] = c[ci]
			ci += 1
			q.append(i)
print(sum(c[1:]))
print(' '.join(map(str, ans[1:])))


import heapq
n = int(input())
g = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
c = list(map(lambda x: -int(x), input().split()))
heapq.heapify(c)
print(min(c) - sum(c))
ans = []
s = [-1] * n
leaf = -1
for (i, a) in enumerate(g):
	if len(a) == 1:
		leaf = i
		break
que = [leaf]
while que:
	t = que.pop()
	for e in g[t]:
		if s[e] == -1:
			s[e] = -heapq.heappop(c)
			que.append(e)
print(*s)


from collections import deque
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	graph[a].append(b)
	graph[b].append(a)
c = list(map(int, input().split()))
c.sort()
score = sum(c) - c[-1]
for i in range(n):
	if len(graph[i]) == 1:
		next_v = deque([i])
		break
ans = [-1] * n
while next_v:
	v = next_v.popleft()
	ans[v] = c.pop()
	for i in graph[v]:
		if ans[i] != -1:
			continue
		next_v.append(i)
print(score)
print(*ans, sep=' ')


n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
c = list(map(int, input().split()))
c.sort(reverse=True)
edges = [[] for _ in range(n)]
ans = [-1] * n
ans[0] = c[0]
count = 1
for (a, b) in ab:
	edges[a - 1].append(b - 1)
	edges[b - 1].append(a - 1)
q = [0]
while q:
	l = q.pop(-1)
	for l1 in edges[l]:
		if ans[l1] == -1:
			q.append(l1)
			ans[l1] = c[count]
			count += 1
print(sum(c[1:]))
for i in ans:
	print(i, end=' ')


n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	graph[a].append(b)
	graph[b].append(a)
c = [int(i) for i in input().split()]
c.sort()
c.reverse()
ans_list = [0 for _ in range(n)]
ans = 0
p_list = [0]
ans_list[0] = c.pop(0)
while len(p_list) > 0:
	p = p_list.pop(0)
	for g in graph[p]:
		if ans_list[g] == 0:
			ans_list[g] = c.pop(0)
			ans += ans_list[g]
			p_list.append(g)
print(ans)
print(' '.join([str(i) for i in ans_list]))


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


N = int(input())
L = [list(map(int, input().split())) for k in range(N - 1)]
c = sorted(list(map(int, input().split())))
a = sum(c) - c[-1]
T = [[] for k in range(N)]
for e in L:
	T[e[0] - 1].append(e[1] - 1)
	T[e[1] - 1].append(e[0] - 1)
kyori = [-1 for k in range(N)]
que = [L[0][0]]
kyori[L[0][0]] = c.pop()
while len(que) > 0:
	now = que.pop()
	for tsugi in T[now]:
		if kyori[tsugi] == -1:
			kyori[tsugi] = c.pop()
			que.append(tsugi)
print(a)
print(*kyori, sep=' ')


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:])


import sys
sys.setrecursionlimit(4100000)
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	edges[a - 1].append(b - 1)
	edges[b - 1].append(a - 1)
C = list(map(int, input().split()))
C.sort(reverse=True)
D = [0] * N

def dfs(x, parent, index):
	D[x] = C[index]
	index += 1
	for u in edges[x]:
		if u != parent:
			index = dfs(u, x, index)
	return index
dfs(0, -1, 0)
print(sum(C[1:]))
print(*D)


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


from collections import deque

def bfs():
	q = deque()
	q.append(1)
	ans = [0] * n
	i = 0
	while q:
		p = q.popleft()
		ans[p - 1] = c[i]
		i += 1
		for j in G[p]:
			if ans[j - 1] == 0:
				q.append(j)
	return ans
n = int(input())
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	G[a].append(b)
	G[b].append(a)
c = list(map(int, input().split()))
c.sort(reverse=True)
s = sum(c) - c[0]
ans = bfs()
print(s)
print(*ans)


import heapq
import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
g = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	g[a - 1].append(b - 1)
	g[b - 1].append(a - 1)
c = [-i for i in list(map(int, input().split()))]
heapq.heapify(c)
print(-sum(c) + min(c))
for i in range(n):
	if len(g[i]) == 1:
		start = i
		break
ans = [-1] * n
ans[start] = -heapq.heappop(c)
q = [start]
while q:
	now = q.pop(-1)
	for i in g[now]:
		if ans[i] == -1:
			ans[i] = -heapq.heappop(c)
			q.append(i)
for i in ans:
	print(i)


N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	G[a].append(b)
	G[b].append(a)
(*C,) = map(int, input().split())
C.sort(reverse=True)
ans = [-1] * N
stk = [0]
ans[0] = C[0]
idx = 1
while stk:
	v = stk.pop()
	for to in G[v]:
		if ans[to] > 0:
			continue
		ans[to] = C[idx]
		idx += 1
		stk.append(to)
print(sum(C) - C[0])
print(*ans)


import sys
import resource
sys.setrecursionlimit(20000)
n = int(input())
edges = [list(map(int, input().split())) for i in range(n - 1)]
e = [[] for i in range(n)]
for (a, b) in edges:
	a -= 1
	b -= 1
	e[a].append(b)
	e[b].append(a)
c = sorted(list(map(int, input().split())))
print(sum(c[:-1]))
visited = [False for i in range(n)]
node = [0] * n
cnt = 0

def dfs(pos):
	global cnt, node, c
	if visited[pos]:
		return
	visited[pos] = True
	for p in e[pos]:
		dfs(p)
	node[pos] = c[cnt]
	cnt += 1
dfs(0)
print(' '.join(map(str, node)))


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)


import heapq
from collections import deque
n = int(input())
graph = [set() for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	graph[a].add(b)
	graph[b].add(a)
nodes = [False for _ in range(n)]
values = list(map(lambda x: -int(x), input().split()))
print(-sum(values) + min(values))
heapq.heapify(values)
next_nodes = deque()
next_nodes.append(0)
while next_nodes:
	node = next_nodes.popleft()
	nodes[node] = -heapq.heappop(values)
	for g in graph[node]:
		if not nodes[g]:
			next_nodes.append(g)
print(*nodes)


import sys
sys.setrecursionlimit(200010)
N = int(input())
tree = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	tree[a].append(b)
	tree[b].append(a)
c = [int(s) for s in input().split()]
c.sort(reverse=True)
anst = [0] * (N + 1)
anss = 0

def visit(a, prev):
	global anst, anss
	ans = 0
	for b in tree[a]:
		if b != prev:
			ci = visit(b, a)
			anss += ci
	ci = c.pop()
	anst[a] = ci
	return ci
visit(1, 1)
print(anss)
print(' '.join((str(i) for i in anst[1:])))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
n = int(input())
edges = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	edges[a].append(b)
	edges[b].append(a)
cost = sorted(map(int, input().split()))
m = 0
ans = [None] * n

def dfs(v, parent):
	ans[v] = cost.pop()
	if parent != -1:
		global m
		m += min(ans[v], ans[parent])
	for v2 in edges[v]:
		if v2 == parent:
			continue
		dfs(v2, v)
dfs(0, -1)
print(m)
print(*ans)


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)


n = int(input())
nodes = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	nodes[a].append(b)
	nodes[b].append(a)
c = list(map(int, input().split()))
c.sort(reverse=True)
count = 0
answer = [0 for _ in range(n)]
for i in range(n):
	end = True
	for j in range(n):
		if len(nodes[j]) == 1:
			end = False
			nodes[nodes[j][0]].remove(j)
			nodes[j].pop()
			answer[j] = c.pop()
			count += answer[j]
	if end:
		break
print(sum(answer))
answer[answer.index(0)] = c.pop()
print(' '.join(map(str, answer)))


n = int(input())
T = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	T[a].append(b)
	T[b].append(a)
C = sorted(map(int, input().split()))
print(sum(C[:-1]))
L = [-1] * n
stack = [0]
while stack:
	temp = stack.pop()
	L[temp] = C.pop()
	for v in T[temp]:
		if L[v] == -1:
			stack.append(v)
print(*L)


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]))


import sys
sys.setrecursionlimit(10 ** 9)
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)
clst = list(map(int, input().split()))
clst.sort(reverse=True)
ans = [0 for _ in range(n)]
ind = 0
total = 0

def dfs(pos, b_pos, b_num):
	global ind, total
	ans[pos] = clst[ind]
	total += min(ans[pos], b_num)
	ind += 1
	for n_pos in edges[pos]:
		if n_pos == b_pos:
			continue
		dfs(n_pos, pos, ans[pos])
dfs(0, -1, 0)
print(total)
print(*ans)


n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
cl = list(map(int, input().split()))
cl.sort(reverse=True)
e = [set() for _ in range(n)]
for (a, b) in ab:
	a -= 1
	b -= 1
	e[a].add(b)
	e[b].add(a)
used = [False] * n
q = [0]
res = [0] * n
i = 0
while len(q) > 0:
	u = q.pop()
	res[u] = cl[i]
	used[u] = True
	i += 1
	for v in e[u]:
		if not used[v]:
			q.append(v)
r = 0
for (a, b) in ab:
	r += min(res[a - 1], res[b - 1])
print(r)
print(*res)


N = int(input())
es = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	es[a - 1].append(b - 1)
	es[b - 1].append(a - 1)
C = list(map(int, input().split()))
C.sort(reverse=True)
D = [0 for _ in range(N)]
stack = es[0]
D[0] = C[0]
cnt_c = 1
while stack:
	new_stack = []
	for i in stack:
		if D[i] == 0:
			D[i] = C[cnt_c]
			cnt_c += 1
			new_stack.extend(es[i])
	if len(new_stack) == 0:
		break
	else:
		stack = new_stack
print(sum(D) - C[0])
print(*D)


from collections import deque
N = int(input())
branch = [0] * (N - 1)
for i in range(N - 1):
	branch[i] = list(map(int, input().split()))
C = list(map(int, input().split()))
C.sort(reverse=True)
M = sum(C[1:])
adj = [[] for i in range(N + 1)]
for i in range(N - 1):
	(a, b) = branch[i]
	adj[a].append(b)
	adj[b].append(a)
ans = [-1] * (N + 1)
deq = deque()
deq.appendleft(1)
while len(deq) > 0:
	v = deq.pop()
	ans[v] = C.pop(0)
	for u in adj[v]:
		if ans[u] == -1:
			deq.appendleft(u)
print(M)
print(' '.join(map(str, ans[1:])))


n = int(input())
e = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	e[a].append(b)
	e[b].append(a)
c = list(map(int, input().split()))
c.sort()
print(sum(c[:-1]))
c.reverse()
ans = [0 for i in range(n)]
ans[0] = c[0]
k = 1
s = [0]
while s:
	ns = []
	for i in s:
		for j in e[i]:
			if ans[j]:
				continue
			ans[j] = c[k]
			k += 1
			ns.append(j)
	s = ns
print(' '.join(map(str, ans)))


from collections import deque
n = int(input())
d = dict()
edge = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	edge[a].append(b)
	edge[b].append(a)
c = list(map(int, input().split()))
c.sort(reverse=True)
visited = [-1] * n

def bfs(s):
	i = 0
	q = deque([s])
	visited[s] = c[i]
	while q:
		x = q.popleft()
		for nx in edge[x]:
			if visited[nx] == -1:
				i += 1
				visited[nx] = c[i]
				q.append(nx)
	return
bfs(0)
print(sum(c) - max(c))
print(*visited)


from collections import deque
n = int(input())
es = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	es[a - 1].append(b - 1)
	es[b - 1].append(a - 1)
c = list(map(int, input().split()))
c.sort()
print(sum(c) - c[-1])
d = [0] * n
q = deque([0])
d[0] = c.pop()
while q:
	v = q.popleft()
	for e in es[v]:
		if d[e] == 0:
			d[e] = c.pop()
			q.append(e)
print(*d)


from collections import deque
n = int(input())
ab = [list(map(int, input().split())) for i in range(n - 1)]
c = sorted(list(map(int, input().split())), reverse=True)
tree = [list() for i in range(n)]
already = [1] * n
ans = [0] * n
k = 0
queue = deque([0])
for (index, (a, b)) in enumerate(ab):
	a -= 1
	b -= 1
	tree[a].append((index, b))
	tree[b].append((index, a))
while queue:
	now = queue.popleft()
	already[now] = 0
	ans[now] = c[k]
	k += 1
	for (index, i) in tree[now]:
		if already[i]:
			queue.append(i)
print(sum(c[1:]))
print(*ans)


import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
edge = [[] for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	edge[a].append(b)
	edge[b].append(a)
C = list(map(int, input().split()))
C.sort(reverse=True)
nodes = [0] * N
cidx = -1
ans = []

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


from collections import deque
n = int(input())
t = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	t[a].append(b)
	t[b].append(a)
c = sorted(list(map(int, input().split())))
queue = deque([0])
ans = [0 for i in range(n)]
num = n - 1
while queue:
	cur_node = queue.popleft()
	if ans[cur_node] > 0:
		continue
	ans[cur_node] = c[num]
	num -= 1
	for i in t[cur_node]:
		queue.append(i)
print(sum(c) - max(c))
print(*ans)


from collections import deque
N = int(input())
es = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	es[a].append(b)
	es[b].append(a)
c = list(map(int, input().split()))
c.sort(reverse=1)
q = deque()
q.append(0)
flg = [0] * N
num = [None] * N
i = 0
while len(q):
	v = q.popleft()
	flg[v] = 1
	num[v] = c[i]
	i += 1
	for u in es[v]:
		if flg[u]:
			continue
		q.append(u)
print(sum(c[1:]))
print(*num)


n = int(input())
route = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = (x - 1 for x in map(int, input().split()))
	route[a] += [b]
	route[b] += [a]
c = list(map(int, input().split()))
c.sort(reverse=1)
check = [False] * n
ans = [0] * n
cnt = 0
q = [0]
while q:
	cur = q[0]
	q = q[1:]
	check[cur] = True
	ans[cur] = c[cnt]
	cnt += 1
	for r in route[cur]:
		if check[r]:
			continue
		q.append(r)
print(sum(ans[1:]))
print(*ans)


import sys
input = sys.stdin.readline
n = int(input())
edge = [set() for i in range(n + 1)]
for i in range(n - 1):
	(a, b) = [int(j) for j in input().split()]
	edge[a].add(b)
	edge[b].add(a)
c = [int(j) for j in input().split()]
d = [len(i) for i in edge]
d1 = [i for (i, x) in enumerate(d) if x == 1]
ans = [None] * (n + 1)
c.sort()
c.reverse()
m = sum(c) - c[0]
while d1:
	v = d1.pop()
	if not d1:
		ans[v] = c.pop()
		break
	w = edge[v].pop()
	edge[w].remove(v)
	d[w] -= 1
	if d[w] == 1:
		d1.append(w)
	ans[v] = c.pop()
print(m)
print(*ans[1:])


import queue
N = int(input())
edge = [set([]) for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	edge[a].add(b)
	edge[b].add(a)
c = list(map(int, input().split()))
c.sort()
q = queue.Queue()
for i in range(N):
	if len(edge[i]) == 1:
		q.put(i)
ans = [0] * N
i = 0
while not q.empty():
	j = q.get()
	ans[j] = c[i]
	i += 1
	if len(edge[j]) == 0:
		continue
	k = list(edge[j])[0]
	edge[k].remove(j)
	if len(edge[k]) == 1:
		q.put(k)
print(sum(c[:-1]))
for i in ans:
	print(i, end=' ')
print()


N = int(input())
AB = [tuple(map(int, input().split())) for i in range(N - 1)]
C = list(map(int, input().split()))
C.sort()
es = [[] for _ in range(N)]
for (a, b) in AB:
	(a, b) = (a - 1, b - 1)
	es[a].append(b)
	es[b].append(a)
stack = [0]
ans = [-1] * N
ans[0] = C.pop()
m = 0
while stack:
	v = stack.pop()
	for to in es[v]:
		if ans[to] >= 0:
			continue
		ans[to] = C.pop()
		m += ans[to]
		stack.append(to)
print(m)
print(*ans)


from collections import deque
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]
C = list(map(int, input().split()))
C.sort()
C = C[::-1]
graph = [[] for _ in range(N + 1)]
check = [1] * (N + 1)
for (A, B) in AB:
	graph[A].append(B)
	graph[B].append(A)
answer = [0] * (N + 1)
stack = deque()
stack.append(1)
check[1] = 0
ci = 0
while stack:
	s = stack.popleft()
	answer[s] = C[ci]
	ci += 1
	for g in graph[s]:
		if check[g]:
			check[g] = 0
			stack.append(g)
print(sum(C) - max(C))
print(*answer[1:])


n = int(input())
if n == 1:
	c = int(input())
	print(c)
	print(c)
	quit()
line = [list(map(int, input().split())) for i in range(n - 1)]
c = list(map(int, input().split()))
c.sort(reverse=True)
print(sum(c) - c[0])
ans = [0] * n
vis = [True] * n
(a, b) = line[0]
a -= 1
b -= 1
ans[a] = c[0]
ans[b] = c[1]
vis[a] = False
vis[b] = False
for i in range(1, n - 1):
	for l in line:
		(a, b) = l
		a -= 1
		b -= 1
		if vis[a] and (not vis[b]):
			ans[a] = c[i + 1]
			vis[a] = False
			break
		elif vis[b] and (not vis[a]):
			ans[b] = c[i + 1]
			vis[b] = False
			break
ans = list(map(str, ans))
print(' '.join(ans))


import sys
input = sys.stdin.readline
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
Ans = [0] * n
q = [0]
Used[0] = True
while q:
	v = q.pop()
	Ans[v] = C.pop()
	for u in Edges[v]:
		if not Used[u]:
			Used[u] = True
			q.append(u)
print(*Ans)


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

def bfs(v, p):
	q = deque()
	q.append((v, p))
	rec[v - 1] = c.pop()
	while c:
		(V, P) = q.popleft()
		for nv in G[V - 1]:
			if nv == P:
				continue
			rec[nv - 1] = c.pop()
			q.append((nv, V))
n = int(input())
ab = [list(map(int, input().split())) for i in range(n - 1)]
c = list(map(int, input().split()))
c.sort()
G = Graph(ab)
print(sum(c[:-1]))
rec = [0] * n
bfs(1, -1)
print(*rec)


from collections import deque
N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N - 1)]
C = sorted(map(int, input().split()))
G = [[] for _ in range(N)]
for (a, b) in AB:
	a -= 1
	b -= 1
	G[a].append(b)
	G[b].append(a)
deq = deque((i for i in range(N) if len(G[i]) == 1))
D = [len(G[i]) for i in range(N)]
X = [0] * N
for c in C:
	i = deq.popleft()
	X[i] = c
	for j in G[i]:
		D[j] -= 1
		if D[j] == 1:
			deq.append(j)
ans = 0
for (a, b) in AB:
	ans += min(X[a - 1], X[b - 1])
print(ans)
print(*X)


from queue import Queue
N = int(input())
node_array = [[] for i in range(N)]
for _ in range(N - 1):
	(i, j) = map(int, input().split())
	node_array[i - 1].append(j - 1)
	node_array[j - 1].append(i - 1)
c_array = sorted(map(int, input().split()), reverse=True)
ans = sum(c_array[1:])
ans_array = [-1] * N
edge = Queue()
edge.put(0)
ans_array[0] = 0
for i in range(N):
	item = edge.get()
	ans_array[item] = str(c_array[i])
	for j in node_array[item]:
		if ans_array[j] == -1:
			edge.put(j)
			ans_array[j] == 0
print(ans)
print(' '.join(ans_array))


import collections
n = int(input())
graph = []
for i in range(n + 1):
	graph.append([])
for i in range(n - 1):
	(a, b) = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)
c = list(map(int, input().split()))
c.sort()
c.reverse()
ans = ['0'] * n
pointer = 0
queue = collections.deque([[1, 1]])
while queue:
	a = queue.popleft()
	ans[a[0] - 1] = str(c[pointer])
	for i in graph[a[0]]:
		if i == a[1]:
			continue
		queue.append([i, a[0]])
	pointer += 1
print(sum(c) - c[0])
print(' '.join(ans))


from collections import deque
N = int(input())
edge = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = map(int, input().split())
	edge[a - 1] += [b - 1]
	edge[b - 1] += [a - 1]
A = list(map(int, input().split()))
A.sort(reverse=1)
print(sum(A[1:]))
ans = [[0, A[0]]]
cnt = 1
visited = [1] + [0] * (N - 1)
que = deque([0])
while que:
	u = que.pop()
	for v in edge[u]:
		if visited[v] == 0:
			que.append(v)
			visited[v] = 1
			ans += [[v, A[cnt]]]
			cnt += 1
ans.sort()
ans2 = []
for i in range(N):
	ans2 += [ans[i][1]]
print(' '.join(map(str, ans2)))


(n, *L) = map(int, open(0).read().split())
ab = L[:2 * n - 2]
c = sorted(L[2 * n - 2:])
con = [[] for _ in range(n)]
ans = [0] * n
tot = sum(c) - max(c)
for (a, b) in zip(*[iter(ab)] * 2):
	con[a - 1].append(b - 1)
	con[b - 1].append(a - 1)
vis = [0] * n
q = [0]
vis[0] = 1
while q:
	cur = q.pop()
	ans[cur] = c.pop()
	for nxt in con[cur]:
		if vis[nxt]:
			continue
		q.append(nxt)
		vis[nxt] = 1
print(tot)
print(*ans)


from collections import deque
N = int(input())
G = {k: [] for k in range(N)}
E = [0] * N
ans = [-1] * N
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	G[a - 1].append(b - 1)
	G[b - 1].append(a - 1)
	E[a - 1] += 1
	E[b - 1] += 1
C = sorted([int(i) for i in input().split()], reverse=True)
print(sum(C[1:]))
ans[E.index(max(E))] = C[0]
que = deque([(E.index(max(E)), -1)])
idx = 0
while que:
	(ci, p) = que.popleft()
	for ni in G[ci]:
		if ni != p:
			idx += 1
			ans[ni] = C[idx]
			que.append((ni, ci))
print(*ans)


def main():
	n = int(input())
	ab = [list(map(int, input().split())) for _ in [0] * (n - 1)]
	c = sorted(list(map(int, input().split())), reverse=True)
	g = [set() for _ in [0] * n]
	[g[a - 1].add(b - 1) for (a, b) in ab]
	[g[b - 1].add(a - 1) for (a, b) in ab]
	l = []
	print(sum(c) - max(c))
	for i in range(n):
		if len(g[i]) == 1:
			l.append(i)
	ans_l = [0] * n
	while l:
		i = l.pop()
		ans_l[i] = c.pop()
		for j in g[i]:
			g[j].remove(i)
			if len(g[j]) == 1:
				l.append(j)
		g[i] = set()
	print(*ans_l)
main()


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)
from collections import deque
n = int(readline())
graph = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = map(int, readline().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
c = list(map(int, readline().split()))
c.sort()
print(sum(c[:-1]))
q = deque([0])
d = [-1] * n
while q:
	x = q.popleft()
	d[x] = c.pop()
	for next in graph[x]:
		if d[next] < 0:
			q.appendleft(next)
print(*d)


import sys

def input():
	return sys.stdin.readline()[:-1]
N = int(input())
s = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	s[a].append(b)
	s[b].append(a)
sys.setrecursionlimit(20000)
l = [None] * N

def hu(n):
	for i in s[n]:
		if l[i] == None:
			l[i] = c.pop()
			hu(i)
c = list(map(int, input().split()))
c.sort()
print(sum(c[:-1]))
l[0] = c.pop()
hu(0)
print(*l)


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)


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)


from collections import defaultdict, deque
d = defaultdict(list)
n = int(input())
for i in range(n - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	d[u].append(v)
	d[v].append(u)
c = list(map(int, input().split()))
c.sort(reverse=True)
vis = [0 for i in range(n)]
q = deque([])
q.append(0)
vis[0] = c[0]
ind = 1
while q:
	f = q.popleft()
	for i in d[f]:
		if not vis[i]:
			vis[i] = c[ind]
			ind += 1
			q.append(i)
print(sum(vis) - c[0])
print(*vis)


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


import sys
sys.setrecursionlimit(10 ** 7)

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


from collections import deque
n = int(input())
edges = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	edges[a - 1].append(b - 1)
	edges[b - 1].append(a - 1)
d = list(map(int, input().split()))
d.sort(reverse=True)
que = deque()
que.append(0)
seen = [False for _ in range(n)]
seen[0] = True
memo = [0]
while que:
	cur = que.popleft()
	for to in edges[cur]:
		if seen[to]:
			continue
		seen[to] = True
		memo.append(to)
		que.append(to)
print(sum(d) - d[0])
ans = [0 for _ in range(n)]
for i in range(n):
	ans[memo[i]] = d[i]
print(*ans)


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

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


import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
E = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	E[a - 1].append(b - 1)
	E[b - 1].append(a - 1)
c = list(map(int, input().split()))
c.sort()
nums = deque(c)
ans = [0] * n

def dfs(cur, pre):
	stack = deque([[cur, pre]])
	while stack:
		(cur, pre) = stack.pop()
		num = nums.pop()
		ans[cur] = str(num)
		for e in E[cur]:
			if e != pre:
				stack.append([e, cur])
dfs(0, -1)
print(sum(c[:-1]))
print(' '.join(ans))


n = int(input())
x = [[] for _ in range(n + 1)]
c = [0 for _ in range(n + 1)]
flag = n
for i in range(n - 1):
	(ai, bi) = map(int, input().split())
	x[ai].append(bi)
	x[bi].append(ai)
	c[ai] += 1
	c[bi] += 1
cc = list(map(int, input().split()))
cc.sort(reverse=True)
print(sum(cc[1:]))
d = [0 for _ in range(n + 1)]
e = [i for i in range(1, n + 1)]
flag = 1
while flag <= n - 1:
	for i in e:
		if c[i] == 1:
			d[i] = flag
			flag += 1
			e.remove(i)
			c[i] = 0
			j = x[i][0]
			x[j].remove(i)
			c[j] -= 1
for i in range(1, n + 1):
	print(cc[-d[i]], end=' ')


from collections import deque
N = int(input())
ab = [[int(i) - 1 for i in input().split()] for _ in range(N - 1)]
c = [int(i) for i in input().split()]
c.sort()
d = [0] * N
vector = [[] for _ in range(N)]
for (a, b) in ab:
	vector[a].append(b)
	vector[b].append(a)
ret = sum(c[:-1])
queue = deque([0])
visited = [False] * N
visited[0] = True
while queue:
	q = queue.popleft()
	for v in vector[q]:
		if not visited[v]:
			queue.append(v)
			visited[v] = True
	d[q] = c.pop()
print(ret)
print(' '.join(map(str, d)))


from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
tree = [[] for _i in range(n)]
for _i in range(n - 1):
	(a, b) = map(int, input().split())
	tree[a - 1].append(b - 1)
	tree[b - 1].append(a - 1)
c = deque(sorted(list(map(int, input().split())), reverse=True))
visit = [-1 for _i in range(n)]
visit[0] = c.popleft()

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


N = int(input())
que = []
edges = {i: [] for i in range(1, N + 1)}
visited = {i: False for i in range(1, N + 1)}
ans = {i: None for i in range(1, N + 1)}
while True:
	s = list(map(int, input().split()))
	if len(s) > 2:
		break
	edges[s[0]].append(s[1])
	edges[s[1]].append(s[0])
s = sorted(s)
ans1 = sum(s[:-1])
que.append(1)
while que:
	temp = que.pop(0)
	if visited[temp]:
		continue
	visited[temp] = True
	ans[temp] = s.pop()
	que += edges[temp]
s = ''
for key in ans:
	if key > 1:
		s += ' '
	s += str(ans[key])
print(ans1)
print(s)


import sys
sys.setrecursionlimit(10 ** 6)
N = int(input())
A = [[] for i in range(N)]
X = [list(map(int, input().split())) for _ in range(N - 1)]
for i in range(N - 1):
	a = X[i][0]
	b = X[i][1]
	a -= 1
	b -= 1
	A[a].append(b)
	A[b].append(a)
D = list(map(int, input().split()))
D = sorted(D)[::-1]
from collections import deque
d = deque(D)
E = [-1] * N

def f(now, pre):
	for i in A[now]:
		if i != pre and E[i] == -1:
			E[i] = d.popleft()
			f(i, now)
E[0] = d.popleft()
f(0, 0)
print(sum(D[1:]))
print(*E)


from collections import defaultdict
import sys
sys.setrecursionlimit(20000000)
connection = defaultdict(lambda : [])
n = int(input())
ab = []
for i in range(n - 1):
	(a, b) = map(int, input().split())
	connection[a].append(b)
	connection[b].append(a)
	ab.append((a, b))
c = list(map(int, input().split()))
c.sort()
ans = [0] * (n + 1)

def dfs(num):
	ans[num] = c.pop()
	for next_num in connection[num]:
		if ans[next_num] == 0:
			dfs(next_num)
dfs(1)
score = 0
for (a, b) in ab:
	score += min(ans[a], ans[b])
print(score)
print(' '.join(map(str, ans[1:])))


from collections import deque
N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	edge[a - 1].append(b - 1)
	edge[b - 1].append(a - 1)
c = list(map(int, input().split()))
c.sort()
c = c[::-1]
max = c[0]
ans = [0 for i in range(N)]
d = [-1 for i in range(N)]
d[0] = 0
ans[0] = c.pop(0)
q = deque([0 * (N - 1)])
while len(q) > 0:
	u = q.popleft()
	for v in edge[u]:
		if d[v] > -1:
			continue
		d[v] = d[u] + 1
		ans[v] = c.pop(0)
		q.append(v)
print(sum(ans) - max)
print(*ans, sep=' ')


from collections import deque
N = int(input())
link = [[] * N for _ in range(N)]
for i in range(N - 1):
	(a, b) = map(lambda x: int(x) - 1, input().split())
	link[a].append(b)
	link[b].append(a)
c = list(map(int, input().split()))
c = sorted(c, reverse=True)
sums = sum(c) - max(c)
q = deque([0])
d = [-1] * N
num = 0
while len(q) > 0:
	x = q.popleft()
	d[x] = c[num]
	num += 1
	for y in link[x]:
		if d[y] < 0:
			q.append(y)
print(sums)
print(*d)


from collections import deque
n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)
c = list(map(int, input().split()))
c.sort()
m = sum(c[:-1])
ans = [-1] * n
q = deque([(0, -1)])
while q:
	(v, pv) = q.popleft()
	ans[v] = c.pop()
	for nv in g[v]:
		if nv == pv:
			continue
		q.append((nv, v))
print(m)
print(*ans)


N = int(input())
from collections import defaultdict
branch = defaultdict(set)
for i in range(N - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	branch[a] |= {b}
	branch[b] |= {a}
C = list(map(int, input().split()))
C.sort()
ans = [0] * N
used = {0}
check = {0}
M = sum(C[:-1])
while len(check) > 0:
	now = check.pop()
	ans[now] = C.pop()
	for nex in branch[now]:
		if nex not in used:
			check |= {nex}
			used |= {nex}
print(M)
print(' '.join([str(x) for x in ans]))


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


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)


N = int(input())
import collections
Ls = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	Ls[a - 1].append(b - 1)
	Ls[b - 1].append(a - 1)
Cs = sorted(map(int, input().split()))
print(sum(Cs) - max(Cs))
sw = [-1] * N
stk = collections.deque([0])
while len(stk) > 0:
	crN = stk.popleft()
	if sw[crN] < 0:
		sw[crN] = Cs.pop()
		for l in Ls[crN]:
			stk.append(l)
print(*sw)


n = int(input())
link = [[] for _ in range(n)]
for i in range(n - 1):
	(a, b) = list(map(int, input().split()))
	link[a - 1].append(b - 1)
	link[b - 1].append(a - 1)
c = list(map(int, input().split()))
c.sort(reverse=True)
print(sum(c) - c[0])
from collections import deque
Q = deque()
Q.append(0)
visited = [-1] * n
visited[0] = 0
ind = 1
while Q:
	now = Q.popleft()
	for nxt in link[now]:
		if visited[nxt] != -1:
			continue
		visited[nxt] = ind
		ind += 1
		Q.append(nxt)
for i in visited:
	print(c[i], end=' ')


n = int(input())
e = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	e[a - 1].append(b - 1)
	e[b - 1].append(a - 1)
(c, Q, l, i) = (sorted(list(map(int, input().split())))[::-1], [0], [0] * n, 0)
print(sum(c[1:]))
while Q:
	a = Q.pop()
	if l[a] != 0:
		continue
	l[a] = c[i]
	i += 1
	for j in e[a]:
		Q.append(j)
print(*l)


n = int(input())
a = [[] for i in range(n + 1)]
for i in range(n - 1):
	(b, c) = map(int, input().split())
	a[b].append(c)
	a[c].append(b)
b = [1]
c = [1]
l = [0] * (n + 1)
l[1] = 1
while len(b) > 0:
	d = []
	for i in b:
		for j in a[i]:
			if l[j] == 0:
				d.append(j)
				c.append(j)
				l[j] = 1
	b = d[:]
c = c[::-1]
e = sorted(list(map(int, input().split())))
b = [0] * n
for i in range(n):
	b[c[i] - 1] = e[i]
print(sum(e[:-1]))
print(*b)


n = int(input())
graph = [[] for i in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
L = list(map(int, input().split()))
L.sort()
used = [0] * n
ans = [0] * n
used[0] = 1
ans[0] = L[n - 1]
next = graph[0]
cur = n - 2
while len(next) > 0:
	t = next.pop()
	ans[t] = L[cur]
	cur -= 1
	used[t] = 1
	for i in range(len(graph[t])):
		if used[graph[t][i]] != 1:
			next.append(graph[t][i])
print(sum(L) - L[n - 1])
print(' '.join(map(str, ans)))


n = int(input())
peer = [[] for _ in range(n)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	peer[a].append(b)
	peer[b].append(a)
now = [0]
scr = list(map(int, input().split()))
scr.sort()
scr.reverse()
ans = [0 for _ in range(n)]
ans[0] = scr[0]
pin = 1
while now:
	last = now
	now = []
	for x in last:
		for y in peer[x]:
			if ans[y] == 0:
				ans[y] = scr[pin]
				pin += 1
				now.append(y)
print(sum(scr[1:]))
print(' '.join(list(map(str, ans))))