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:
import sys
sys.setrecursionlimit(4100000)

N = int(input())
edges = [[] for _ in range(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()))
L = [0] * N

c.sort(reverse = True)

def dfs(x, par, index):
    L[x] = c[index]
    for u in edges[x]:
        if u != par:
            index += 1
            index = dfs(u, x, index)
    return index

dfs(0, -1, 0)

print(sum(L[1:]))
print(*L)

Submission status: Accepted

Solution code:
N = int(input())
D = {i: [0] for i in range(N)}
for i in range(N-1):
  a, b = map(int, input().split())
  D[a-1].append(b-1)
  D[a-1][0] += 1
  D[b-1].append(a-1)
  D[b-1][0] += 1
m = 0
nod = -1
for i in D:
  if m < D[i][0]:
    m = D[i][0]
    nod = i
c = list(map(int, input().split()))
c.sort(reverse=True)
pnt = 0
cnt = 1
p = [nod]
L = [-1 for _ in range(N)]
L[nod] = c[0]
while cnt < N:
  n = cnt
  for i in range(pnt, cnt):
    for j in range(1, D[p[i]][0]+1):
      if L[D[p[i]][j]] == -1:
        L[D[p[i]][j]] = c[cnt]
        cnt += 1
        p.append(D[p[i]][j])
  pnt = n
S = 0
for i in D:
  for j in range(1, D[i][0]+1):
    S += min(L[i], L[D[i][j]])
print(S//2)
for i in range(N):
  print(L[i], end = ' '*(i != N - 1))
print()

Submission status: Accepted

Solution code:
n=int(input())
e=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(lambda x:int(x)-1,input().split())
  e[a].append(b)
  e[b].append(a)
c=list(map(int,input().split()))
c.sort()
print(sum(c[:-1]))

c.reverse()
ans=[0 for i in range(n)]
ans[0]=c[0]
k=1

s=[0]
while s:
  ns=[]
  for i in s:
    for j in e[i]:
      if ans[j]:
        continue
      ans[j]=c[k]
      k+=1
      ns.append(j)
  s=ns
print(" ".join(map(str,ans)))

Submission status: Accepted

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(10**7)

n=int(input())
to=[[] for _ in range(n)]
eda=[]
for _ in range(n-1):
  a,b=map(int,input().split())
  to[a-1].append(b-1)
  to[b-1].append(a-1)
  eda.append([a-1,b-1])
  
c=list(map(int,input().split()))

c.sort(reverse=True)

cd=deque(c)
poi=[0 for _ in range(n)] 
vi=[-1 for _ in range(n)]

vi[0]+=1
def dfs(now):
  vi[now]+=1
  v=cd.popleft()
  poi[now]+=v
  for i in to[now]:
    if vi[i]==-1:
      dfs(i)
  
dfs(0)

ans=0

for u in eda:
  x,y=u
  ans+=min(poi[x],poi[y])
  
print(ans)
for u in range(n):
  poi[u]=str(poi[u])
  
print(' '.join(poi))

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
ad_ls = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    ad_ls[a].append(b)
    ad_ls[b].append(a)
c_ls = list(map(int, input().split()))
c_ls.sort(reverse=True)
c_q = deque(c_ls)

# d_ls[i] := 0idxでi番目の頂点に書く数字
d_ls = [0] * N

q = deque()
q.append(0)
d_ls[0] = c_q.popleft()
while q:
    now = q.popleft()
    for nex in ad_ls[now]:
        if d_ls[nex] == 0:
            d_ls[nex] = c_q.popleft()
            q.append(nex)

print(sum(c_ls) - max(c_ls))
print(*d_ls)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

N = int(readline())
G = [[] for i in range(N)]

for i in range(N - 1):
  a,b = map(int,readline().split())
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)
  
C = list(map(int,readline().split()))

def get_farest(x):
  dist = [-1] * N
  stack = [(x,-1,0)]
  while stack:
    v,parent,c = stack.pop()
    if dist[v] != -1:
      continue
    dist[v] = c
    for child in G[v]:
      if child == parent:
        continue
      stack.append([child, v, c + 1])
  maxv = -1
  maxi = -1
  for i in range(len(dist)):
    if dist[i] > maxv:
      maxv = dist[i]
      maxi = i
  return maxi

f = get_farest(0)
start = get_farest(f)

C = sorted(C, reverse = True)
from collections import deque
q = deque([])
q.append([start, -1])
ind = 0
ans = [None] * N
while q:
  v,parent = q.popleft()
  ans[v] = C[ind]
  ind += 1
  for child in G[v]:
    if child == parent:
      continue
    q.append([child, v])
  
