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 random
import sys
sys.setrecursionlimit(10**5 + 10)


def main():
    n = input()
    edges = []
    nodes = [0] * n
    children = {i: [] for i in xrange(n)}
    for _ in xrange(n - 1):
        a, b = map(int, raw_input().split())
        a -= 1
        b -= 1
        edges.append([a, b])
        nodes[a] += 1
        nodes[b] += 1
        children[a].append(b)
        children[b].append(a)

    cc = map(int, raw_input().split())
    cc.sort(reverse=True)
    ans = [0] * n

    def dfs(node, visited):
        for nex in children[node]:
            if nex in visited:
                continue
            visited.add(nex)
            dfs(nex, visited)
        ans[node] = cc.pop()

    while True:
        start = random.randrange(n)
        if len(children[start]) > 1:
            break
    dfs(start, {start})

    score = 0
    for a, b in edges:
        score += min(ans[a], ans[b])
    print score
    print ' '.join(map(str, ans))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
N = int(input())
num_edges = N-1
edges = [list(map(int, input().split())) for i in range(num_edges)]

adj = [[] for i in range(N+1)]
for ed in edges:
    adj[ed[0]] += [[ed[1]] ]
    adj[ed[1]] += [[ed[0]] ]
c_list = list(map(int, input().split()))
c_list = sorted(c_list)
d_list = [-1 for i in range(N+1)]

def recfun(vi, ind, M):
    d_list[vi] = 0 
    for ed in adj[vi]: 
        if d_list[ed[0]] == -1: 
            ind, M = recfun(ed[0], ind, M) 
    d_list[vi] = c_list[ind] 
    M += c_list[ind]
    ind += 1
    return  ind, M
        
_, M  = recfun(1, 0, 0)
print(M-c_list[-1])
print(" ".join(map(str, d_list[1:])))

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

Solution (Python):
n=int(input())
edge=[]
for i in range(n-1):
    a,b=map(int,input().split())
    edge.append([a,b])
c=list(map(int,input().split()))
c.sort(reverse=True)
node=[0]*n
weight=[-1]*n
edges=[[] for _ in range(n)]
for a,b in edge:
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    node[a-1]=node[a-1]+1
    node[b-1]=node[b-1]+1
s=node.index(max(node))


stack=[]
stack.append(s)
weight[s]=c.pop(0)
while stack:
    
    buf=stack.pop(-1)
    for e in edges[buf]:
        if weight[e]==-1:
            weight[e]=c.pop(0)
            stack.append(e)
w=0
for a,b in edge:
    if(weight[a-1]>weight[b-1]):
        w+=weight[b-1]
    else:
        w+=weight[a-1]
print(w)
for i in range(n):
    print(weight[i])

Solution (Python):

import sys
sys.setrecursionlimit(100000+10)


def add_edge(u, v):
	G[u].append(v)
	G[v].append(u)

def dfs(vertex):
	global values
	global now_index

	values[vertex] = values_to_give[now_index]
	now_index -= 1

	for info in G[vertex]:
		v = info
		if values[v] >= 0: 
			
			pass
		else:
			dfs(v)

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

G = [[] for _ in range(n)] 
for edge in edges:
	add_edge(edge[0]-1, edge[1]-1)

values = [-1] * n

now_index = n-1

dfs(0)

mmm = list(map(str, values))
print(sum(values_to_give) - max(values_to_give))
print(" ".join(mmm))

Solution (Python):
import collections
N = int(input())
tree = [[] for i in range(N+1)]
hen = []
tyouten = [0 for i in range(N+1)]
zisuu = []
for i in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
    hen.append([a,b])
c = list(map(int, input().split()))
c.sort(reverse = True)

for i in range(1,N+1):
    zisuu.append([len(tree[i]),i])

zisuu.sort(reverse = True)

queue = collections.deque()
queue.append(zisuu[0][1])
count = 1
tyouten[zisuu[0][1]] = c[0]
while len(queue) > 0:
    now = queue.popleft()
    for next in tree[now]:
        if tyouten[next] == 0:
            tyouten[next] = c[count]
            count += 1
            queue.append(next)



