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.



Sample input:
5
1 2
2 3
3 4
4 5
1 2 3 4 5


Sample output:
10
1 2 3 4 5

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# N = int(input())
# edge = []
# for _ in range(N - 1):
#     a, b = map(int, input().split())
#     edge.append((a - 1, b - 1))
#
# c = sorted(map(int, input().split()))
# M = sum(c[:-1])
# use = [0 for _ in range(N)]
#
# for e in edge:
#     a, b = e
#     if use[a] == 0:
#         use[a] = c.pop()
#     if use[b] == 0:
#         use[b] = c.pop()
#
# print(M)
# print(*use)



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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)
        #print(score)
        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(d)
print(sum(s))
print(*t)

Submission status: Accepted

Solution code:
import numpy as np 
N = int(input())
# N = 1000
# G = np.zeros((N,N),dtype = np.bool)

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

for i in range(N-1):
    a,b = map(int,input().split())
    # a,b = 1,2
    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))
# Cs = [1 for i in range(N)]

# print(Cs)

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

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

# minag = np.argmin(links)
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
    # print(nodeval)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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 = [i for i, e in enumerate(edge) if len(e) == 1]
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)))

Submission status: Accepted

Solution code:
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))))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
from collections import deque
# import heapq


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

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
n,*t=map(int,open(0).read().split())
c=sorted(t[-n:])
e=[[]for _ in[0]*n]
for a,b in zip(t[:-n:2],t[1:-n:2]):e[a-1]+=b-1,;e[b-1]+=a-1,
q=[0]
f=q*n
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)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

N = int(input())
adj_list = defaultdict(list)
E = []
V_number = [None]*N
for _ in range(N-1):
    a, b = map(int, input().split())
    E.append((a, b))
    adj_list[a].append(b)
    adj_list[b].append(a)
C = sorted(list(map(int, input().split())), reverse=True)
q = deque([1])
i = 0
while q:
    v = q.popleft()
    V_number[v-1] = C[i]
    i += 1
    for u in adj_list[v]:
        if V_number[u-1] is None:
            q.append(u)

print(sum(C[1:]))
print(*V_number)

Submission status: Accepted

Solution code:
#実験用の写経
N = int(input())
g = {i: [] for i in range(N)}
for i in range(N - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
c = list(map(int, input().split()))
c.sort()
print(sum(c[:-1]))
nums = [0] * N
stack = [0]
while stack:
    d = stack.pop()
    nums[d] = c.pop()
    for node in g[d]:
        if nums[node] == 0:
            stack.append(node)
print(' '.join(map(str, nums)))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env 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()

Submission status: Accepted

Solution code:
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)
max_c = sorted_c[-1]

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]
            w = c1 if c1 < c2 else c2
            M += w
            q.append(neighbor)

print(M)
print(*use)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
g = [[] for i in range(n)]

for i in range(n-1):
  a,b = na()
  g[a-1].append(b-1)
  g[b-1].append(a-1)

c = na()
c = sorted(c)

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

ans = [0]*n
st = [0]

while st:
  d = st.pop()
  ans[d] = c.pop()
  for v in g[d]:
    if ans[v] == 0:
      st.append(v)

print(' '.join([str(s) for s in ans]))

Submission status: Accepted

Solution code:
n = int(input())

edge = [[] for i in range(n)]

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

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

hhh = c.copy()

c.sort(reverse=True)

w = [0] * n

w[0] = c.pop(0)

chk = [i for i in edge[0]]
# print(chk)

while chk != []:
    node = chk.pop(0)
    if w[node] == 0:
        w[node] = c.pop(0)
        chk.extend(edge[node])

print(sum(hhh) - max(hhh))

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

Submission status: Accepted

Solution code:
N=int(input());g={i:[]for i in range(N)}
for i in range(N-1):a,b=map(int,input().split());g[a-1].append(b-1);g[b-1].append(a-1)
c=sorted(list(map(int,input().split())));n=[0]*N;s=[0];print(sum(c[:-1]))
while s:
 d=s.pop()
 n[d]=c.pop()
 for m in g[d]:
  if n[m]==0:
   s.append(m)
print(' '.join(map(str,n)))

Submission status: Accepted

