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

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

Solution (Python):


from collections import deque
import itertools as ite
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

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

for i in range(N - 1):
	a, b = map(int, raw_input().split())
	E[a].append(b)
	E[b].append(a)

c = map(int, raw_input().split())
c.sort(reverse = True)
print sum(c[1:])

ans = [0] * (N + 1)
def func(pos, pre, id):
	ans[pos] = c[id]
	id += 1
	for to in E[pos]:
		if to != pre:
			id = func(to, pos, id)
	return id

func(1, -1, 0)
print " ".join(map(str, ans[1:]))

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

Solution (Python):

def input_from_console():
    n = int(input())
    a_list, b_list = [], []
    for i in range(n - 1):
        data = input()
        a, b = map(int, data.split())
        if b > a:
            a, b = b, a  
        a_list.append(a)
        b_list.append(b)
    c_list = list(map(int, input().split()))
    return n, a_list, b_list, c_list


def solve(n, a_list, b_list, c_list):
    edge = [[] for i in range(n)]  
    for i in range(len(a_list)):
        a, b = a_list[i] - 1, b_list[i] - 1  
        edge[a].append(b)
        edge[b].append(a)
    c_list.sort(reverse=True)

    vertices = [None] * n
    vertices[0] = c_list.pop(0)

    graph_value = sum(c_list)  

    search_path = []
    search_path.extend(edge[0])

    while search_path:
        node = search_path.pop(0)
        if vertices[node] is None:
            vertices[node] = c_list.pop(0)
            search_path.extend(edge[node])
    return "{:d}\n{}".format(graph_value, ' '.join(map(str, vertices)))


def main():
    n, a_list, b_list, c_list = input_from_console()
    print(solve(n, a_list, b_list, c_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  
        check_cases()
    else:
        main()

Solution (Python):
def input_from_console():
    n = int(input())
    a_list, b_list = [], []
    for i in range(n - 1):
        data = input()
        a, b = map(int, data.split())
        if b > a:
            a, b = b, a  
        a_list.append(a)
        b_list.append(b)
    c_list = list(map(int, input().split()))
    return n, a_list, b_list, c_list


def solve(n, a_list, b_list, c_list):
    edge = [[] for i in range(n)]  
    for i in range(len(a_list)):
        a, b = a_list[i] - 1, b_list[i] - 1  
        edge[a].append(b)
        edge[b].append(a)
    c_list.sort(reverse=True)

    vertices = [None] * n
    vertices[0] = c_list.pop(0)

    graph_value = sum(c_list)  

    search_path = []
    search_path.extend(edge[0])

    while search_path:
        node = search_path.pop(0)
        if vertices[node] is None:
            vertices[node] = c_list.pop(0)
            search_path.extend(edge[node])
    return "{:d}\n{}".format(graph_value, ' '.join(map(str, vertices)))


def main():
    n, a_list, b_list, c_list = input_from_console()
    print(solve(n, a_list, b_list, c_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  
        check_cases()
    else:
        main()

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

Solution (Python):
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)
checked_list = []
def dfs(num):
    checked_list.append(num)
    ans[num] = c.pop()
    for next_num in connection[num]:
        if next_num not in checked_list:
            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:])))

Solution (Python):

def input_from_console():
    n = int(input())
    a_list, b_list = [], []
    for i in range(n - 1):
        data = input()
        a, b = map(int, data.split())
        if b > a:
            a, b = b, a  
        a_list.append(a)
        b_list.append(b)
    c_list = []
    c_list = list(map(int, input().split()))
    return n, a_list, b_list, c_list


def solve(n, a_list, b_list, c_list):
    edge = [[] for i in range(n)]
    for i in range(len(a_list)):
        a, b = a_list[i] - 1, b_list[i] - 1  
        edge[a].append(b)
        edge[b].append(a)
    c_list_new = sorted(c_list, reverse=True)

    value = sum(c_list_new[1:])

    vertices = [None] * n
    vertices[0] = c_list_new.pop(0)

    search_path = []
    search_path.extend(edge[0])

    while search_path:
        node = search_path.pop(0)
        if vertices[node] is None:
            vertices[node] = c_list_new.pop(0)
            search_path.extend(edge[node])
    return str(value) + '\n' + ' '.join(map(str, vertices))


