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:
from collections import defaultdict

V = defaultdict(list)
N = int(input())
for _ in range(N-1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)
*c, = map(int, input().split())
c.sort(reverse=True)

root, _ = max(V.items(), key=lambda x:len(x[1]))
visited = [False] * (N+1)
identifier = [0] * (N+1)

p = 0
q = [root]
while q:
    a = q.pop()
    visited[a] = True
    identifier[a] = p

    p+=1

    for i in V[a]:
        if visited[i]:continue
        q.append(i)

cost = 0
visited = [False] * (N+1)
q = [root]
while q:
    a = q.pop()
    visited[a] = True
    p+=1

    for b in V[a]:
        if visited[b]:continue
        cost += min(c[identifier[a]], c[identifier[b]])
        q.append(b)

print(cost)
print(*[c[i] for i in identifier[1:]])

Submission status: Accepted

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    def bfs(n, e, fordfs, C):
        # 点の数、スタートの点、有向グラフ
        W = [-1] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        i = 0
        W[e] = C[i]
        i += 1
        que = deque()
        que.append(e)
        while que and i<n:
            now = que.popleft()
            for ne in fordfs[now]:
                if W[ne] == -1:
                    W[ne] = C[i]
                    i += 1
                    que.append(ne)
        return W
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        A, B = LI()
        V[A-1].append(B-1)
        V[B-1].append(A-1)
    C = LI(); C.sort(reverse=True)
    e = 0
    ans = bfs(N,e,V,C)
    print(sum(ans)-C[0])
    print(" ".join(map(str,ans)))
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
g=[set() for i in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  g[a].add(b)
  g[b].add(a)
c=list(map(int,input().split()))
c.sort(reverse=True)
print(sum(c)-c[0])
q=deque()
nums=[0]*(n+1)
q.appendleft(1)
while q:
  d=q.popleft()
  nums[d]=c.pop(0)
  for node in g[d]:
    if nums[node]==0:
      q.append(node)
print(*nums[1:])

Submission status: Accepted

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
edges = [set() for _ in range(N+1)] # 1-indexed
for _ in range(N-1):
    a, b = lr()
    edges[a].add(b)
    edges[b].add(a)
    
C = lr()
C.sort(reverse=True)
degrees = [len(x) for x in edges]
deg_1 = [i for i, d in enumerate(degrees) if d == 1]
score = sum(C[1:])
answer = [None] * (N+1)

# start from every leaf
while deg_1:
    leaf = deg_1.pop()
    answer[leaf] = C.pop()
    if not deg_1:
        break
    cand = edges[leaf].pop()
    edges[cand].remove(leaf)
    degrees[cand] -= 1
    if degrees[cand] == 1:
        deg_1.append(cand)

print(score)
print(*answer[1:])

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n=int(input())
ab=[list(map(int,input().split())) for i in range(n-1)]
c=list(map(int,input().split()))
c.sort()
print(sum(c)-c[-1])
lst=[[] for i in range(n)]
nodelst=[0]*n
ans=0
for i in range(n-1):
    a,b=ab[i]
    lst[a-1].append(b)
    lst[b-1].append(a)

# print(lst)
nodelst[0]=c[-1]
d=deque(lst[0])
cnt=-2
while d:
    tmp=d.popleft()-1
    if nodelst[tmp]==0:
        nodelst[tmp]=c[cnt]
        cnt-=1
        d+=lst[tmp]
print(*nodelst)

Submission status: Accepted

Solution code:
from collections import *
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
C=list(map(int,input().split()))
C.sort(reverse=True)
data=[[] for i in range(N+1)]
num=[-1 for i in range(N+1)]
num[1]=C[0]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)
sumc=sum(C[1:])

stack=[1]
stack=deque(stack)
visited=set()
visited.add(1)
idx=1
while stack:
    a=stack.popleft()
    for p in data[a]:
        if not p in visited:
            visited.add(p)
            num[p]=C[idx]
            idx+=1
            stack.append(p)