print(sum(C[1:]))
print(*ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
ab = [LIST() for _ in range(N-1)]
c = sorted(LIST())
print(sum(c)-c[-1])

cnt = [0]*N
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)
	cnt[a-1] += 1
	cnt[b-1] += 1

ans = [0]*N

q = deque([0])
while q:
	p = q.popleft()
	ans[p] = c.pop()
	for i in graph[p]:
		if ans[i] == 0:
			q.append(i)

print(*ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
ab = [LIST() for _ in range(N-1)]
c = sorted(LIST())
print(sum(c)-c[-1])

cnt = [0]*N
graph = [[] for _ in range(N)]

for a, b in ab:
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)
	cnt[a-1] += 1
	cnt[b-1] += 1

ans = [0]*N

q = deque([cnt.index(max(cnt))])
while q:
	p = q.popleft()
	ans[p] = c.pop()
	for i in graph[p]:
		if ans[i] == 0:
			q.append(i)

print(*ans)

Submission status: Accepted

Solution code:
from collections import deque


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

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

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


def main():
    ans = [0] * N
    ans[0] = c.pop()
    S = 0

    seen = [0] * N
    seen[0] = 1
    que = deque([0])

    while que:
        v = que.popleft()
        for nv in to[v]:
            if not seen[nv]:
                seen[nv] = 1
                ans[nv] = c.pop()
                S += ans[nv]
                que.append(nv)

    print(S)
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def dfs(v,p):
    ans[v]=c.pop()
    for nv in G[v]:
        if nv==p:
            continue
        dfs(nv,v)

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

for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
c=sorted(map(int,input().split()))
print(sum(c[:-1]))
ans=[-1]*N
dfs(0,-1)
print(*ans)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect

n=int(input())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(n-1))
c=list(map(int,input().split()))
c.sort(reverse=True)
node=[[] for _ in range(n)]
d=deque()
d.append(0)
seen=[0]*n
seen[0]=1
ans=[0]*n
for pair in v:
    node[pair[0]].append(pair[1])
    node[pair[1]].append(pair[0])

s=0
while d:
    i=d.pop()
    ans[i]=c[s]
    s+=1
    for j in node[i]:
        if seen[j]==0:
            d.appendleft(j)
            seen[j]=1
print(sum(ans)-c[0])
print(*ans)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect

n=int(input())
v=tuple(tuple(map(lambda x: int(x)-1,input().split())) for _ in range(n-1))
c=list(map(int,input().split()))
c.sort(reverse=True)
node=[[] for _ in range(n)]
d=deque()
d.append(0)
seen=[0]*n
seen[0]=1
ans=[0]*n
for pair in v:
    node[pair[0]].append(pair[1])
    node[pair[1]].append(pair[0])

s=0
while d:
    i=d.pop()
    ans[i]=c[s]
    s+=1
    for j in node[i]:
        if seen[j]==0:
            d.append(j)
            seen[j]=1
print(sum(ans)-c[0])
print(*ans)

Submission status: Accepted

Solution code:
N=int(input())
G=[[] for _ 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,=map(int,input().split())

from collections import deque

def bfs(s):
    seen = [0]*N
    d = [0]*N
    prev = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
          prev[b] = a
    return d, prev

d, prev = bfs(0)
order = list(zip(*sorted(enumerate(d), key=lambda x:x[1])))[0]

dp = [1]*N
for v in order[::-1]:
    if len(G[v])==0:
        dp[v] = 1
    dp[prev[v]] += dp[v]
    
sizes=[0]*N
for i in range(N):
  if i == 0:
    tmp = max([dp[v] for v in G[i]])
    sizes[i]=tmp
    continue
  tmp = max(dp[i]-1,N-dp[i])
  sizes[i]=tmp
  
MIN=10**20
argmin=-1
for i in range(N):
  if sizes[i]<MIN:
    MIN=sizes[i]
    argmin=i
    
c = sorted(c,reverse=True)
score=[0]*N
score[argmin]=c[0]

def bfs2(s):
    i = 1
    seen = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while len(todo):
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          score[b] = c[i]
          i += 1
    return 
  
bfs2(argmin)

ans=0
for i in range(N):
  for j in G[i]:
    if i>j:continue
    ans += min(score[i],score[j])
    
print(ans)
print(*score)

Submission status: Accepted

Solution code:
n = int(input())

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

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

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

from collections import deque

dq = deque()

dq.append(0)
ans = [-1] * n

while len(dq) > 0:
    node = dq.popleft()
    ans[node] = c[idx]
    idx += 1
    for next_node in adj_list[node]:
        if ans[next_node] < 0:
            dq.append(next_node)

print(sum(c[1:]))
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

not_visited = [-1]*N
not_visited[0] = 0
stack = deque()
stack.append(0)

ans = [0]*N
ans[0] = c[0]

cut = 1
while stack:
    now = stack.popleft()
    for nex in lines[now]:
        if not_visited[nex] == -1:
            ans[nex] = c[cut]
            not_visited[nex] =  not_visited[now] + 1
            cut += 1
            stack.append(nex)

print(sum(c[1:]))
print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)