ans = 0
for i in range(N-1):
    ans += min(tyouten[hen[i][0]], tyouten[hen[i][1]])

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

Solution (Python):
import sys

sys.setrecursionlimit(100000)

n = int(input())
edgeList0 = [list(map(int, input().split())) for i in range(n-1)]
cList = list(map(int,input().split()))
cList.sort(reverse=True)
print(sum(cList[1:]))
edgeList = []
for _ in range(n):
  edgeList.append([])
for i in edgeList0:
  edgeList[i[0]-1].append(i[1]-1)
  edgeList[i[1]-1].append(i[0]-1)

def edgefunc(j):
  numList.append((j,cList.pop(0)))
  if len(edgeList[j]) != 0:
    for k in edgeList[j]:
      edgeList[k].remove(j)
      edgefunc(k)

numList = []
edgefunc(0)
numList.sort()
answer2 = ""
for l in numList:
  answer2 += str(l[1]) + " "
print(answer2[:-1])

Solution (Python):
import heapq
from collections import defaultdict

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()


N = n()
M = 0
ds = [None] * N

edges = defaultdict(set)
ranks = [0] * N
for i in range(N-1):
    a, b = nl()
    edges[a-1].add(b-1)
    edges[b-1].add(a-1)
    ranks[a-1] += 1
    ranks[b-1] += 1
cs = sorted(nl())
M = sum(cs[:-1])

h = []
for i in range(N):
    heapq.heappush(h, (ranks[i], i))

for i in range(N):
    rank, node = heapq.heappop(h)
    ds[node] = cs[i]
    for next_node in edges[node]:
        ranks[next_node] -= 1
        heapq.heappush(h, (ranks[next_node], next_node))
        edges[next_node].remove(node)

print(M)
print(' '.join([str(d) for d in ds]))

Solution (Python):

N=int(input())
road_list = [[] for i in range(N)]

for i in range(N-1):
    a,b=list(map(int,input().split()))
    a=a-1
    b=b-1
    road_list[a].append(b)
    road_list[b].append(a)
c = list(map(int,input().split()))
from collections import deque
Q = deque([[0,0]])
ans = []
checked_list = [False for i in range(N)]
checked_list[0]=True
count_list = [10**9 for i in range(N)]
count_list[0] = 0

while len(Q)>0:
    v,count = Q.pop()
    count+=1
    for v1 in road_list[v]:        
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.append([v1,count])
            count_list[v1]=count

c.sort()

count_list = [[i,count_list[i]] for i in range(N)]
count_list = sorted(count_list, key=lambda x:x[1],reverse=True)
d = [[count_list[i][0],c[i]] for i in range(N)]
d = sorted(d, key=lambda x:x[0])
d = [d[i][1] for i in range(N)]
print(sum(c[:-1]))
print(*d)

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

E = [[] for i in range(N + 1)]
ans = {}
First = 0
edges = 0
q = []
visited = [False] * (N + 1)


for i in range(N - 1):
    A, B = map(int, input().split())
    E[A].append(B)
    E[B].append(A)
    if len(E[A]) > edges:
        First = A
        edges = len(E[A])

    if len(E[B]) > edges:
        First = B
        edges = len(E[B])

C = list(map(int, input().split()))
C.sort()
max = sum(C) - C[-1]
q.append(First)

for i in range(1, N + 1):
    x = q.pop(0)
    visited[x] = True
    ans[x] = C[-i]
    for xx in E[x]:
        if not visited[xx]:
            q.append(xx)

print(max)

s = ""
for i in range(1, N + 1):
    s += str(ans[i])
    if i != N:
        s += " "

print(s)

Solution (Python):
from collections import defaultdict, deque

n = int(input())

nodes = defaultdict(list)
edges = []
edge_count = defaultdict(int)
node = defaultdict(int)
node_num = defaultdict(int)

for _ in range(n - 1):
    a, b = map(int, input().split())
    nodes[a].append(b)
    nodes[b].append(a)
    edges.append((a, b))
    edge_count[a] += 1
    edge_count[b] += 1

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