Solution code:
N = int(input())
es = [[] for idx in range(N)]
# es[idx]:=[隣接リスト]

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

h = [len(es[i]) for i in range(N)]
# 次数

c = list(map(int, input().split()))
c.sort()
# スコアが小さい順にソート

v = [-1] * N
cur = 0
ans = 0
for _ in range(N - 1):
    for target in range(N):
        # print(target, h, v, ans)
        if h[target] == 1:
            h[target] = 0
            v[target] = c[cur]
            ans += c[cur]
            cur += 1
            for nv in es[target]:
                h[nv] -= 1
            break
for target in range(N):
    if v[target] == -1:
        v[target] = c[cur]
print(ans)
print(*v, sep='\n')

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
 
#A
def A():
    n = II()
    print((n-2)*180)
    return
 
#B
def B():
    b = S()
    kati = b.count("o")
    kati += 15 - len(b)
    if kati >= 8:
        print("YES")
    else:
        print("NO")
    return
 
#C
def C():
    return
 
#D
def D():
    n = II()
    ab = LIR_(n-1)
    C = LI()
    C.sort()
    c = deque(C)
    edg = [[] for i in range(n)]
    for a, b in ab:
        edg[a].append(b)
        edg[b].append(a)
    for num,e in enumerate(edg):
        if len(e) == 1:
            start = num
            break
    q = deque()
    ans = [0 for i in range(n)]
    q.append(start)
    ans[start] = c.pop()
#    print(start)
    while q:
        p = q.pop()
        for e in edg[p]:
            if not ans[e]:
                ans[e] = c.pop()
                q.append(e)
    anssum = 0
    for a, b in ab:
        anssum += min(ans[a], ans[b])
    print(anssum)
    ans = list(map(str, ans))
    print(" ".join(ans))
 
 
    return
 
#E
def E():
    return
 
#F
def F():
    return
 
#G
def G():
    return
 
#H
def H():
    return
 
#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
from collections import deque


def main():
    N = int(input())
    ans = [0] * N
    adj = [set() for _ in range(N)]
    edge = [None] * (N-1)
    for i in range(N-1):
        a, b = map(int, input().split())
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)
        edge[i] = (a-1, b-1)
    C = list(map(int, input().split()))
    C.sort()
    q = deque()
    for i in range(N):
        if len(adj[i]) == 1:
            q.append(i)
    x = 0
    while len(q):
        n = q.popleft()
        ans[n] = C[x]
        x += 1
        for a in adj[n]:
            adj[a].remove(n)
            if len(adj[a]) == 1:
                q.append(a)
    total = 0
    for i in range(N-1):
        a, b = edge[i]
        total += min(ans[a], ans[b])
    print(total)
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
ab = list()
for _ in range(n - 1):
    ab.append(list(map(int, input().split())))

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

tree = [[] for i in range(n)]
for a, b in ab:
    tree[a - 1].append(b - 1)
    tree[b - 1].append(a - 1)

c.sort(reverse=True)

ans = [-1 for _ in range(n)]
ans[0] = c.pop(0)

q = list()
q.append(0)

while(len(q) != 0):
    v = q.pop(0)
    for u in tree[v]:
        if ans[u] != -1:
            continue
        ans[u] = c.pop(0)
        q.append(u)

print(sum(ans[1:]))
print(" ".join([str(a) for a in ans]))

Submission status: Accepted

Solution code:
import heapq
import sys
sys.setrecursionlimit(10000000)
n=int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
c=sorted(list(map(lambda x:-int(x), input().split())))
print(-sum(c[1:]))
heapq.heapify(c)
mat = [[] for _ in range(n+1)]
ans=[0]*n
for i in range(n-1):
    a, b = ab[i]
    mat[a].append(b)
    mat[b].append(a)
def dp(x, y):
    ans[y-1]=-heapq.heappop(c)
    if y>1 and len(mat[y])==1:
        return
    for i in mat[y]:
        if i!=x:
            dp(y, i)