def main():
    n, a_list, b_list, c_list = input_from_console()
    print(solve(n, a_list, b_list, c_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  
        check_cases()
    else:
        main()

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

checked_list = []
def dfs(num):
    checked_list.append(num)
    ans[num] = c.pop()
    for next_num in connection[num]:
        if next_num not in checked_list:
            dfs(next_num)


l = []
for i in range(1, n+1):
    l.append([i, len(connection[i])])
l.sort(key=lambda x: x[1], reverse=True)
dfs(1)

score = 0

for a, b in ab:
    score += min(ans[a], ans[b])

print(score)
print(" ".join(map(str, ans[1:])))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())


def func(v):
    if ans[v] != -1:
        return
    ans[v] = c[index]
    global index
    index += 1
    for next_v in graph[v]:
        if v == next_v:
            continue
        func(next_v)


n = II()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = MI()
    graph[u-1].append(v-1)
    graph[v-1].append(u-1)
c = sorted(LI(), reverse=True)
ans = [-1] * n
index = 0
func(0)
print(sum(c[1::]))
for i in range(n):
    print(ans[i], end=' ')
print()

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

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0

    for i in neighbor[start]:
        
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            try:
                dfs(neighbor,i)
            except RuntimeError:
                flag = True
                return 0




m = max(node)
nn = node.index(m)

visited[nn] = 1
ans[nn] = max(c)

dfs(neigh,nn)
"""
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
ans2 = ' '.join([str(ans[i]) for i in range(N)])


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

Solution (Python):
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
 
n = int(input())
g = [[]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()))
kyo = [float("inf")] * n
def dfs(x,y,z):
  kyo[x] = y
  for i in g[x]:
    if i == z:
            continue
    dfs(i,y+1,x)
dfs(0,0,-1)
kyo2 = []
for i in range(n):
        kyo2.append([kyo[i],i])
ans = [0]*n
kyo2.sort()
kyo2 = kyo2[::-1]
c.sort()
for i in range(n):
        ans[kyo2[i][1]] = c[i]
print(sum(c)-c[-1])
print(*ans)

Solution (Python):
from collections import deque

N = int(input())

G = [[] for i 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 = sorted([int(i) for i in input().split()])

print(sum(C) - max(C))
    
Q = deque()
Q.append(N - 1)
order = []
visited = [False] * N
while len(Q) != 0:
    q = Q.popleft()
    visited[q] = True
    c = C.pop()
    order.append([q, c])
    for g in G[q]:
        if visited[g] == False:
            Q.append(g)

sorted_order = sorted(order)
ans2 = []
for i in range(N):
    ans2.append(sorted_order[i][1])
    
print(' '.join(map(str, ans2)))

Solution (Python):












n = int(input())

abn = [list(map(int,input().split())) for _ in range(n-1)]

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


links = [set() for _ in range(n)]

for abi in abn:
    a, b = abi

    a -= 1; b-=1
    links[a].add(b)
    links[b].add(a)




pv = [0]*n
ans = 0



leaves = { i for i, l in enumerate(links) if len(l) == 1 }




while leaves:
    
    index = leaves.pop()
    cmax = cn.pop()
    
    pv[index] = cmax

    if not cn: 
        break

    ans += cmax
    for ci in links[index]:
        lu = links[ci]
        lu.remove(index)
        if len(lu) == 1:
            leaves.add(ci)

print(ans)
print(*pv)

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

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

Solution (Python):





from collections import deque, _heapq

n = int(input())

g = [{"num":0,"neighber":[]} for _ in range(n+1) ]

for _ in range(n-1):

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

    g[a]["neighber"].append(b)
    g[b]["neighber"].append(a)


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


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


i = 0
s = [(0,1)]

while i < len(s):
    
    pre, cur = s[i]
    i += 1

    g[cur]["num"] = c.pop()

    for e in g[cur]["neighber"]:
        if e == pre:
            continue

        s.append( (cur,e) )

ans = ''
for i in range(1,n+1):
    ans += str( g[i]["num"] ) + " "



print( ans[:-1] )

Solution (Python):
n = int(input())
adj_path = [[] for _ in range(n)]
paths = []
for _ in range(n-1):
    a,b = map(int,input().split())
    paths.append([a,b])
    adj_path[a-1].append(b-1)
    adj_path[b-1].append(a-1)
c_list = sorted(list(map(int,input().split())),reverse=True)
out = [0 for i in range(n)]
que = [[0,adj_path[0]]]
visited = []
cnt = 0
while(que):
    node_num,children = que.pop(0)
    visited.append(node_num)
    out[node_num] = c_list[cnt]
    cnt += 1
    for child in children:
        if child not in visited:
            que.append([child,adj_path[child]])
score = 0
for path in paths:
    a,b = path
    score += min(out[a-1],out[b-1])
print(score)
print(" ".join(str(x) for x in out))

Solution (Python):
from scipy.sparse import*
n,*t=map(int,open(0).read().split())
c=sorted(t[-n:])[::-1]
f=find(c)[0]
f[csgraph.depth_first_order(csr_matrix((f[1:],(t[:-n:2],t[1:-n:2])),[n+1]*2),1,0,0)-1]=c
print(sum(c[1:]),*f)

Solution (Python):
import sys;sys.setrecursionlimit(10**6)
    
from collections import *
    
d=defaultdict(list)
    
n=int(input())
    
start=2
    
for i in range(n-1):
    
    a,b=map(int,input().split())
    
    d[a].append(b)
    
    d[b].append(a)
    
    start=min(start,a)
    
*p,=sorted(map(int,input().split()))
    
ans=[0 for i in range(n)]
    
def DFS_dict(point,TFlist):
    
    if all(TFlist):
    
        return 1
    
    for i in d[point]:
    
        if TFlist[i-1]:
    
            continue
    
        TFlist[i-1]=True
        ans[i-1]=p.pop()
    
        DFS_dict(i,TFlist)
    
        TFlist[i-1]=False
    
    return ans
    
TFlist=[False]*n
    
TFlist[start-1]=True
    
score=sum(p)-max(p)
    
ans[start-1]=p.pop()
    
ans=DFS_dict(start,TFlist)
    
print(score)
    
print(*ans)

Solution (Python):
import sys;sys.setrecursionlimit(10**6)
    
from collections import *
    
d=defaultdict(list)
    
n=int(input())
    
start=float("inf")
    
for i in range(n-1):
    
    a,b=map(int,input().split())
    
    d[a].append(b)
    
    d[b].append(a)
    
    start=min(start,a)
    
*p,=sorted(map(int,input().split()))
    
ans=[0 for i in range(n)]
    
def DFS_dict(point,TFlist):
    
    if all(TFlist):
    
        return 1
    
    for i in d[point]:
    
        if TFlist[i-1]:
    
            continue
    
        TFlist[i-1]=True
        ans[i-1]=p.pop()
    
        DFS_dict(i,TFlist)
    
        TFlist[i-1]=False
    
    return ans
    
TFlist=[False]*n
    
TFlist[start-1]=True
    
score=sum(p)-max(p)
    
ans[start-1]=p.pop()
    
ans=DFS_dict(start,TFlist)
    
print(score)
    
print(*ans)

Solution (Python):
N = int(input())
edges = [list(map(int, input().split())) for i in range(N-1)]
c = list(map(int, input().split()))
c.sort(reverse=True)
_c = c[::]

conn = [[] for i in range(N)]
for edge in edges:
    a = edge[0]-1
    b = edge[1]-1
    conn[a].append(b)
    conn[b].append(a)
ans = [0 for i in range(N)]
stack = []
stack.append(0)
checked = set()
while len(stack) > 0:
    current = stack.pop(0)
    checked.add(current)
    ans[current] = c[0]
    c.pop(0)
    for next in conn[current]:
        if next not in checked:
            stack.append(next)

print(sum(_c[1:]))
ans_str = ""
for i in range(N):
    ans_str += str(ans[i])
    if i < N-1:
        ans_str += " "
print(ans_str)

Solution (Python):
from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

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((1,b))
    e[b].append((1,a))

c = list(map(int,input().split()))
c.sort()
print(sum(c)-c[-1])
d = dijkstra(e,N,0)
d = [(d[i],i) for i in range(N)]
d.sort()
d = [(d[i][0],d[i][1],c[-i-1]) for i in range(N)]
d.sort(key=lambda x:x[1])
ans = [str(d[i][2]) for i in range(N)]
print(' '.join(ans))

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

Solution (Python):
def d_maximum_sum_of_minimum(N, Nodes, C):
    
    import sys
    sys.setrecursionlimit(10**6)

    int_list = list(sorted(C))
    graph = [[] for _ in range(N)]
    for u, v in Nodes:  
        graph[u - 1].append(v - 1)
        graph[v - 1].append(u - 1)

    def traverse_tree(parent, current, ret=[0] * N):
        """各頂点にCの値が大きなもの順に書き込んでいく"""
        def dfs(p, c):
            ret[c] = int_list.pop()
            for next_edge in graph[c]:
                if next_edge != p:  
                    dfs(c, next_edge)
        dfs(parent, current)
        return ret
    tmp = traverse_tree(-1, 0)
    return str(sum(tmp[1:])) + '\n' + ' '.join(map(str, tmp))

N = int(input())
Nodes = [[int(i) for i in input().split()] for j in range(N - 1)]
C = [int(i) for i in input().split()]
print(d_maximum_sum_of_minimum(N, Nodes, C))

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

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

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

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

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


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

print(M)
print(*use)

Solution (Python):






















from collections import deque

N = int(input())

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

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

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


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

print(M)
print(*use)

Solution (Python):
from scipy.sparse import*
n,*t=map(int,open(0).read().split())
c=sorted(t[-n:])
f=c[:]
for i in csgraph.depth_first_order(csr_matrix((f[1:],(t[:-n:2],t[1:-n:2])),[n+1]*2),1,0,0):n-=1;f[i-1]=c[n]
print(sum(c[:-1]),*f)

Solution (Python):
import sys;sys.setrecursionlimit(10**6)
from collections import*
n=int(input())
d=defaultdict(list)

start=float("inf")
for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
    start=min(a,start)
p=sorted(map(int,input().split()))

def DFS(point,TFlist):
    global ans
    global score
    if all(TFlist):
        return 1
    for i in d[point]:
        if TFlist[i-1]:
            continue
        TFlist[i-1]=True
        tmp=p.pop()
        ans[i-1]=tmp
        score.append(tmp)
        
        DFS(i,TFlist)
        TFlist[i-1]=False
    return score,ans

TFlist=[False]*(n)
TFlist[start-1]=True
ans=[0 for i in range(n)]
score=[]
ans[start-1]=p.pop()
s,t=DFS(start,TFlist)

print(sum(s))
print(*t)

Solution (Python):
import numpy as np 
N = int(input())



linked = [[] for i in range(N)]
pairs = []

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

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




links = np.array([0 for i in range(N)])

for i in range(N):
    links[i] = len(linked[i])


nodeval = np.array([0 for i in range(N)])

stack = [1]

visited = [False for i in range(N)]

while(len(stack)>0):
    minag = stack.pop()
    nodeval[minag] = Cs.pop(0)
    for l in linked[minag]:
        if not visited[l]:
            stack.append(l)
    visited[minag] = True
    

sumval=0
for p in pairs:
    sumval += min(nodeval[p[0]-1], nodeval[p[1]-1] )

print(sumval)
for i,l in enumerate(nodeval):
    print(l,end=" " if i!=N-1 else "\n")

Solution (Python):
from scipy.sparse import*
n,*t=map(int,open(0).read().split())
c=sorted(t[-n:])
i=n
for j in csgraph.depth_first_order(csr_matrix((t[:n-1],(t[:-n:2],t[1:-n:2])),[n+1]*2),1,0,0):i-=1;t[j-1]=c[i]
print(sum(c[:-1]),*t[:n])

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

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

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

c.sort(reverse = True)
edge = [[] for _ in range(N)]
for a, b in ab:
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v, p):
    global ans
    global count
    if p != -1:
        anse[v] = c[count+1]
        ans += min(anse[v], anse[p])
        count += 1
    for nv in edge[v]:
        if nv == p:
            continue
        dfs(nv, v)


search = [0]
res = 0
rese = [None for _ in range(N)]
for i in search:
    count = 0
    ans = 0
    anse = [None for _ in range(N)]
    anse[i] = c[0]
    dfs(i, -1)
    if res < ans:
        res = ans
        rese = anse
print(res)
print(" ".join(map(str, rese)))

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

Solution (Python):
from scipy.sparse import*
n,*t=map(int,open(0).read().split())
c=sorted(t[-n:])
f=[1]*n
for i in csgraph.depth_first_order(csr_matrix((f[1:],(t[:-n:2],t[1:-n:2])),[n+1]*2),1,0,0):n-=1;f[i-1]=c[n]
print(sum(c[:-1]),*f)

Solution (Python):
from collections import defaultdict
from sys import setrecursionlimit, getrecursionlimit

setrecursionlimit(100*getrecursionlimit())

N = int(input())
g = defaultdict(list)
K = []
for i in range(N-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
    K.append((a,b))

C = sorted([int(i) for i in input().split()], reverse=True)

a = {i:0 for i in range(1, N+1)}

visited = defaultdict(bool)
ct = 0
def dfs(v):
    global ct
    visited[v] = True
    a[v] = C[ct]
    ct += 1
    for c in g[v]:
        if not visited[c]:
            dfs(c)

dfs(1)

ans1 = 0
ans2 = ' '.join([str(b) for b in a.values()])
for b, c in K:
    ans1 += min(a[b], a[c])

print(ans1)
print(ans2)

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

Solution (Python):
from scipy.sparse import*
n,*t=map(int,open(0).read().split())
c=sorted(t[-n:])
f=[0]*n
for i in csgraph.depth_first_order(csr_matrix(([1]*~-n,(t[:-n:2],t[1:-n:2])),[n+1]*2),1,0,0):n-=1;f[i-1]=c[n]
print(sum(c[:-1]),*f)

Solution (Python):
from scipy.sparse import*
n,*t=map(int,open(0).read().split())
c=sorted(t[-n:])
f=[0]*n
for i in csgraph.depth_first_order(csr_matrix(([1]*~-n,(t[:-n:2],t[1:-n:2])),[n+1]*2),1,0)[0]:n-=1;f[i-1]=c[n]
print(sum(c[:-1]),*f)

Solution (Python):
from collections import deque



N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    
    G[u-1].append((v-1))
    G[v-1].append((u-1))
cs = sorted(list(map(int,input().split())),reverse=True)
gs = [len(g) for g in G]
K = gs.index(min(gs))

ds = [-1]*N
used = [False] * N
ans = 0


q = deque([K])
ds[K] = cs[0]
i = 1
while len(q) > 0:
    a = q.popleft()
    Vs = G[a]
    for u in Vs:
        if ds[u] == -1:
            q.append(u)
            ds[u] = cs[i]
            used[u] = True
            i += 1
ansd = ""
for d in ds:
    ansd += str(d)+" "
print(sum(cs)-max(cs))
print(ansd)

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

Solution (Python):
from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

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

c = sorted(list(map(int,input().split())))
vcost = [-1]*(N+1)
vcost[1]=c.pop()
ans = 0
def dfs(i):
    global ans
    for j in D[i]:
        if vcost[j]==-1:
            vcost[j]=c.pop()
            ans += vcost[j]
            dfs(j)
dfs(1)
print(ans)
print(*vcost[1:])

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

Solution (Python):
from collections import deque

n = int(input())
graph = {}
for i in range(1, n):
    a, b = map(int,input().split())
    try:
        if graph[a] is not None:
            graph[a].append(b)
    except:
        graph[a] = [b]
    try:
        if graph[b] is not None:
            graph[b].append(a)
    except:
        graph[b] = [a]
c = list(map(int, input().split()))
c.sort()
M = sum(c) - c[-1]
q = deque([1])
a = [0 for i in range(n)]
visited = []
while q:
    for x in list(q):
        visited.append(x)
        for y in graph[x]:
            if not y in visited:
                q.append(y)
        a[x-1] = str(c.pop())
        q.popleft()
print(M)
print(' '.join(a))

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