q = deque()
q.append(1)
node[1] = 0

while q:
    current = q.popleft()
    depth = node[current]

    for next in nodes[current]:
        if next not in node:
            node[next] = depth + 1
            q.append(next)


depth_list = sorted(node.items(), key=lambda x:x[1])

for i, e in enumerate(depth_list):
    node_num[e[0]] = c[i]

ans = 0
for edge in edges:
    ans += min(node_num[edge[0]], node_num[edge[1]])

print(ans)

position = []

for i in range(n):
    position.append(node_num[i + 1])

print(*position, sep=" ")

Solution (Python):
from collections import defaultdict


N = int(input())

ab = []

for _ in range(N - 1):
    ab.append(tuple(map(int, input().split())))

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


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


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

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

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))
def oon(x,n,nn):
	global c,ppp
	for i in range(len(x[n])):
		if x[n][i] != nn:
			kk[x[n][i]] = c[ppp]
			ppp += 1
			oon(x,x[n][i],n)

q = int(input())

k = [0 for i in range(q)]
kk = [0 for i in range(q)]
aa = [[]for i in range(q)]
for i in range(q-1):
	a,b  = m()
	k[a-1] += 1
	k[b-1] += 1
	aa[a-1].append(b-1)
	aa[b-1].append(a-1)
k.sort(reverse = True)
c = l()
c.sort(reverse = True)
kk[0] = c[0]
ppp = 1
oon(aa,0,0)
su = sum(c[1:])

print(su)
for i in range(q-1):
	print(kk[i],end = " ")
print(kk[-1])

Solution (Python):
import sys, math, collections, heapq, itertools
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    file = sys.stdin.readline 
    INF = 10 ** 25
    mod = 7 + 10 ** 9

    N = int(file())
    edge = [[] for i in range(N)]
    for i in range(N-1):
        a, b = map(int, file().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    c = [int(i) for i in file().split()]
    c.sort(reverse = True)

    que = collections.deque()
    last = 0
    forward = [-1] * N
    que.append((0, 0))
    while que:
        now, dist = que.popleft()
        if forward[now] == -1:
            forward[now] = dist
            last = now
            for e in edge[now]:
                if forward[e] == -1: que.append((e, dist + 1))
    backward = [-1] * N
    que.append(last)
    count = 0
    while que:
        now = que.popleft()
        if backward[now] == -1:
            backward[now] = c[count]
            count += 1
            last = now
            for e in edge[now]:
                if backward[e] == -1: que.append(e)

    total = 0
    que.append((last, backward[last]))
    visited = [False] * N
    while que:
        now, weight = que.popleft()
        if visited[now] == False:
            visited[now] = True
            for e in edge[now]:
                if visited[e] == False:
                    total += min(weight, backward[e])
                    que.append((e, backward[e]))

    print(total)
    print(" ".join(map(str, backward)))

    return 0
  
if __name__ == "__main__":
    solve()

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

Solution (Python):



import queue

def readInt():
    return int(input())

def readList():
    return list(input().split())

def readListI():
    return list(map(int, input().split()))

def main():
    n = readInt()
    edges = {}
    edges2 = []
    links = {}
    leaf = queue.Queue()
    for _ in range(n-1):
        a, b = readListI()
        a -= 1
        b -= 1
        edges.setdefault(a, set())
        edges.setdefault(b, set())
        edges[a].add(b)
        edges[b].add(a)
        links.setdefault(a, 0)
        links.setdefault(b, 0)
        links[a] += 1
        links[b] += 1
        edges2.append((a, b))
    for e, l in links.items():
        if l == 1:
            leaf.put(e)
    lc = sorted(readListI())
    ret = {}
    for c in lc:
        e = leaf.get()
        ret[e] = c
        for e2 in edges[e]:
            if e2 in links:
                links[e2] -= 1
                if links[e2] == 1:
                    leaf.put(e2)
    ans = 0
    for a, b in edges2:
        ans += min(ret[a], ret[b])
    print(ans)
    print(" ".join(map(str, [v for e, v in sorted(ret.items())])))


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import deque

N=input()

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

for _ in range(N-1):
	a,b=map(int, sys.stdin.readline().split())
	nl[a].append(b)
	nl[b].append(a)


C=map(int, sys.stdin.readline().split())
C.sort(reverse=True)
C=deque(C)


start=None
max_nl_cnt=0
for i in range(1,N+1):
	nl_cnt=len( nl[i] )
	if max_nl_cnt < nl_cnt:
		start=i
		max_nl_cnt=nl_cnt

Visit=[ None for i in range(N+1) ] 

q=deque()
q.append(start)
val=C.popleft()
Visit[start]=val

ans=0
while q:
	x=q.popleft()
	for to in nl[x]:
		if Visit[to] is None:
			val=C.popleft()
			Visit[to]=val
			ans+=val
			q.append(to)

print ans
for x in Visit[1:]:
	print x,

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

Solution (Python):
N=int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)] 
C = list(map(int, input().split())) 
C.sort()

