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

Solution (Python):
import 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)

Solution (Python):
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)

Solution (Python):
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)
c=list(map(int,input().split()))
c.sort()
c.reverse()

def bfs(v):
  ans=[-1]*n
  ans[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i]]==-1:
        ct+=1
        ans[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return ans

ans=bfs(0)
print(sum(c)-c[0])
for i in range(n):
  ans[i]=str(c[ans[i]])
print(' '.join(ans))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
from collections import deque

N = int(input())
dic = {}
lnum = [0] * N
q = deque([])
alis = [0] * N


for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    lnum[a] += 1
    lnum[b] += 1

    if a not in dic:
        dic[a] = []

    if b not in dic:
        dic[b] = []

    dic[a].append(b)
    dic[b].append(a)

for i in range(N):

    if lnum[i] == 1:
        q.append(i)

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

for i in range(N):

    now = q.popleft()
    lnum[now] = 0

    alis[now] = c[i]
    

    for nex in dic[now]:

        lnum[nex] -= 1
        if lnum[nex] == 1:
            q.append(nex)

print (sum(c) - c[-1])
print (" ".join(map(str,alis)))

Solution (Python):



def main():
    from collections import deque

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

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

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

    
    print(sum(c[1:]))

    
    visited = [False for _ in range(n)]
    visited[0] = True
    d = deque()
    d.append(0)
    ans = [0 for _ in range(n)]
    ans[0] = c[0]
    count = 1

    while d:
        di = d.popleft()

        for dii in graph[di]:
            if not visited[dii]:
                ans[dii] = c[count]
                count += 1
                visited[dii] = True
                d.append(dii)

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n+1)]
    for i in range(len(s)):
        pt[s[i]].append(t[i])
        if directed==False:
            pt[t[i]].append(s[i])
    return pt

N = I()
a,b = Line(N-1,2)
c = III()

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

c.sort()
M = sum(c[:-1])

pt = edges_to_pt(a,b,N)

used = [False]*(N+1)
ans = [0]*(N+1)
used[1] = True
ans[1] = c.pop()
q = [1]
while q:
    q1 = []
    for i in q:
        for j in pt[i]:
            if used[j]==False:
                used[j] = True
                ans[j] = c.pop()
                q1.append(j)
    q = q1

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

Solution (Python):
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)

Solution (Python):

def bfs(start: int) -> None:
    q = [start]
    nodes[start] = C.pop()
    while q:
        v = q.pop(0)
        for u in T[v]:
            if not nodes[u]:
                nodes[u] = C.pop()
                q.append(u)


def main():
    
    global T, C, nodes
    N, *ABC = map(int, open(0).read().split())
    AB, C = ABC[:-N], ABC[-N:]
    C.sort()
    T = [[] for _ in range(N + 1)]
    for v, u in zip(*[iter(AB)] * 2):
        T[v].append(u), T[u].append(v)
    score, nodes = sum(C) - C[-1], [0] * (N + 1)  
    for i, t in enumerate(T[1:], 1):
        if len(t) == 1:
            start = i  
            break
    bfs(start)
    print(score)
    print(*nodes[1:])


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
c=list(map(int,input().split()))
c.sort()
connection=[[] for i in range(n)]
ans=[0 for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)
next=[0]
next=deque(next)
check=[-1 for i in range(n)]
check[0]=1
ct=n
while ct>0:
  ct-=1
  x=next.popleft()
  ans[x]=str(c[ct])
  for i in range(len(connection[x])):
    if check[connection[x][i]]==-1:
      next.append(connection[x][i])
      check[connection[x][i]]=1
print(sum(c)-c[n-1])
print(' '.join(ans))

Solution (Python):

def bfs(start: int) -> None:
    q = [start]
    nodes[start] = C.pop()
    while q:
        v = q.pop(0)
        for u in T[v]:
            if not nodes[u]:
                nodes[u] = C.pop()
                q.append(u)


def main():
    global T, C, nodes
    N, *ABC = map(int, open(0).read().split())
    AB, C = ABC[:-N], ABC[-N:]
    C.sort()
    T = [[] for _ in range(N + 1)]
    for v, u in zip(*[iter(AB)] * 2):
        T[v].append(u), T[u].append(v)
    score, nodes = sum(C) - C[-1], [0] * (N + 1)  
    for i, t in enumerate(T[1:], 1):
        if len(t) == 1:
            start = i
            break
    bfs(start)
    print(score)
    print(" ".join(map(str, nodes[1:])))


if __name__ == "__main__":
    main()

Solution (Python):
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:])

Solution (Python):
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)

q = [0]
checked = [False]*N
checked[0] = True
ans = 0
c = 0
score = [None for _ in range(N)]
score[0] = C[c]