def DFS(num,pre):
    global point
    if color[num]=="white":
        A[num]=C.pop()
        point +=min(A[num],pre)
        color[num]="black"
        for i in tree[num]:
            DFS(i,A[num])


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

color=["white" for _ in range(n+1)]
tree=[[] for _ in range(n+1)]
for a,b in AB:
    tree[a].append(b)
    tree[b].append(a)

A=[0 for _ in range(n+1)]
point=0
DFS(1,0)

print(point)
print(*A[1:])

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    ai, bi = map(lambda x: int(x) - 1, input().split())
    G[ai].append(bi)
    G[bi].append(ai)


# 大きい数字から順番に割り当てる
C = list(map(lambda x: -int(x), input().split()))
heapify(C)
score = -sum(C) + min(C)

# どこかの葉にmaxを置いて，そこから順番に置く
# => maxの値は葉のスコア計算で消えてOK
leaf = -1
for n in range(N):
    if len(G[n]) == 1:
        leaf = n
        break

# 深さ優先で全探索
queue = [leaf]
ans = [-1] * N
while queue:
    node = queue.pop()
    for neighbor in G[node]:
        if ans[neighbor] == -1:
            ans[neighbor] = -heappop(C)
            queue.append(neighbor)

print(score)
print(*ans)

Submission status: Accepted

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def solve():
    n = getN()
    g = [[] for i in range(n)]
    ans = [-1 for i in range(n)]
    ji = [0 for i in range(n)]

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

    cn = getList()
    cn.sort()
    h = []
    for i, j in enumerate(ji):
        heappush(h, (j, i))

    anss = 0

    for cnn in cn:
        while True:
            cj, ci = heappop(h)
            if ans[ci] == -1:
                ans[ci] = cnn
                anss += cnn * cj
                for gg in g[ci]:
                    ji[gg] -= 1
                    heappush(h, (ji[gg], gg))
                break

    print(anss)
    print(*ans)
def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    ab = [0] * (N-1)
    num = [0] * N
    l = [[] for _ in range(N)]
    for n in range(N-1):
        a, b = [int(x)-1 for x in input().strip().split()]
        l[a].append(b)
        l[b].append(a)
    C = sorted([int(x) for x in input().strip().split()], reverse=True)
    ans = 0
    q = [0]
    i = 0
    while q:
        c = q.pop()
        num[c] = C[i]
        i += 1
        for n in l[c]:
            if num[n] == 0:
                q.append(n)

    print(sum(num)-C[0])
    print(*num)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def msol19_d():
    n = int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        graph[a].append(b)
        graph[b].append(a)
    C = sorted(map(int, input().split()), reverse=True)

    score = sum(C[1:])
    label = [-1]*n
    from collections import deque
    que = deque([0])
    idx = 0
    while que:
        u = que.popleft()
        label[u] = C[idx]
        idx += 1
        for v in graph[u]:
            if label[v] != -1: continue
            que.append(v)
    print(score)
    print(*label, sep=' ')

if __name__ == '__main__':
    msol19_d()

Submission status: Accepted

Solution code:
from collections import deque