print(sumc)
print(" ".join([str(num[i]) for i in range(1,N+1)]))

Submission status: Accepted

Solution code:
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
C=list(map(int,input().split()))
C.sort(reverse=True)
data=[[] for i in range(N+1)]
num=[-1 for i in range(N+1)]
num[1]=C[0]
for a,b in AB:
    data[a].append(b)
    data[b].append(a)
sumc=sum(C[1:])

stack=[1]
visited=set()
visited.add(1)
idx=1
while stack:
    a=stack.pop()
    for p in data[a]:
        if not p in visited:
            visited.add(p)
            num[p]=C[idx]
            idx+=1
            stack.append(p)
print(sumc)
print(" ".join([str(num[i]) for i in range(1,N+1)]))

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
c = list(map(int,input().split()))
c.sort(reverse=True)
graph = [[] for i in range(n+1)]
parent = [0 for i in range(n+1)]
root = 1
order = []
que = deque([root])
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
while que:
  x = que.popleft()
  order.append(x)
  for y in graph[x]:
    if parent[x] == y:
      continue
    parent[y] = x
    que.append(y)
ans = []
for i in range(n):
  ans.append((order[i],c[i]))
ans.sort()
print(sum(c[1:]))
for i in ans:
  print(i[1],end=" ")

Submission status: Accepted

Solution code:
N=int(input())

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

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

num=[0 for i in range(N+1)]
un_used=[True for i in range(N+1)]

q=[]
q.append(1)
un_used[1]=False

while q:
    node = q.pop(0)
    num[node] = C.pop(0)
    
    for i in range(len(G[node])):
        if un_used[G[node][i]]:
            un_used[G[node][i]]=False
            q.append(G[node][i])

print(S)
print(" ".join(map(str,num[1:])))

Submission status: Accepted

Solution code:
N=int(input())
E=[[] for _ in range(N)]
for _ 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(reverse=True)

ans=[0]*(N)
stack=[0]
ans[0]=C[0]
k=1
while stack:
    n=stack.pop()
    for to in E[n]:
        if ans[to]!=0: continue
        ans[to]=C[k]
        k+=1
        stack.append(to)

print(sum(C[1:]))
print(' '.join(map(str,ans)))

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
tree = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    tree[a].append(b)
    tree[b].append(a)
C = list(map(int, input().split()))
C.sort(reverse=True)
q = deque([0])
visited = [False] * N
ans = {}
ans[0] = C[0]
visited[0] = True
pointa = 1
while len(q):
    v = q.pop()
    for e in tree[v]:
        if visited[e]:
            continue
        visited[e] = True
        ans[e] = C[pointa]
        pointa += 1
        q.append(e)
num = []
for i in range(N):
    num.append(str(ans[i]))
print(sum(C[1:]))
print(" ".join(num))

Submission status: Accepted

Solution code:
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
import heapq
# https://atcoder.jp/contests/agc033/tasks/agc033_b
# B - LRUD Game
"""
"""
N = gi()
t = [[] for i in range(N + 5)]

for i in range(1, N):
    a = gi()
    b = gi()
    t[a].append(b)
    t[b].append(a)
cs = [0] * N
for i in range(N):
    cs[i] = gi()
cs.sort()
print(sum(cs) - max(cs))
vs = [0] * (N + 5)
ci = N - 1
q = deque()
q.append(1)

while len(q):
    v = q.pop()
    # print(v, ci)
    vs[v] = cs[ci]
    ci -= 1
    for u in t[v]:
        if vs[u]:
            continue
        else:
            q.append(u)
for i in range(1, N + 1):
    print("%d " % (vs[i]), end="")

Submission status: Accepted

Solution code:
from heapq import heapify, heappop
N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N - 1)]
C = list(map(int, input().split()))

M = sum(C) - max(C)