while q:
    qq = []
    for p in q:
        for np in graph[p]:
            if not checked[np]:
                qq.append(np)
                checked[np] = True
                c += 1
                score[np] = C[c]
                ans += min(score[np], score[p])
    q = qq

print(ans)
for s in score:
    print(s, end=' ')
print()

Solution (Python):
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)

Solution (Python):
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)))

Solution (Python):
import collections
import sys
input = sys.stdin.readline
import heapq
def solve():
  n = int(input())

  query2 = []
  edge = [[] for _ in range(n)]
  ans = [ 0 for i in range(n)]
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query2.append(a)
    query2.append(b)
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
  c = list(int(i) for i in input().split())
  if n == 1:
    print(0)
    print(c[0])
    exit()
  c = collections.deque(sorted(c,reverse =True))
  d = collections.Counter(query2)
  d2 = d.most_common()
  bfs = []
  heapq.heappush(bfs,(-1*d2[0][1],d2[0][0]-1))
  ct = 0
  visit = [False]*n
  
  while bfs:
    times,place = heapq.heappop(bfs)
    if visit[place]:
      continue
    else:
      visit[place] = True

      for i in range(len(edge[place])):
        newp = edge[place][i]
        newtimes = len(edge[newp])
        if not visit[newp]:
          heapq.heappush(bfs,(-1*newtimes,newp))
      
      ans[place] = c.popleft()

      

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

Solution (Python):
import collections
import sys
input = sys.stdin.readline
import heapq
from array import array
def solve():
  n = int(input())

  query2 = collections.deque([])
  edge = [[] for _ in range(n)]
  ans = array('I', [ 0 for i in range(n)])
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query2.append(a)
    query2.append(b)
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
  c = list(int(i) for i in input().split())
  if n == 1:
    print(1)
    print(c[0])
    exit()
  c = collections.deque(sorted(c,reverse =True))
  d = collections.Counter(query2)
  d2 = d.most_common()
  bfs = []
  heapq.heappush(bfs,(-1*d2[0][1],d2[0][0]-1,-1))
  ct = 0
  visit = [False]*n
  while bfs:
    times,place,parent = heapq.heappop(bfs)
    if visit[place]:
      continue
    else:
      visit[place] = True

      for i in range(len(edge[place])):
        newp = edge[place][i]
        newtimes = len(edge[newp])
        if not visit[newp]:
          heapq.heappush(bfs,(-1*newtimes,newp,place))
      
      ans[place] = c.popleft()

      

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

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
cnt = [0]*n
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    cnt[a-1] += 1
    cnt[b-1] += 1
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
c = LI()
m = sum(c) - max(c)
print(m)
d = [0]*n
for i in range(n):
    if cnt[i] == 1:
        d[i] = max(c)
        break
c.sort(reverse = True)
c = c[1:]
que = deque(c)
def dfs(x,p):
    for v in graph[x]:
        if v != p:
            if d[v] == 0:
                d[v] = que.popleft()
                dfs(v,x)
dfs(i,-1)
print(*d)

Solution (Python):
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)

Solution (Python):
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]))

Solution (Python):

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

Solution (Python):
N = int(input())
e_list = [[] for i in range(N)]
for i in range(N-1):
        a,b = list(map(int,input().split()))
        a,b = a-1,b-1
        e_list[a].append(b)
        e_list[b].append(a)
c = list(map(int,input().split()))

vi = 0 
from collections import deque
Q = deque([vi])
checked_list = [False for i in range(N)]
checked_list[vi]=True
min_path_list = [10**27 for i in range(N)] 
min_path_list[vi] = 0
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.appendleft(v1)
            min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) 


min_i_list = [[i,min_path_list[i]] for i in range(N)]
min_i_list.sort(key=lambda x:x[1],reverse=True)

c.sort()

ans = [[min_i_list[i][0]+1, c[i]] for i in range(N)]

ans.sort(key=lambda x:x[0])
ans = [ans[i][1] for i in range(N)]
print(sum(c[:-1]))
print(*ans)

Solution (Python):
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)))

Solution (Python):

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

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]
def mi(n): return [wi() for _ in range(n)]
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n = i()
ab = mip(n - 1)
c = wi()
c.sort(reverse=True)

connect = [[] for _ in range(n)]

for x, y in ab:
    connect[x].append(y)
    connect[y].append(x)

flagli = [0] * n
ansli = [0] * n

queue = deque()
queue.append(0)
cnt = 0
while queue != deque():
    kk = queue.popleft()
    flagli[kk] = 1

    ansli[kk] = c[cnt]
    cnt += 1

    for root in connect[kk]:
        if flagli[root] == 0:
            queue.append(root)