M = sum(C[:-1])

adjacent_dict={}
for a,b in AB:
  adjacent_dict.setdefault(a, set()).add(b)
  adjacent_dict.setdefault(b, set()).add(a)
  

leafs = []
adjacents = [0] * (N+1) 
for k, v in adjacent_dict.items():
  adjacents[k] = len(v)
  if len(v)==1:
    leafs.append(k)

nodes = leafs.copy() 
visited = [0] * (N+1) 
for n in nodes:
  visited[n] = 1
  






  
  
while leafs:
  new_stack = []
  for v in leafs:
    for u in adjacent_dict[v]:
      adjacents[u] -= 1
      if visited[u]==0:
        visited[u]=1
        new_stack.append(u)
  leafs = [v for v in new_stack if adjacents[v]==1]
  nodes.extend(leafs)
  if not leafs:
    nodes.extend(new_stack) 
    break
  for u in [v for v in new_stack if adjacents[v]!=1]:
    visited[u] = 0
    
  
ans = [0]*(N)
for i in range(N):
  ans[nodes[i]-1] = C[i]
  
print(M)
print(*ans)

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(l[0][0])

score = 0

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

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

Solution (Python):
N = int(input())
E = [ [] for i in range(N)]
D = [0] * 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()))
x = max(c)
print(sum(c)-max(c))
start = 0
for i in range(N):
    if (len(E[i]) >= 2):
        start = i
        break
already = [0]*N
already[start] = 1
path = [start]
while(path):
    start = path[0]
    try:
        next = E[start][0]
    except:
        d = min(c)
        D[start] = d
        c.remove(d)
        path.remove(start)
        continue
    if already[next] == 1:
        E[start].remove(next)
        continue
    path.insert(0,next)
    already[next] = 1
for d in D:
    print(d,end = " ")

Solution (Python):


import itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

def main():
    N = int(input())
    d = [0] * N
    multi = [0] * N

    edges = defaultdict(list)
    edges_l = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        d[a-1] += 1
        d[b-1] += 1
        multi[a-1] += 1
        multi[b-1] += 1

        edges_l.append((a-1, b-1))
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)

    for i in range(len(d)):
        d[i] = (d[i], i)
    d.sort(key=lambda v: v[0], reverse=True)

    C = list(map(int, input().split()))
    C.sort(reverse=True)
    
    
    used = [False] * N
    ans = [0] * N
    count = 0
    que = []
    que.append(d[0][1])
    while que:
        index = que.pop()
        if not used[index]:
            
            ans[index] = C[count]
            used[index] = True
            count += 1

        
        for nei in edges[index]:
            if not used[nei]:
                que.append(nei)

    val = 0
    for a, b in edges_l:
        node_val = min(ans[a], ans[b])
        val += node_val

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

n = int(input())
ch = [[0,i] for i in range(n)]
graph = [[] for i in range(n)]

for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    ch[a][0] += 1
    ch[b][0] += 1
    graph[a].append(b)
    graph[b].append(a)

use =[0 for i in range(n)]

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

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