def main():
    n = int(input())
    ans = [0 for _ in range(n)]
    graph = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        graph[a].append(b)
        graph[b].append(a)
    c = list(map(int, input().split()))
    c.sort(reverse=True)
    root = 0
    max_deg = 0
    for i in range(n):
        if max_deg < len(graph[i]):
            root = i
            max_deg = len(graph[i])
    q = deque([root])
    ans[root] = c[0]
    idx = 1
    while q:
        now_v = q.pop()
        for next_v in graph[now_v]:
            if ans[next_v] == 0:
                ans[next_v] = c[idx]
                idx += 1
                q.append(next_v)
    print(sum(c[1:]))
    print(" ".join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

#大きいものから適当に決める。
#総和は最大数を除いた和になる選び方ができる。
#適当に最大数を置いて、周囲に大きい数字から順に置いていく
#BFSかな
N = int(input())
road = [[] for _ in range(N+1)]#1~N番までの道
number = [0]*(N+1)#indexに置く数字のメモ。BFSでは0なら行き先追加
for _ in range(N-1):
    a,b=map(int,input().split())
    road[a].append(b)
    road[b].append(a)
c = list(map(int,input().split()))

q = collections.deque([])
cSort=sorted(c)
number[1]=cSort.pop()
q.append(1)

while q:
    now = q.popleft()
    for idx in road[now]:
        if number[idx]==0:
            q.append(idx)
            number[idx]=cSort.pop()
print(sum(number[2:]))
print(*number[1:])

Submission status: Accepted

Solution code:
n=int(input())
e=[[i] for i in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
c=sorted(list(map(int,input().split())))
q=[1]
vis=[0]*(n+1)
ans=0
while q:
  now=q.pop()
  vis[now]=c.pop()
  for to in e[now]:
    if vis[to]:continue
    q+=[to]
print(sum(vis[2:]))
print(*vis[1:])

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)
    c = LI()
    c.sort()

    # 最大の数は使われない、2番目に大きい数は、最大の数の隣のときだけ使われる
    # 深くなるほど小さくなるように置けば良い
    # DFSで置いていく
    ans = [0] * N
    def dfs(cur):
        ans[cur] = c.pop()
        for nxt in G[cur]:
            if ans[nxt] == 0:
                dfs(nxt)

    dfs(0)

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

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n = int(input())
graph = [[] for _ in range(n)]
cnt = [0] * (n)
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

C = list(map(int, input().split()))
C.sort(reverse=True)
num = sum(C[1:])

ans = [0] * (n)

start = 0
par = [-1] * n
stack = [start]
idx = 0
ans[0] = C[idx]
idx += 1
while stack:
    v = stack.pop()
    for u in graph[v]:
        if u == par[v]:
            continue
        par[u] = v
        ans[u] = C[idx]
        idx += 1
        stack.append(u)
    # print(stack)

print(num)
print(*ans, sep=" ")

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import deque, defaultdict
    n = int(readline())
    edge = defaultdict(list)

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

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

    nums = [0] * (n + 1)

    que = deque()
    que.append((1, 0))

    cnt = 0
    m = 0

    while que:
        cur, prev_num = que.popleft()
        num = c[cnt]
        nums[cur] = num
        m += min(num, prev_num)
        cnt += 1
        for nx in edge[cur]:
            if nums[nx] == 0:
                que.append((nx, num))

    print(m)
    print(*nums[1:])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
V = [[] for i in range(n+1)]

a = [0]*(n-1)
for i in range(n-1):
    A,B = map(int,input().split())
    V[A].append(B)
    V[B].append(A)

c = list(map(int,input().split()))
c = sorted(c, reverse=True)
ans = sum(c[1:])


L = [0]*n
for i in range(1,n+1):
    L[i-1] = [i, len(V[i])]
    
L.sort(key= lambda val : val[1], reverse=True)

q = deque([])
d = [-1] + [0]*n
j = 0

q.append(L[0][0])
d[L[0][0]] = c[0]
j += 1

while q:
    x = q.popleft()
    for y in V[x]:
        if d[y] <= 0:
            q.append(y)
            d[y] = c[j]
            j += 1

print(ans)
for i in range(1,n+1):
    print(d[i],end="")
    print(" ",end="")

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    C = list(map(int, input().split()))
    C.sort(reverse=True)

    M = sum(C[1:])
    d = [0] * N
    i = 0
    queue = deque([(i, -1)])
    while queue:
        u, p = queue.popleft()
        d[u] = C[i]
        i += 1
        for v in G[u]:
            if v == p: continue
            queue.append((v, u))

    print(M)
    print(" ".join(map(str, d)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

queue = deque([0])
ans = [0 for i in range(n)]
num = n - 1
while queue:
    cur_node = queue.popleft()
    if ans[cur_node] > 0:
        continue
    ans[cur_node] = c[num]
    num -= 1
    for i in t[cur_node]:
        queue.append(i)
print(sum(c) - max(c))
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

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

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

stack=deque([0])
check = [-1]*N
check[0] = 0

while len(stack)>0:
    v = stack.popleft()
    for i in root[v]:
        if check[i] == -1:
            check[i]=check[v]+1
            stack.append(i)

keyCheck = [(i,check[i]) for i in range(N)]
keyCheck.sort(key=lambda t:t[1])
#print(keyCheck)
ans = [-1]*N
for i in range(N):
    ans[keyCheck[i][0]] = c[i]

print(sum(c[1:]))
print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

def bfs():
    q = deque([0])
    dist = [-1]*N
    dist[0] = 0
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
    
    return dist

N = int(input())
G = [[] for _ 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 = list(map(int, input().split()))
c.sort(reverse=True)
dist = bfs()
idist = [(i, dist[i]) for i in range(N)]
idist.sort(key=lambda t: t[1])
ans = [-1]*N

for i in range(N):
    ans[idist[i][0]] = c[i]

print(sum(c[1:]))
print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

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

C = list(map(int, input().split()))
C.sort(reverse=True)
nodes = [0] * N

#print(nodes)
cidx = -1
ans = []
def dfs(v, pv, w):
    global cidx
    cidx += 1
    nodes[v] = C[cidx]
    ans.append(min(w, C[cidx]))
    for nv in edge[v]:
        if pv == nv: continue
        dfs(nv, v, C[cidx])

dfs(0, 0, 0)
print(sum(ans))
print(*nodes, sep=" ")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

N = int(input())
edge = [[] for _ in range(N)]
cnt = [[0,i] for i in range(N)]

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


cnt.sort(reverse=True)
start = cnt[0][1]
C = list(map(int, input().split()))
C.sort(reverse=True)
nodes = [0] * N

#print(nodes)
cidx = -1
ans = []
def dfs(v, pv, w):
    global cidx
    cidx += 1
    nodes[v] = C[cidx]
    ans.append(min(w, C[cidx]))
    for nv in edge[v]:
        if pv == nv: continue
        dfs(nv, v, C[cidx])

dfs(start, 0, 0)
print(sum(ans))
print(*nodes, sep=" ")

Submission status: Accepted

Solution code:
N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
C = sorted(list(map(int, input().split())))
M = sum(C[:-1])
import sys
sys.setrecursionlimit(10**8)

def dfs(v):
  for u in edge[v]:
    if nums[u]==-1:
      nums[u]=C.pop(-1)
      dfs(u)
  return 0

nums = [-1]*N
nums[0] = C.pop(-1)
dfs(0)

print(M)
print(*nums)

Submission status: Accepted

Solution code:
import heapq
import sys
sys.setrecursionlimit(10**7)
n = int(input())
g = [[] for _ 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 = [-i for i in list(map(int,input().split()))]
heapq.heapify(c)
print(-sum(c)+min(c))

for i in range(n):
    if len(g[i]) == 1:
        start = i
        break

ans = [-1]*n
ans[start] = -heapq.heappop(c)
q = [start]

while q:
    now = q.pop(-1)
    for i in g[now]:
        if ans[i] == -1:
            ans[i] = -heapq.heappop(c)
            q.append(i)

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
n=int(input())
e=[[]for i in range(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,Q,l,i=sorted(list(map(int,input().split())))[::-1],[0],[0]*n,0
print(sum(c[1:]))
while Q:
 a=Q.pop()
 if l[a]!=0:continue
 l[a]=c[i];i+=1
 for j in e[a]:Q.append(j)
print(*l)

Submission status: Accepted

Solution code:
from collections import deque


def nearlist(N, LIST):  # 隣接リスト
    NEAR = [set() for _ in range(N)]
    for a, b in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
    return NEAR


def bfs(NEAR, S):  # 幅優先探索  # キュー
    ans[S] = c.pop()
    que, frag = deque([S]), set([S])

    while len(que) > 0:
        q = que.popleft()
        for i in NEAR[q]:  # 移動先の候補
            if i in frag:  # 処理済みか否か
                continue
            ans[i] = c.pop()
            que.append(i), frag.add(i)
    return ans


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

ans = [0] * n
near = nearlist(n, ab)
print(sum(c) - max(c))
print(*bfs(near, 0))

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    e = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = ns()
        a, b = a - 1, b - 1
        e[a].append(b)
        e[b].append(a)

    c = na()
    c.sort(reverse=True)
    cost = collections.deque(c)

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

    que = collections.deque(e[0])
    notvisited[0] = False
    ans[0] = cost.popleft()

    while que:
        for _ in range(len(que)):
            q = que.popleft()
            if notvisited[q]:
                ans[q] = cost.popleft()
                notvisited[q] = False
                for ei in e[q]:
                    que.append(ei)

    res = 0
    for i in range(n):
        for ei in e[i]:
            if i < ei:
                res += min(ans[i], ans[ei])

    print(res)
    print(*ans, sep=" ")


if __name__ == '__main__':
    main()