sumans = sum(c) - max(c)
print(sumans)
print(*ansli)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
from collections import deque

class Node:
    def __init__(self):
        self.val = -1
        self.link = []

def main():
    N = int(input())
    nodes = [Node() for i in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1; b -= 1;
        nodes[a].link.append(nodes[b])
        nodes[b].link.append(nodes[a])
    c = list(map(int, input().split()))
    c = sorted(c, reverse=True)
    count = 0
    q = deque()
    q.append(nodes[0])
    while len(q) > 0:
        node = q.popleft()
        node.val = c[count]
        count += 1
        for next in node.link:
            if next.val == -1:
                q.append(next)
    print(sum(c) - c[0])
    for i in range(N):
        print(nodes[i].val, end="")
        if i != N-1:
            print(" ",end="")
        else:
            print()

if __name__ == "__main__":
    main()

Solution (Python):
import heapq

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


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

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


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


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



node = [-1]*N


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


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

Solution (Python):
import 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)

Solution (Python):
import collections, heapq, sys

n = int(sys.stdin.readline().rstrip())
g = collections.defaultdict(list)
visited = set()
deg = collections.defaultdict(int)
for i in range(n-1):
    a, b = map(int, sys.stdin.readline().rstrip().split(' '))
    deg[a] += 1
    deg[b] += 1
    g[a].append(b)
    g[b].append(a)

pq = []
for i in range(1, n+1):
    heapq.heappush(pq, [deg[i], i])
wts = map(int, sys.stdin.readline().rstrip().split(' '))
wts.sort(reverse=True)
    
vToWt = [-1 for _ in range(n+1)]
sm = 0
while len(pq):
    _, v = heapq.heappop(pq)
    
    if vToWt[v] != -1:
        continue
    vToWt[v] = wts.pop()
    for nei in g[v]:
        if vToWt[nei] != -1:
            continue
        sm += vToWt[v]
        deg[nei] -= 1
        heapq.heappush(pq, [deg[nei], nei])

print(sm)
print(' '.join(map(str, [x for x in vToWt[1:]])))

Solution (Python):
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)

Solution (Python):
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]))

Solution (Python):
from collections import deque
N = int(input())
G = [[] for i in range(N)]
D = [0]*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)
    D[a-1] += 1
    D[b-1] += 1
*C, = map(int, input().split())
C.sort()

U = [1]*N
que = deque()
for i in range(N):
    if D[i] <= 1:
        que.append(i)
        U[i] = 0
it = iter(C).__next__
ans = [0]*N
R = 0
while que:
    v = que.popleft()
    ans[v] = r = it()
    R += r
    for w in G[v]:
        if U[w] == 0:
            continue
        D[w] -= 1
        if D[w] <= 1:
            U[w] = 0
            que.append(w)
print(R - C[-1])
print(*ans)

Solution (Python):
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)))

Solution (Python):
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)))

Solution (Python):







import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

from itertools import combinations, permutations 
from math import factorial
def combinations_count(n, r):
    
    
    
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter 
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
from copy import deepcopy, copy 
from functools import reduce
from fractions import gcd 
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

    
    
    
    
    
    
    
    
    






R = lambda: list(map(int, input().split()))
input2 = sys.stdin.readline
R2 = lambda: list(map(int, input2().split()))

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


dic = {}
l = deque()
for a, b in ab:
    dic.setdefault(a, []).append(b)
    dic.setdefault(b, []).append(a)

m = sum(c) - max(c)
d = [-1] * n
l.extend(dic[1])
d[0] = c[0]
i = 1
while l:
    deq = l.popleft()
    if d[deq-1] >= 0:
        pass
    else:
        if deq in dic:
            l.extend(dic[deq])
        d[deq-1] = c[i]
        i += 1
print(m)
print(*d)

Solution (Python):







import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

from itertools import combinations, permutations 
from math import factorial
def combinations_count(n, r):
    
    
    
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter 
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
from copy import deepcopy, copy 
from functools import reduce
from fractions import gcd 
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

    
    
    
    
    
    
    
    
    






R = lambda: list(map(int, input().split()))
n = int(input())
ab = [R() for i in range(n-1)]
c = R()
c.sort(reverse=True)


dic = {}
l = deque()
for a, b in ab:
    dic.setdefault(a, []).append(b)
    dic.setdefault(b, []).append(a)

m = sum(c) - max(c)
d = [-1] * n
l.extend(dic[1])
d[0] = c[0]
i = 1
while l:
    deq = l.popleft()
    if d[deq-1] >= 0:
        pass
    else:
        if deq in dic:
            l.extend(dic[deq])
        d[deq-1] = c[i]
        i += 1
print(m)
print(*d)