stack = [ch[0][1]]
count = 1
use[ch[0][1]] = 1
ans[ch[0][1]] = c[0]
while len(stack) > 0:
    now = stack.pop()
    data = graph[now]
    for i in data:
        if use[i] == 0:
            use[i] = 1
            ans[i] = c[count]
            count += 1
            stack.append(i)




print(sum(c)-c[0])
for i in ans:
    print(i,end=' ')

print()

Solution (Python):
import numpy as np
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
def rec(start, p):
    if ans[start] != -1:
        return p
    ans[start] = C[p]
    p += 1
    for node in tree[start+1]:
        p = rec(node-1, p)
    return p

N = int(input())
tree = defaultdict(list)
degree = [0 for i in range(N)]
edges = [0 for i in range(N-1)]
for i in range(N-1):
    a, b = map(int, input().split())
    edges[i] = (a, b)
    tree[a].append(b)
    tree[b].append(a)
for k, v in tree.items():
    degree[k-1] = len(v)

sort_i = np.argsort(degree)[::-1]


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


ans = 0
visited_e = []

visited = [False for i in range(N)]
p = 0
ans = [-1 for i in range(N)]
M = 0

rec(sort_i[0], p)

for e in edges:
    M += min(ans[e[0]-1], ans[e[1]-1])
    
print(M)
print(' '.join(list(map(lambda x: str(x), ans))))

Solution (Python):

import sys
import heapq
INF = float("inf")


def argmax(a):
    m, n = -(1 << 31), -1
    for i, v in enumerate(a):
        if m < v:
            m, n = v, i
    return n


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])  

        pass


def shortestPath(g: Graph, s: int):
    """ グラフgにおいて、始点sから各頂点への最短路を求める
    引数
    g: グラフ, s: 始点
    返り値
    dist: 始点からの距離が格納されたリスト
    prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    """
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    g = Graph(N)
    for _f, _t in zip(a, b):
        g.add_edge([_f-1, _t-1])
    dist, prev = shortestPath(g, 0)
    s = argmax(dist)
    dist, prev = shortestPath(g, s)
    g = argmax(dist)

    c.sort()

    
    ans = -1
    haichi = [0]*N
    while True:
        haichi[g] = c.pop()
        if ans == -1:
            ans = 0
        else:
            ans += haichi[g]
        if prev[g] == None:
            break
        else:
            g = prev[g]
    
    buf = []
    for i in range(N):
        if haichi[i] == 0:
            buf.append(i)
    buf.sort(key=lambda x: dist[x])
    for b in buf:
        haichi[b] = c.pop()
        ans += haichi[b]
    print(ans)
    print(*haichi)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    a = [int()] * (N-1)  
    b = [int()] * (N-1)  
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    c = [int(next(tokens)) for _ in range(N)]  
    solve(N, a, b, c)


if __name__ == '__main__':
    main()

Solution (Python):


from queue import PriorityQueue

def readInts():
  return [int(s) for s in input().split(" ")]

def main():
  N = readInts()[0]
  counts = [0 for _ in range(N)]
  edges = [[] for _ in range(N)]

  maxP = 0

  A = [0 for _ in range(N-1)]
  B = [0 for _ in range(N-1)]

  for i in range(N-1):
    A[i], B[i] = readInts()
    a, b = A[i] - 1, B[i] - 1
    counts[a] += 1
    counts[b] += 1
    if counts[a] > counts[maxP]:
      maxP = a
    if counts[b] > counts[maxP]:
      maxP = b

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

  c = readInts()
  c.sort(reverse=True)
  cursor = 0
  ans = [0 for _ in range(N)]

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

  queue = PriorityQueue()
  queue.put( (-1 * counts[maxP], maxP) )
  while not queue.empty():
    _, n = queue.get()
    ans[n] = c[cursor]
    cursor += 1
    visited[n] = True

    for p in edges[n]:
      if not visited[p]:
        queue.put( (-1 * counts[p], p) )

  s = 0
  for i in range(N-1):
    a, b = A[i] - 1, B[i] - 1
    s += min(ans[a], ans[b])

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

