N=int(eval(input()))

from collections import defaultdict,deque

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

branch=defaultdict(set)

for a,b in B:

    branch[a-1]|={b-1}

    branch[b-1]|={a-1}

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

cnt=[len(branch[i]) for i in range(N)]

M=0

start=-1

for i in range(N):

    if M<len(branch[i]):

        M=len(branch[i])

        start=i

C.sort(reverse=True)

idx=0

ans=[0]*N

check=deque([start])

while len(check)>0:

    now=check.popleft()

    ans[now]=C[idx]

    idx+=1

    nex=[(i,len(branch[i])) for i in branch[now] if ans[i]==0]

    nex.sort(key=lambda x:x[1],reverse=True)

    check+=deque([i[0] for i in nex])

res=0

for a,b in B:

    res+=min(ans[a-1],ans[b-1])

print(res)

print((" ".join(list(map(str,ans)))))
N=int(eval(input()))

from collections import defaultdict

branch=defaultdict(set)

for i in range(N-1):

    a,b=list(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])))
N = int(eval(input()))
from collections import defaultdict, deque

B = [tuple(map(int, input().split())) for i in range(N - 1)]
branch = defaultdict(set)
for a, b in B:
    branch[a - 1] |= {b - 1}
    branch[b - 1] |= {a - 1}
C = list(map(int, input().split()))
cnt = [len(branch[i]) for i in range(N)]
M = 0
start = -1
for i in range(N):
    if M < len(branch[i]):
        M = len(branch[i])
        start = i
C.sort(reverse=True)
idx = 0
ans = [0] * N
check = deque([start])
while len(check) > 0:
    now = check.popleft()
    ans[now] = C[idx]
    idx += 1
    nex = [(i, len(branch[i])) for i in branch[now] if ans[i] == 0]
    nex.sort(key=lambda x: x[1], reverse=True)
    check += deque([i[0] for i in nex])
res = 0
for a, b in B:
    res += min(ans[a - 1], ans[b - 1])
print(res)
print((" ".join(list(map(str, ans)))))

N = int(eval(input()))
from collections import defaultdict

branch = defaultdict(set)
for i in range(N - 1):
    a, b = list(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 defaultdict, deque +from collections import defaultdict -B = [tuple(map(int, input().split())) for i in range(N - 1)] -for a, b in B: -    branch[a - 1] |= {b - 1} -    branch[b - 1] |= {a - 1} +for i in range(N - 1): +    a, b = list(map(int, input().split())) +    a -= 1 +    b -= 1 +    branch[a] |= {b} +    branch[b] |= {a} -cnt = [len(branch[i]) for i in range(N)] -M = 0 -start = -1 -for i in range(N): -    if M < len(branch[i]): -        M = len(branch[i]) -        start = i -C.sort(reverse=True) -idx = 0 +C.sort() -check = deque([start]) +used = {0} +check = {0} +M = sum(C[:-1]) -    now = check.popleft() -    ans[now] = C[idx] -    idx += 1 -    nex = [(i, len(branch[i])) for i in branch[now] if ans[i] == 0] -    nex.sort(key=lambda x: x[1], reverse=True) -    check += deque([i[0] for i in nex]) -res = 0 -for a, b in B: -    res += min(ans[a - 1], ans[b - 1]) -print(res) -print((" ".join(list(map(str, ans))))) +    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])))