nl = [list() for i in range(N)]
for a, b in AB:
    nl[a - 1].append(b - 1)
    nl[b - 1].append(a - 1)

v0 = -1
mlen = 0
for i, n in enumerate(nl):
    if len(n) > mlen:
        mlen = len(n)
        v0 = i

q = [-c for c in C]
heapify(q)
ans = [0] * N
stack = [(v0, -1)]
while len(stack) > 0:
    v, p = stack.pop()
    c = heappop(q)
    ans[v] = -c
    for next_v in nl[v]:
        if next_v != p:
            stack.append((next_v, v))
print(M)
print(*ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10 ** 7)

    def dfs(v):
        nonlocal curr

        num[v] = 0  # 0: visited, but not written yet

        for u in g[v]:
            if num[u] >= 0:
                continue
            dfs(u)
        num[v] = c[curr]
        curr += 1

    n = int(input())

    g = [set() for _ in range(n)]
    for _ in range(n - 1):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(b)
        g[b].add(a)
        # 出次数は、len(g[x])-1
        # 親を除いた残りが子
    *c, = sorted(map(int, input().split()))

    num = [-1] * n
    curr = 0
    dfs(0)

    print(sum(c[:-1]))
    print(*num)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N = int(input())
graph = [[] for _ in range(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 = False)

tmp = len(graph[0])
start = 0
for index, x in enumerate(graph):
    if len(x) > tmp:
        tmp = len(x)
        start = index

ans = 0
ans_lst = [-1] * N
ans_lst[start] = c.pop()
stack = [start]
while stack:
    x = stack.pop()
    for next_ in graph[x]:
        if ans_lst[next_] == -1:
            tmp = c.pop()
            ans_lst[next_] = tmp
            stack.append(next_)
            ans += tmp

print (ans)
print (*ans_lst, sep = ' ')

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
C = sorted(list(map(int,input().split())))
A = [0 for _ in range(N+1)]
hist = [0 for _ in range(N+1)]
que = deque([1])
hist[1] = 1
cur = 0
while que:
    i = que[-1]
    if len(G[i])==1:
        A[i] = C[cur]
        cur += 1
        hist[i] = 2
        que.pop()
    flag = 2
    for j in G[i]:
        if hist[j]==0:
            que.append(j)
            hist[j] = 1
            flag = 1
    if flag==2 and hist[i]==1:
        A[i] = C[cur]
        cur += 1
        hist[i] = 2
        que.pop()
cnt = 0
hist = {(i,j):0 for i in range(1,N+1) for j in G[i]}
for i in range(1,N+1):
    for j in G[i]:
        if hist[(i,j)]==0:
            cnt += min(A[i],A[j])
            hist[(i,j)] = 1
            hist[(j,i)] = 1
print(cnt)
print(*A[1:])

Submission status: Accepted

Solution code:
import sys
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
nodes = [set() for _ in range(N+1)]

for _ in range(N-1):
    a, b = rl()
    nodes[a].add(b)
    nodes[b].add(a)

C = rl()
C.sort(reverse=True)
score = sum(C[1:])
deg = [len(x) for x in nodes]
deg_1 = [i for i, x in enumerate(deg) if x == 1]
answer = [0] * (N+1)

while deg_1:
    v = deg_1.pop()
    if not deg_1:
        answer[v] = C.pop()
        break
    w = nodes[v].pop()
    nodes[w].remove(v)
    deg[w] -= 1
    if deg[w] == 1:
        deg_1.append(w)
    answer[v] = C.pop()

print(score)
print(*answer[1:])

Submission status: Accepted

Solution code:
import sys

N=int(input())
ab=[list(map(int,input().split())) for i in range(N-1)]
c=list(map(int,input().split()))
c.sort(reverse=True)
data=[[] for i in range(N+1)]
for a,b in ab:
    data[a].append(b)
    data[b].append(a)
    
flag=[0]*(N+1)
ans=[0]*(N+1)
flag[1]=1
k=0
que=[1]
while que:
    for u in que:
        ans[u]=c[k]
        k+=1
    if k>N:
        break
    h=[]
    for u in que:
        for v in data[u]:
            if flag[v]==0:
                flag[v]=1
                h.append(v)
    que=h
print(sum(ans[2:]))
print(*ans[1:])

Submission status: Accepted

Solution code:
from collections import deque

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

C.sort()
C = C[::-1]

graph = [[] for _ in range(N + 1)]
check = [1] * (N + 1)
for A, B in AB:
  graph[A].append(B)
  graph[B].append(A)

answer = [0] * (N + 1)
stack = deque()
stack.append(1)
check[1] = 0
ci = 0

while stack:
  s = stack.popleft()
  answer[s] = C[ci]
  ci += 1
  for g in graph[s]:
    if check[g]:
      check[g] = 0
      stack.append(g)
      
print(sum(C) - max(C))
print(*answer[1:])

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
G = {k: [] for k in range(N)}
E = [0]*N
ans = [-1]*N

for _ in range(N-1):
    a, b = map(int, input().split())
    # 無向グラフ
    G[a-1].append(b-1)
    G[b-1].append(a-1)

    E[a-1] += 1
    E[b-1] += 1

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


ans[E.index(max(E))] = C[0]
que = deque([(E.index(max(E)), -1)])

idx = 0
while que:
    ci, p = que.popleft()

    for ni in G[ci]:
        if ni != p:
            idx += 1
            ans[ni] = C[idx]
            que.append((ni, ci))

print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
graph = [[] for _ in range(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()
score = sum(c)-c[-1]

for i in range(n):
    if len(graph[i]) == 1:
        next_v = deque([i])
        break
# dfs
ans = [-1]*n
while next_v:
    v = next_v.popleft()
    ans[v] = c.pop()
    for i in graph[v]:
        if ans[i] != -1:
            continue
        next_v.append(i)

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

Submission status: Accepted

Solution code:
# maximum sum of minimum
n=int(input())
node={i:[]for i in range(n+1)}
visited=[False for i in range(n+1)]

#尋ねたことがあるかどうか確認するためのリスト
first=0

for _ in range(n-1):
    a,b=map(int,input().split())
    node[a].append(b)
    node[b].append(a)
    if _==0:
        first+=a
        

dictionary=[0 for i in range(n+1)]
#答を格納するためのリスト
clist=list(map(int,input().split()))
clist=sorted(clist,reverse=True)
counter=0
dictionary[first]=clist[0]
K=sum(clist[1:])
from collections import deque
d=deque()
e=deque()
d.append(first)
visited[first]=True
while d:
    for some in d:
        for point in node[some]:
            if visited[point]==False:
                #まだ訪れたことのない頂点にあった場合
                counter+=1
                visited[point]=True
                dictionary[point]=clist[counter]
                e.append(point)
            else:
                pass
    d=e
    e=deque()
print(K)
print(*dictionary[1:])

Submission status: Accepted

Solution code:
#%%
n = int(input())
a, b = [0] * (n-1), [0] * (n-1)
reach = [[] for _ in range(n)]
for i in range(n-1):
    a[i], b[i] = map(int, input().split())
    reach[a[i]-1].append(b[i]-1)
    reach[b[i]-1].append(a[i]-1)
c = list(map(int, input().split()))
c.sort(reverse=True)
ans_list = [0] * n
check = [0] * n

stack = [0]
j = 0

while len(stack) > 0: 
    tmp = stack.pop(-1)
    check[tmp] = 1
    ans_list[tmp] = str(c[j])
    j += 1
    for i in range(len(reach[tmp])):
        if check[reach[tmp][i]] == 0:
            stack.append(reach[tmp][i])
        else:
            pass
    
print(sum(c) - max(c))
print(' '.join(ans_list))

Submission status: Accepted

Solution code:
N = int(input())
import collections

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

Cs = sorted(map(int, input().split()))
print(sum(Cs) - max(Cs))

sw = [-1] * N
stk = collections.deque([0])
while len(stk) > 0:
    crN = stk.popleft()
    if sw[crN] < 0:
        sw[crN] = Cs.pop()
        for l in Ls[crN]:
            stk.append(l)

print(*sw)

Submission status: Accepted

Solution code:
N = int(input())
import collections

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

Cs = sorted(map(int, input().split()), reverse=True)
print(sum(Cs) - Cs[0])

sw = [-1] * N
sw[0] = Cs[0]
ct = 1
stk = collections.deque()
stk.appendleft(0)
while len(stk) > 0:
    crN = stk[0]
    if len(Ls[crN]) == 0:
        stk.popleft()
        continue
    nxN = Ls[crN].popleft()
    if sw[nxN] > 0:
        continue
    sw[nxN] = Cs[ct]
    ct += 1
    stk.append(nxN)
print(" ".join(map(str, sw)))

Submission status: Accepted

Solution code:
N = int(input())
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
c = list(map(int,input().split()))
c.sort()
ans = sum(c) - max(c)
F = []
for i in range(1,N+1):
    n = len(G[i])
    if n == 1:
        F.append(i)
d = {}
i = 0
while i < N:
    x = F.pop(0)
    d[x] = c[i]
    i += 1
    if len(G[x]) > 0:
        y = G[x][0]
        G[y].remove(x)
        if len(G[y]) == 1:
            F.append(y)
ANS = []
for i in range(1,N+1):
    ANS.append(d[i])
print(ans)
print(*ANS)

Submission status: Accepted

Solution code:
import sys
import collections
input = sys.stdin.readline
N = int(input())
edge = [list(map(int,input().split())) for _ in range(N-1)]
c = sorted(list(map(int,input().split())),reverse=True)
graph = [[] for _ in range(N)]
ans = [-1 for _ in range(N)]
queue = collections.deque()

for e in edge:
    graph[e[0]-1].append(e[1]-1)
    graph[e[1]-1].append(e[0]-1)

for i in range(N):
    if len(graph[i])==1:
        queue.append(i)
        ans[i] = c[0]
        break
k=1
while queue:
    node = queue.popleft()
    for adj in graph[node]:
        if ans[adj]==-1:
            ans[adj] = c[k]
            k += 1
            queue.append(adj)
            
print(sum(c)-max(c))
print(*ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[[]for i in range(n+1)]
for i in range(n-1):
    b,c=map(int,input().split())
    a[b].append(c)
    a[c].append(b)
b=[1]
c=[1]
l=[0]*(n+1)
l[1]=1
while len(b)>0:
    d=[]
    for i in b:
        for j in a[i]:
            if l[j]==0:
                d.append(j)
                c.append(j)
                l[j]=1
    b=d[:]
c=c[::-1]
e=sorted(list(map(int,input().split())))
b=[0]*n
for i in range(n):
    b[c[i]-1]=e[i]
print(sum(e[:-1]))
print(*b)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque as dq
input = sys.stdin.readline
N = int(input())
e = dd(list)
if N == 1:
  print(0)
  print(1)
  exit(0)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
res = [0] * (N + 1)
x = list(map(int, input().split()))
x.sort()
print(sum(x[: -1]))
p = 0
dimp = 0
for i in range(N + 1):
  if len(e[i]) > dimp:
    p = i
    dimp = len(e[i])
Q = dq([])
Q.append(p)
vis = set()
while len(Q):
  q = Q.popleft()
  y = x.pop()
  vis.add(q)
  res[q] = y
  for n in e[q]:
    if n in vis: continue
    Q.append(n)

print(" ".join(list(map(str, res[1: ]))))

Submission status: Accepted

Solution code:
def examD():
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        A, B = LI()
        V[A-1].append(B-1)
        V[B-1].append(A-1)
    C = LI(); C.sort()
    e = 0
    low = 0; up = N-1
    ans = 0; W = [-1] * N
    # 各点の値
    W[e] = C[up]; up -=1
    que = deque()
    que.append(e)
    while que or low<up:
        now = que.popleft()
        if len(V[now])==1 and now!=0:
            W[now] = C[low]
            ans += W[now]
            low +=1
        elif now!=0:
            W[now] = C[up]
            up -= 1
            ans += W[now]
        for ne in V[now]:
            if W[ne] == -1:
                que.append(ne)
    print(ans)
    print(" ".join(map(str,W)))

from string import digits
import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
ab = [list(map(int, input().split())) for i in range(n-1)]
c = sorted(list(map(int, input().split())), reverse = True)
tree = [list() for i in range(n)]
already = [1] * n 
ans = [0] * n
k = 0
queue = deque([0])

for index,(a,b) in enumerate(ab):
  a -= 1
  b -= 1
  tree[a].append((index,b))
  tree[b].append((index,a))
while queue:
  now = queue.popleft()
  already[now] = 0
  ans[now] = c[k]
  k += 1
  for index,i in tree[now]:
    if already[i]:
      queue.append(i)
         
print(sum(c[1:]))
print(*ans)

Submission status: Accepted

Solution code:
import heapq
import sys
sys.setrecursionlimit(20000)
N = int(input())
ab = [tuple(map(int, input().split())) for i in range(N-1)]
c = list(map(int, input().split()))

print(sum(c) - max(c))
c = list(map(lambda x: x*(-1), c))
heapq.heapify(c)
d = [[0, i] for i in range(N)]
g = [set() for i in range(N)]
for a, b in ab:
    d[a-1][0] += 1
    d[b-1][0] += 1
    g[a-1].add(b-1)
    g[b-1].add(a-1)
d.sort(reverse=True, key=lambda x: x[0])
for i in range(N):
    d[i][0] = -1


ans = ["-1"]*N
ans[d[0][1]] = str(-1 * heapq.heappop(c))


def dfs(start):
    for x in g[start]:
        if ans[x] == "-1":
            ans[x] = str(-1 * heapq.heappop(c))
            dfs(x)


dfs(d[0][1])
d.sort(key=lambda x: x[1])


print(" ".join(ans))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



n = I()
G = [[] for _ in range(n)]
for a, b in LIR(n - 1):
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


C = sorted(LI())
ans = [0] * n
ans[0] = C.pop()
total = sum(C)
dq = deque([0])
while dq:
    u = dq.popleft()
    for v in G[u]:
        if not ans[v]:
            ans[v] = C.pop()
            dq += [v]


print(total)
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
g = [set() for i in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    g[a].add(b)
    g[b].add(a)
    
c = list(map(int, input().split()))
c.sort(reverse=True)

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

q = deque()
nums = [0] * (N + 1)

q.appendleft(1)

while q:
  d = q.popleft()
  nums[d] = c.pop(0)
  for node in g[d]:
    if nums[node] == 0:
      q.append(node)
print(*nums[1:])

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
g = [set() for i in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    g[a].add(b)
    g[b].add(a)
    
c = list(map(int, input().split()))
c.sort(reverse=True)

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

q = deque()
nums = [0] * (N + 1)

q.appendleft(1)

while q:
  d = q.popleft()
  nums[d] = c.pop(0)
  for node in g[d]:
    if nums[node] == 0:
      q.appendleft(node)
print(*nums[1:])

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
ans=[0 for i in range(n)]
l=[[] for i in range(n+1)]
for i in range(n-1):
  a,b=map(int,input().split())
  l[a].append(b)
  l[b].append(a)
l1=sorted(list(map(int,input().split())))
l1=l1[::-1]
sum=0
for i in range(1,n):
  sum+=l1[i]
q=deque(l1)
q1=deque([[1]])
while q:
  l2=q1.popleft()
  for i in l2:
    if ans[i-1]!=0:
      pass
    else:
      n2=q.popleft()
      ans[i-1]=n2
      q1.append(l[i])
print(sum)
answ=""
for i in range(n):
  answ+=str(ans[i])+" "
print(answ)

Submission status: Accepted

Solution code:
def main():

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

    max_l = 0
    max_i = -1
    for i in range(N):
        if len(count[i]) > max_l:
            max_l = len(count[i])
            max_i = i

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

    cur = [max_i]
    val = [0 for _ in range(N)]
    i = 0
    val[max_i] = c[i]
    i += 1
    ans = 0
    while cur:
        temp = []
        for j in cur:
            for k in count[j]:
                if val[k] == 0:
                    val[k] = c[i]
                    ans += c[i]
                    i += 1
                    temp.append(k)
        cur = temp

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    ab=[list(map(int,input().split())) for _ in [0]*(n-1)]
    c=sorted(list(map(int,input().split())),reverse=True)
    g=[set() for _ in [0]*n]
    [g[a-1].add(b-1) for a,b in ab]
    [g[b-1].add(a-1) for a,b in ab]
    l=[]
    print(sum(c)-max(c))
    for i in range(n):
        if len(g[i])==1:
            l.append(i)
    ans_l=[0]*n
    while l:
        i=l.pop()
        ans_l[i]=c.pop()
        for j in g[i]:
            g[j].remove(i)
            if len(g[j])==1:
                l.append(j)
        g[i]=set()
    print(*ans_l)
main()

Submission status: Accepted

Solution code:
n, *L = map(int, open(0).read().split())
ab = L[:2 * n - 2]
c = sorted(L[2 * n - 2:])
con = [[] for _ in range(n)]
ans = [0] * n
tot = sum(c) - max(c)
for a, b in zip(*[iter(ab)] * 2):
	con[a - 1].append(b - 1)
	con[b - 1].append(a - 1)
vis = [0] * n
q = [0]
vis[0] = 1
while q:
	cur = q.pop()
	ans[cur] = c.pop()
	for nxt in con[cur]:
		if vis[nxt]:
			continue
		q.append(nxt)
		vis[nxt] = 1
print(tot)
print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
edge=[set() for i in range(n+1)]
for i in range(n-1):
    a,b=[int(j) for j in input().split()]
    edge[a].add(b)
    edge[b].add(a)

c=[int(j) for j in input().split()]
d=[len(i) for i in edge]

d1=[i for i,x in enumerate(d) if x==1]

ans=[None]*(n+1)
c.sort()
c.reverse()
m=sum(c)-c[0]

while d1:
    v=d1.pop()
    if not d1:
        ans[v]=c.pop()
        break
    w=edge[v].pop()
    edge[w].remove(v)
    d[w]-=1
    if d[w]==1:
        d1.append(w)
    ans[v]=c.pop()

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

Submission status: Accepted

Solution code:
n = int(input())
edge = [ [ int(v)-1 for v in input().split() ] for i in range(n-1) ]
num_list = sorted([ int(v) for v in input().split() ])
parent_list = [ None for i in range(n) ]
connect_list = [ [] for i in range(n) ]

for a, b in edge:
    connect_list[a].append(b)
    connect_list[b].append(a)

connect_point = [ len(i) for i in connect_list ]
p = connect_point.index(max(connect_point))

depth_list = [[p]]
search_list = [p]
parent_list[p] = -1

while search_list:
    new_search_list = []
    for i in search_list:
        for j in connect_list[i]:
            if parent_list[j] is None:
                parent_list[j] = i
                new_search_list.append(j)
    if new_search_list:
        depth_list.append(new_search_list)
    search_list = new_search_list

node = [ None for i in range(n) ]
q = 0

for i in depth_list[::-1]:
    for j in i:
        node[j] = num_list[q]
        q += 1

print(sum(num_list[:-1]))
print(*node)