if __name__ == "__main__":
  main()

Solution (Python):

"""<https://github.com/cheran-senthil/PyRival>"""
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    _str = str
    str = lambda x=b"": x if type(x) is bytes else _str(x).encode()


def main():
    N = read_int()
    g = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = read_int_array()
        g[a-1].append(b-1)
        g[b-1].append(a-1)
    C = read_int_array()
    C.sort()
    labels = [None]*N
    labels[0] = C.pop()
    M = sum(C)
    q = [0]
    for x in q:
        for ch in g[x]:
            if labels[ch] is None:
                q.append(ch)
                labels[ch] = C.pop()

    print(M)
    print(' '.join(map(str, labels)))







BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        if self.buffer.tell():
            return self.buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", b" "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", b"\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip(b"\r\n")


def read():
    return input()


def read_array(sep=None, maxsplit=-1):
    return read().split(sep, maxsplit)


def read_int():
    return int(read())


def read_int_array(sep=None, maxsplit=-1):
    return [int(a) for a in read_array(sep, maxsplit)]



if __name__ == "__main__":
    main()

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

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

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

c_list.sort()
c_list.reverse()

d_table = {}
d_rev = [None] * N
for i in range(N):
	d = len(table[i])
	if d in d_table:
		d_table[d].add(i)
	else:
		d_table[d] = {i}
	d_rev[i] = d

scores = [None] * N
for i in range(N):
	if i in d_table:
		n_set = d_table[i]
		while n_set:
			n = n_set.pop()
			scores[n] = c_list.pop()
			for n2 in table[n]:
				d = d_rev[n2]
				d_rev[n2] = d - 1
				n_set2 = d_table[d]
				if n2 in n_set2:
					n_set2.remove(n2)
					if d - 1 in d_table:
						d_table[d - 1].add(n2)
					else:
						d_table[d - 1] = {n2}

for i in range(N):
	if scores[i] == None:
		scores[i] = c_list[0]

score = 0
stack = [0]
visited = set()
visited.add(0)
while stack:
	cur = stack.pop()
	s1 = scores[cur]
	for n in table[cur]:
		if not n in visited:
			s2 = scores[n]
			if s1 < s2:
				score += s1
			else:
				score += s2
			stack.append(n)
			visited.add(n)

print(score)
print(" ".join([str(s) for s in scores]))

Solution (Python):
from collections import defaultdict
from collections import deque

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)
        self.node = defaultdict(int)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def get_nodes(self):
        return self.graph.keys()

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


G = Graph()
N = int(input())
for i in range(N - 1):
	a, b = getlist()
	G.add_edge(a - 1, b - 1)
	G.add_edge(b - 1, a - 1)
	G.node[a - 1] += 1
	G.node[b - 1] += 1

c = getlist()
c = sorted(c)

cnt = []
for i in G.node:
	cnt.append([G.node[i], i])

D = defaultdict(int)
Q = deque()
for i in G.node:
	if G.node[i] == 1:
		Q.append(i)


val = 0
while Q:
	x = Q.popleft()
	D[x] = c[val]
	val += 1
	for i in G.graph[x]:
		G.node[i] -= 1
		if G.node[i] == 1:
			Q.append(i)




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

ansL = []
for i in range(N):
	ansL.append(D[i])

ansL = list(map(str, ansL))
print(" ".join(ansL))

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

Solution (Python):
from collections import deque

N = int(input())
eg = []
v_cnt = [0 for i in range(N)]
v_to = [[] for i in range(N)]
v_ans = [0 for i in range(N)]
v_visited = [False for i in range(N)]

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

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

v_m = 0
for i in range(N):
    if v_m < v_cnt[i]:
        v_m = i

q = deque([v_m])
while len(q) > 0:
    i = q.popleft()

    v_ans[i] = c.pop()
    v_visited[i] = True
    for ni in v_to[i]:
        if not v_visited[ni]:
            q.append(ni)

ans = 0
for a, b in eg:
    ans += min(v_ans[a], v_ans[b])

print(ans)
print(*v_ans)