dp(0, 1)
print(' '.join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(100000)
n = int(input())

edges=[[] for i in range(n+1)]
d=[-1 for i in range(n+1)]
for i in range(1,n):
	a, b=[int(i) for i in input().split()]
	edges[a].append([b,1])
	edges[b].append([a,1])
def kyori(u):
	for v,w in edges[u]:
		if d[v]==-1:
			d[v]=d[u]+w
			kyori(v)

d[1]=0
kyori(1)

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

ans_lst = [0] * n
ans = sum(D[1:])

ans_lst[0] = D[0]
now_kyori = 1
idx = 1
m = 1
idx_lst = [i for i in range(n)]

d.pop(0)

lst = np.array([d, idx_lst]).T.tolist()
lst.sort()
d = np.array(lst).T.tolist()[0]
idx_lst = np.array(lst).T.tolist()[1]

for i in range(n):
    ans_lst[idx_lst[i]] = D[i]

ans_lst = list(map(str, ans_lst))
mojiretu = ' '.join(ans_lst)
print(ans)
print(mojiretu)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000) 

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

def ab(i):
    global c,l,x
    while len(l[i])>0:
        x[l[i][0]] = c.pop(0)
        l[l[i][0]].remove(i)
        ab(l[i][0])
        l[i].pop(0)
    return

n=int(input())
l = [[] for _ in range(n+1)]
for i in range(n-1):
    a,b=intinput()
    l[a].append(b)
    l[b].append(a)
c = list(intinput())
c.sort(reverse=1)
x = [0 for _ in range(n+1)]
x[1]=c.pop(0)
for i in range(1,n+1):
    ab(i)
print(sum(x[2:]))
f = ""
q= len(x[1:])
for i in range(q):
    if i != q-1:
        f += str(x[i+1])+" "
    else:
        f += str(x[i+1])
print(f)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N = int(input())
p = [list(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
c = list(map(int,input().split()))

def dfs(v,gen,node):
    Stack = []
    visit[v] = True
    Stack.append(v)
    while Stack:
        v = Stack.pop()
        node[v] = gen.__next__()
        for i in nextl[v]:
            if not visit[i]:
                visit[i] = True
                Stack.append(i)

def list2gen(l):
    for e in l:
        yield e

node = [0]*N
visit = [False]*N
nextl = [[] for i in range(N)]
for a, b in p:
    nextl[a].append(b)
    nextl[b].append(a)
c.sort(reverse=True)
gen = list2gen(c)
dfs(0,gen,node)
anssum = sum(c[1:])
print(anssum)
for e in node:
    print(e,end=" ")

Submission status: Accepted

Solution code:
class Queue(object):

    def __init__(self):
        self.queue_list = []

    def enqueue(self, value):
        self.queue_list.append(value)

    def dequeue(self):
        try:
            value = self.queue_list.pop(0)
        except IndexError:
            value = None

        return value

N = int(input())

pair = []
tree = {}

for _ in range(N-1):
    a, b = list(map(int, input().split(" "))) 
    if a in tree.keys():
        tree[a].append(b)
    else:
        tree[a] = [b]
        
    if b in tree.keys():
        tree[b].append(a)
    else:
        tree[b] = [a]
    pair.append([a,b])
    
c = list(map(int, input().split(" ")))
c.sort(reverse=True)
c = c[:N+2]


queue = Queue()
tree_l = {}
for key in tree.keys():
    tree_l[key] = len(tree[key])

ans = {}
max_node = max((v, k) for k, v in tree_l.items())[1]
ans[max_node] = c[0]
used = [max_node]
cnt = 0

candi = {}
for i in tree[max_node]:
    candi[i] = tree_l[i]

for k, v in sorted(candi.items(), key=lambda x: -x[1]):
    queue.enqueue(k)
    used.append(k)

while True:
    node = queue.dequeue()
    cnt += 1
    ans[node] = c[cnt]
    
    if cnt == N-1:
        break
    
    candi = {}
    for i in tree[node]:
        candi[i] = tree_l[i]
    for k, v in sorted(candi.items(), key=lambda x: -x[1]):
        if k not in used:
            queue.enqueue(k)
            used.append(k)
total = 0
for a, b in pair:
    if ans[a] > ans[b]:
        total += ans[b]
    else:
        total += ans[a]
        
print(total)
for i in range(1, N, 1):
    print(ans[i], end=" ")

print(ans[N])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
g = [[] for _ 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))

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


ans = [-1 for _ in range(n)]

#次にどの頂点に行くのかを表すリスト
q = list()
 
# g[0] の処理
ans[0] = c_list[0]
c_list.pop(0)
#始め0から始めたいから0
q.append(0)

#qが0になるまで動かしたい
while(len(q) != 0):
    v = q[0]
    q.pop(0)
    for u in g[v]:
        # print(v, u, w)
        if ans[u] != -1:
            continue
        # 問題特有のやつ
        ans[u] = c_list[0]
        c_list.pop(0)
        #uという頂点を次にみる
        q.append(u)
    # print(v, q)


print(sum(ans[1:]))
print(" ".join([str(a) for a in ans]))

Submission status: Accepted

Solution code:
class Queue(object):

    def __init__(self):
        self.queue_list = []

    def enqueue(self, value):
        self.queue_list.append(value)

    def dequeue(self):
        try:
            # 先頭をとりだす
            value = self.queue_list.pop(0)
        except IndexError:
            value = None

        return value
N = int(input())

pair = []
tree = {}

for _ in range(N-1):
    a, b = list(map(int, input().split(" "))) 
    if a in tree.keys():
        tree[a].append(b)
    else:
        tree[a] = [b]
        
    if b in tree.keys():
        tree[b].append(a)
    else:
        tree[b] = [a]
    pair.append([a,b])
    
c = list(map(int, input().split(" ")))
c.sort(reverse=True)
c = c[:N+2]


queue = Queue()
tree_l = {}
for key in tree.keys():
    tree_l[key] = len(tree[key])

ans = {}
max_node = max((v, k) for k, v in tree_l.items())[1]
ans[max_node] = c[0]
used = [max_node]
cnt = 0

candi = {}
for i in tree[max_node]:
    candi[i] = tree_l[i]

for k, v in sorted(candi.items(), key=lambda x: -x[1]):
    queue.enqueue(k)
    used.append(k)

while True:
    node = queue.dequeue()
    cnt += 1
    ans[node] = c[cnt]
    
    if cnt == N-1:
        break
    
    candi = {}
    for i in tree[node]:
        candi[i] = tree_l[i]
    for k, v in sorted(candi.items(), key=lambda x: -x[1]):
        if k not in used:
            queue.enqueue(k)
            used.append(k)
total = 0
for a, b in pair:
    if ans[a] > ans[b]:
        total += ans[b]
    else:
        total += ans[a]
        
print(total)
for i in range(1, N, 1):
    print(ans[i], end=" ")

print(ans[N])

Submission status: Accepted

Solution code:
class Queue(object):

    def __init__(self):
        self.queue_list = []

    def enqueue(self, value):
        self.queue_list.append(value)

    def dequeue(self):
        try:
            # 先頭をとりだす
            value = self.queue_list.pop(0)
        except IndexError:
            value = None

        return value
N = int(input())

pair = []
tree = {}

for _ in range(N-1):
    a, b = list(map(int, input().split(" "))) 
    if a in tree.keys():
        tree[a].append(b)
    else:
        tree[a] = [b]
        
    if b in tree.keys():
        tree[b].append(a)
    else:
        tree[b] = [a]
    pair.append([a,b])
    
c = list(map(int, input().split(" ")))
c.sort(reverse=True)
c = c[:N+2]


queue = Queue()
tree_l = {}
for key in tree.keys():
    tree_l[key] = len(tree[key])

ans = {}
max_node = max((v, k) for k, v in tree_l.items())[1]
ans[max_node] = c[0]
used = [max_node]
cnt = 0

candi = {}
for i in tree[max_node]:
    candi[i] = tree_l[i]

for k, v in sorted(candi.items(), key=lambda x: -x[1]):
    queue.enqueue(k)
    used.append(k)

while True:
    node = queue.dequeue()
    cnt += 1
    ans[node] = c[cnt]
    
    if cnt == N-1:
        break
    
    candi = {}
    for i in tree[node]:
        candi[i] = tree_l[i]
    for k, v in sorted(candi.items(), key=lambda x: -x[1]):
        if k not in used:
            queue.enqueue(k)
            used.append(k)
total = 0
for a, b in pair:
    if ans[a] > ans[b]:
        total += ans[b]
    else:
        total += ans[a]
        
print(total)
for i in range(1, N, 1):
    print(ans[i], end=" ")

print(ans[N])