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:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

prepare=[]
n=I()
tree=[[] for i in range(n)]
for i in range(n-1):
    a,b=MI()
    a-=1
    b-=1
    prepare.append([a,b])
    tree[a].append(b)
    tree[b].append(a)
lis=sorted(LI(),reverse=True)
answers=[0 for i in range(n)]
Q=deque([0])
answers[0]=lis[0]
count=1
while Q:
    q=Q.popleft()
    for x in tree[q]:
        if answers[x]==0:
            answers[x]=lis[count]
            Q.append(x)
            count+=1
#print(answers)
ans=0
for i in range(n-1):
    ans+=min(answers[prepare[i][0]],answers[prepare[i][1]])
print(ans)
print(*answers)

Submission status: Accepted

Solution code:
from collections import deque

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

C = list(map(int, input().split()))
C.sort()
ans = sum(C[:-1])
dep = [-1] * N
dep[0] = C.pop()
d = deque([[0, -1]])
while d:
  node, par = d.popleft()
  children = tree[node]
  for child in children:
    if child == par:
      continue
    dep[child] = C.pop()
    d.append([child, node])

print(ans)
print(*dep)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

def build_tree(N, edge_list):

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

    for i in range(len(edge_list)):
        a, b = edge_list[i]
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    # 葉（末端の数）
    leaves = []
    for i in range(N):
        if len(G[i]) == 1:
            leaves.append(i)

    return G, leaves

N = getN()
query = [[] for i in range(N - 1)]
for i in range(N - 1):
    query[i] = getList()

d = list(sorted(getList()))

edges, leaves = build_tree(N, query)

v = leaves[0]

# 最も理想的な場合のsum = d[0] + d[1] + ... + d[-2]
ans = -d[-1]
nodes = [0] * N

# 葉の先端から辿っていく
def dfs(now):
    global ans
    if nodes[now] > 0:
        return
    nodes[now] = d.pop()
    ans += nodes[now]
    for i in edges[now]:
        if nodes[i] > 0:
            continue
        dfs(i)

dfs(v)
print(ans)
print(*nodes)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify, heappop, heappush
N = int(input())
edge = [[] for _ in range(N)]
ID = set([i for i in range(N-1)])
popular = [0 for _ in range(N)] #繋がっている頂点の数
#ID = set(ID)
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1 #0index
  edge[a].append(b) #相手方の点と道のIndexを保存
  edge[b].append(a)
  popular[a] += 1;popular[b] += 1
#print(edge)

Q = []
C = list(map(int,input().split()))
C.sort(reverse = True)
ans = sum(C) - max(C)
print(ans)
#for i in range(N):
#  temp,point = heappop(P)
#  heappush(Q,(C[i],point))
#print(Q)
#while Q:
#  X = heappop(Q)
#  print(X)
Q = deque([])
Q.append(0)
R = [-1 for _ in range(N)]
num = -1
v = 0
reach = set([])
while Q:
  v = Q.popleft() #頂点とID
  if v in reach:
    continue
  reach.add(v)
  num += 1
  #print(v,num)
  R[v] = C[num]
  for u in edge[v]:
    Q.append(u)

#print(ans)
print(*R)

Submission status: Accepted

Solution code:
#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G
from collections import deque
def bfs(v, p):
    q = deque()
    q.append((v, p))
    rec[v - 1] = c.pop()
    while c:
        V, P = q.popleft()
        for nv in G[V - 1]:
            if nv == P:continue
            rec[nv - 1] = c.pop()
            q.append((nv, V))

n = int(input())
ab = [list(map(int, input().split())) for i in range(n - 1)]
c = list(map(int, input().split()))
c.sort()
G = Graph(ab)
print(sum(c[:-1]))
rec = [0] * n
bfs(1, -1)
print(*rec)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    N = int(input())
    edge = [[] for _ 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()))
    C.sort(reverse=True)
    ans = [0] * N
    Q = deque([0])
    cnt = 0
    ans[0] = C[0]
    while Q:
        s = Q.pop()
        for v in edge[s]:
            if ans[v]:
                continue
            cnt += 1
            ans[v] = C[cnt]
            Q.append(v)

    print(sum(C) - max(C))
    print(*ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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


def DFS(num,pre):
    global point
    if color[num]=="white":
        ans[num]=C.pop()
        point +=min(ans[num],pre)
        color[num]="black"
        for i in T[num]:
            DFS(i,ans[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)]

T=[[] for _ in range(n)]
for a,b in AB:
    T[a-1].append(b-1)
    T[b-1].append(a-1)

ans=[0 for _ in range(n)]
point=0
DFS(0,0)

print(point)
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())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
c = list(map(int, input().split()))
c.sort(reverse=True)
ans = [None]*n
ans[0] = c[0]
q = deque([0])
i = 1
while q:
    node = q.popleft()
    for c_node in graph[node]:
        if ans[c_node] is not None:
            continue
        ans[c_node] = c[i]
        i += 1
        q.append(c_node)
print(sum(c)-c[0])
print(*ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

N = int(input())
X = defaultdict(list)
for i in range(N - 1):
    ai, bi = map(lambda s: int(s) - 1, input().split())
    X[ai].append(bi)
    X[bi].append(ai)
c = list(map(int, input().split()))

c.sort(reverse=True)
print(sum(c[1:]))
d = [0] * N
q = deque([0])
i = 0
while len(q) > 0:
    v = q.popleft()
    d[v] = c[i]
    i += 1
    for x in X[v]:
        if d[x] != 0:
            continue
        q.append(x)
print(' '.join(list(map(str, d))))

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict,deque
N = int(stdin.readline().rstrip())
adj = defaultdict(set)

for i in range(N-1):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]
    adj[a].add(b)
    adj[b].add(a)
    
C = [int(x) for x in stdin.readline().rstrip().split()]

ans = sum(C) - max(C)
print(ans)

visit_p = deque()
visit_p.append(1)
visited = [False]*(N+1)
visited[1] = True

C.sort(reverse=True)
 
print(C[0],end=" ")
cnt = 1
ans_lst = [0]*(N+1)
while visit_p:
    now_v = visit_p.popleft()
    for v in adj[now_v]:
        if visited[v]:
            continue
        ans_lst[v] = C[cnt]
        cnt += 1
        visited[v] = True
        visit_p.append(v)
for i in ans_lst[2:]:
    print(i,end=" ")

Submission status: Accepted

Solution code:
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 = [int(i) for i in input().split()]
c.sort()
c.reverse()
ans_list = [0 for _ in range(n)]
ans = 0
p_list = [0]
ans_list[0] = c.pop(0)
while len(p_list) > 0:
    p = p_list.pop(0)
    for g in graph[p]:
        if ans_list[g] == 0:
            ans_list[g] = c.pop(0)
            ans += ans_list[g]
            p_list.append(g)
print(ans)
print(' '.join([str(i) for i in ans_list]))

Submission status: Accepted

Solution code:
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
cl = list(map(int, input().split()))
cl.sort(reverse=True)

e = [set() for _ in range(n)]
for a,b in ab:
    a -= 1
    b -= 1
    e[a].add(b)
    e[b].add(a)

used = [False]*n
q = [0]

res = [0]*n
i = 0
while len(q)>0:
    u = q.pop()
    res[u] = cl[i]
    used[u] = True
    i += 1
    for v in e[u]:
        if not used[v]:
            q.append(v)

r = 0
for a,b in ab:
    r += min(res[a-1], res[b-1])
print(r)
print(*res)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    way = [[] for _ in [0]*n]
    for i in [0]*(n-1):
        a,b = map(int,ipt().split())
        way[a-1].append(b-1)
        way[b-1].append(a-1)
    c = [int(i) for i in ipt().split()]
    c.sort(reverse=True)
    ans = [0]*n
    q = queue.Queue()
    ans[0] = c[0]
    ni = 1
    q.put(0)
    sum = 0
    while ni < n:
        qi = q.get()
        for i in way[qi]:
            if ans[i] == 0:
                ans[i] = c[ni]
                sum += c[ni]
                ni += 1
                q.put(i)

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



    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
edge=[[] for _ in range(N)]
for _ in range(N-1):
    a,b=map(int1,input().split())
    edge[a].append(b)
    edge[b].append(a)
C=list(map(int,input().split()))
C.sort()
print(sum(C)-C[-1])
que=deque([0])
ans=[-1]*N
while que:
    v=que.popleft()
    ans[v]=C.pop()
    for nv in edge[v]:
        if ans[nv]==-1:
            que.append(nv)
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
path = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path[a].append(b)
    path[b].append(a)
C = sorted(list(map(int,input().split())),reverse = True)
M = sum(C[1:])
ans = [-1]*n
que = deque([0])
i = 0
while que:
    p = que.popleft()
    ans[p] = C[i]
    i += 1
    for nxt in path[p]:
        if ans[nxt] >= 0:continue
        que.append(nxt)
print(M)
print(' '.join(str(i) for i in ans))

Submission status: Accepted

Solution code:
#M-SOLUTIONS プロコンオープン-D Maximum Sum of Minimum
"""
問題：
木が与えられる。
リストCが与えられるので、各頂点に割り当てる。
全ての辺において、その辺をつなぐ2頂点をa,bとした時、min(Ca,Cb)をスコアとする。
これを最大化するスコアを求め、そのような頂点への数値の割り振りを出力せよ。
考察：
シュミレーションしてみると、
1.辺数が多い頂点に大きい数字を割り当てると良さそう
2.複数あっても適当に選んで良い
3.大きい数字は隣り合ったほうが良い
4.よって、辺数が多い頂点をrootとして、そこから幅を優先して
大きい数字を順に割り当てるのが良さそう。
5.この時には別に子の辺数を気にする必要はない。(これは、その"子"がスコアとして使用
されるのは必ず1回であることから言える)
解法：
接続する辺が最も多い頂点をrootとして、幅優先でそこから大きい値を割り振っていく。
全ての子は必ず1回づつ使われるので、実はスコアの最大値は
all(C)-(rootの値)となる。
"""
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
g = [[] for _ in range(n)]
edges = [0]*n
for i in range(n-1):
    a,b = map(int,readline().split())
    a,b = a-1,b-1
    edges[a] += 1
    edges[b] += 1
    g[a].append(b)
    g[b].append(a)
C = list(map(int,readline().split()))
C.sort(reverse=True)
C = deque(C)
root = 0
res = 0
for i in range(n):
    if res < edges[i]:
        root = i
        res = edges[i]

ans = [-1]*n
ans[root] = C.popleft()
deq = deque([root])
while deq:
    fr = deq.popleft() #queue
    for go in g[fr]:
        if ans[go] != -1:
            continue
        ans[go] = C.popleft()
        deq.append(go)

print(sum(ans)-ans[root])
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
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()
M = sum(c)-c[-1]

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

seen = [False for i in range(N+1)]
seen[1] = True
score[1] = c.pop()
d = deque([1])
while len(d)>0:
  v = d.pop()
  for i in G[v]:
    if seen[i] == False:
      seen[i] = True
      score[i] = c.pop()
      d.append(i)
###
print(M)
print(*score[1:])

Submission status: Accepted

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

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

c = deque(sorted(list(map(int, input().split())), reverse=True))
visit = [-1 for _i in range(n)]
visit[0] = c.popleft()

def solve(p):
    r = 0
    for i in tree[p]:
        if visit[i] < 0:
            visit[i] = c.popleft()
            r += visit[i]
            r += solve(i)
    return r
x = solve(0)
print(x)
print(*visit)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n=int(input())
    graph=[[]for _ in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    C=list(map(int,input().split()))
    C.sort(reverse=True)#頂点の値が大きい順に
    node_c=[0]*n #各頂点の値 0なら初めて
    node_c[0]=C[0]
    queue=deque([0])
    i=1
    while queue:
        node=queue.popleft()
        for xnode in graph[node]:
            if node_c[xnode]>0:continue
            node_c[xnode]=C[i]
            i+=1
            queue.append(xnode)
    print(sum(C[1:]))
    print(' '.join(map(str,node_c)))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G

#BFS
from collections import deque
def bfs(G, v, p):
    point = [0] * n
    q=deque()
    q.append((v, p))
    point[0] = c.pop(0)

    score = 0
    while q:
        #qの先頭を取り出す
        V, P = q.popleft()
        for next_v in G[V - 1]:
            if next_v == P:continue
            q.append((next_v, V))
            temp = c.pop(0)
            score += temp
            point[next_v - 1] = temp

    return point, score

n = int(input())
ab = [list(map(int,input().split())) for i in range(n - 1)]
c = list(map(int,input().split()))
c = sorted(c, reverse=True)
G = Graph(ab)

point, score = bfs(G, 1, -1)
print(score)
print(*point)

Submission status: Accepted

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

from collections import deque

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

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

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

d = deque([0])
ans = [c[0]] + [0]*(N-1)
M = 0
c_idx = 1

while d:
    p = d.popleft()
    for n in neighbor[p]:
        if not ans[n]:
            ans[n] = c[c_idx]
            M += c[c_idx]
            c_idx += 1
            d.append(n)

print(M)
print(*ans)

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(lambda x:int(x)-1,input().split())
    T[a].append(b)
    T[b].append(a)
P = list(map(int,input().split()))
P.sort(reverse=True)
A = [-1]*N
v = -1
for i in range(N):
    if len(T[i])==1:
        v = i
        break
Q = deque([v])
p_index = 0
while Q:
    v = Q.pop()
    A[v] = P[p_index]
    p_index+=1
    for c in T[v]:
        if A[c]==-1:
            Q.append(c)
print(sum(P[1:]))
print(*A)

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
G=[[]for _ in range(N)]
cnt=[0]*N
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
    cnt[a]+=1
    cnt[b]+=1

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

root=0
v=0
for i in range(N):
    if v>cnt[i]:
        root=i
        v=cnt[i]

def bfs(s):
    que=deque()
    que.append(s)
    nodes=[-1]*N
    k=0
    ans=0
    while len(que)>0:
        q=que.pop()
        nodes[q]=C[k]
        k+=1

        for v in G[q]:
            if nodes[v]<0:
                que.append(v)
    print(sum(C[1:]))
    print(*nodes)

bfs(root)

Submission status: Accepted

Solution code:
from collections import deque
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 = [int(x) for x in input().split()]
c = sorted(c, reverse=True)

q = deque([0])
visited = [False]*n
ans = [-1]*n
ans[0] = c[0]
i = 1

while q:
    v = q.popleft()
    visited[v] = True
    for w in g[v]:
        if not visited[w]:
            ans[w] = c[i]
            i += 1
            q.append(w)

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

Submission status: Accepted

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

c.sort(reverse = True)
edges = [[] for _ in range(n)]
ans = [-1]*n
ans[0] = c[0]
count = 1

for a,b in ab:
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

q = [0]

while q:
    l = q.pop(-1)
    for l1 in edges[l]:
        if ans[l1] == -1:
            q.append(l1)
            ans[l1] = c[count]
            count += 1

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

Submission status: Accepted

Solution code:
from collections import Counter
from collections import deque
n = int(input())

counter = [0]*n
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)
  counter[a-1] += 1
  counter[b-1] += 1
  
C = sorted(list(map(int,input().split())))[::-1]


root = 0
v = 0
for i in range(n):
  if v > counter[i]:
    root = i
    v = counter[i]


def bfs(s):
  que = deque()
  que.append(s)
  nodes = [-1]*n
  k = 0
  ans = 0
  while len(que)>0:    
    q = que.pop()    
    nodes[q] = C[k]    
    k += 1
    
    for v in G[q]:
      if nodes[v]<0:
        que.append(v)
  
  print(sum(C[1:]))
  print(*nodes)                

bfs(root)

Submission status: Accepted

Solution code:
N = int(input())
cnt = dict()

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

for _ in range(N-1):
    a, b = [int(x) for x in input().split()]
    cnt[a-1] = cnt.get(a-1,0) + 1
    cnt[b-1] = cnt.get(b-1,0) + 1
    nodes[a-1].add(b-1)
    nodes[b-1].add(a-1)


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

Z = cnt.items()
Z = sorted(Z, key=lambda x:x[1], reverse=True)
# print(Z)

opennodes = {Z[0][0]}
closednodes = set()

ans = [-1] * N


for i in range(N):
    n = opennodes.pop()
    closednodes.add(n)
    ans[n] = C[i]

    for nn in nodes[n]:
        if not nn in closednodes:
            opennodes.add(nn)

print(sum(C) - max(C))
print(" ".join([str(x) for x in ans]))

Submission status: Accepted

Solution code:
n = int(input())

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

from collections import defaultdict
G = defaultdict(list)


abl = []
for _ in range(n-1):
    a,b = map(int,input().split())
    deg[a-1] += 1
    deg[b-1] += 1
    abl.append((a-1, b-1))
    G[a-1].append(b-1)
    G[b-1].append(a-1)

cl = list(map(int,input().split()))
cl = sorted(cl)
ansl = [0 for _ in range(n)]
for c in cl:
    for idx, d in enumerate(deg):
        if d == 1:
            ansl[idx] = c
            deg[idx] -= 1
            for j in G[idx]:
                deg[j] -= 1
            break
for idx, a in enumerate(ansl):
    if a == 0:
        ansl[idx] = cl[-1]

print(sum(cl[:-1]))
print(*ansl)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque

n = int(readline())
graph = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, readline().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
c = list(map(int, readline().split()))
c.sort()
print(sum(c[:-1]))
q = deque([0])
d = [-1] * n

while q:
    x = q.popleft()
    d[x] = c.pop()
    for next in graph[x]:
        if d[next] < 0:
            q.appendleft(next)

print(*d)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
s=[[]for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x: int(x)-1,input().split())
    s[a].append(b)
    s[b].append(a)
sys.setrecursionlimit(20000)
l=[None]*N
def hu(n):
    for i in s[n]:
        if l[i]==None:
            l[i]=c.pop()
            hu(i)
c=list(map(int,input().split()))
c.sort()
print(sum(c[:-1]))
l[0]=c.pop()
hu(0)
print(*l)

Submission status: Accepted

Solution code:
# スタート地点からDFSで大きい順に入れていけば、最も大きい数以外は得点を得られる

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 = sorted(list(map(int,input().split())))[::-1]

ans = [-1 for i in range(N)] # -1は未訪問
point = sum(C[1:])

from collections import deque
q = deque([])
q.append(0)
ind = 0
while q:
  v = q.popleft()
  if ans[v] != -1:
    # 訪問済み
    continue
  ans[v] = C[ind]
  ind += 1
  if ind == len(C):
    break
  children = E[v]
  for child in children:
    q.append(child)
  
print(point)  
print(*ans)

Submission status: Accepted

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

C.sort()

M = sum(C[:-1])
d = [-1] * N

from collections import deque

que = deque([0])
while que:
    v = que.popleft()
    d[v] = C.pop()
    for w in edge[v]:
        if d[w] < 0:
            que.append(w)

print(M)
print(*d)

Submission status: Accepted

Solution code:
N=int(input())
G=[[] for _ in range(N)]
for _ in range(N-1):
    a,b=map(int, input().split())
    a,b=a-1,b-1
    G[a].append(b)
    G[b].append(a)
*C,=map(int, input().split())

C.sort(reverse=True)
ans=[-1]*N

stk=[0]
ans[0]=C[0]
idx=1
while stk:
    v=stk.pop()
    for to in G[v]:
        if ans[to]>0: continue
        ans[to]=C[idx]
        idx+=1
        stk.append(to)

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

Submission status: Accepted

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        Edge[a-1].append(b-1)
        Edge[b-1].append(a-1)
    C = [int(c) for c in input().split()]
    C.sort(reverse  = True)
    Color = [None] * N
    Color[0] = C[0]
    q = deque()
    for e in Edge[0]:
        q.append((e, 0))
    ans = 0
    for i in range(1, N):
        nowN, preN = q.popleft()
        ans += C[i]
        Color[nowN] = C[i]
        for e in Edge[nowN]:
            if e != preN: q.append((e, nowN))
    print(ans)
    print(" ".join(map(str, Color)))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

n = int(input())
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    g[a].append(b)
    g[b].append(a)
C = list(map(int, input().split()))
C.sort()

s = []
parent = [-1]*n
order = []
s.append(0)
while s:
    v = s.pop()
    order.append(v)
    for u in g[v]:
        if parent[v] == u:
            continue
        parent[u] = v
        s.append(u)

order.reverse()
ans = 0
D = [0]*n
for i in range(n):
    v = order[i]
    D[v] = C[i]
    if i != n-1:
        ans += C[i]
print(ans)
print(*D)

Submission status: Accepted

Solution code:
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
C = list(map(int,input().split()))
C.sort()
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

stack = [0]
ans = [-1] * N
ans[0] = C.pop()
m = 0
while stack:
    v = stack.pop()
    for to in es[v]:
        if ans[to] >= 0: continue
        ans[to] = C.pop()
        m += ans[to]
        stack.append(to)
print(m)
print(*ans)

Submission status: Accepted

Solution code:
n=int(input())
edge=[[]for _ in range(n)]
for _ 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()))
c.sort(reverse=1)
print(sum(c)-c[0])
d=[-1]*n
d[0]=c[0]
Q=[0]
visited={0}
ind=1
while Q:
  P=[]
  for i in Q:
    for j in edge[i]:
      if j in visited:continue
      visited.add(j)
      d[j]=c[ind]
      ind+=1
      P.append(j)
  Q=P
print(*d)

Submission status: Accepted

Solution code:
N = int(input())

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)
C = list(map(int, input().split()))
A = sum(C) - max(C)
C.sort()

ans = [None] * N
ans[0] = C.pop()
st = [0]
while st:
    now = st.pop()
    for to in edges[now]:
        if ans[to] == None:
            ans[to] = C.pop()
            st.append(to)

print(A)
print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5*5)
n=int(input())
ab=[[]for _ in range(n)]
for _ in range(n-1):
	a,b=map(int,input().split())
	ab[a-1].append(b-1)
	ab[b-1].append(a-1)
c=list(map(int,input().split()))
c.sort()
print(sum(c)-c[-1])
ans=[-1]*n
cnt=0
node=[]
visited=[0]*n
ans=[-1]*n
def dfs(x):
	global cnt
	ans[x]=c[-cnt-1]
	visited[x]=1
	for next in ab[x]:
		if visited[next]==0:
			cnt+=1
			dfs(next)
dfs(0)
print(*ans)

Submission status: Accepted

Solution code:
n = int(input())
link = [[] for _ in range(n)]
for i in range(n-1):
    a,b = list(map(int,input().split()))
    link[a-1].append(b-1)
    link[b-1].append(a-1)
c=list(map(int, input().split()))
c.sort(reverse=True)
print(sum(c)-c[0])

from collections import deque
Q = deque()
Q.append(0)
visited=[-1]*n
visited[0]=0

ind=1
while Q:
    now = Q.popleft()
    for nxt in link[now]:
        if visited[nxt]!=-1:
            continue
        visited[nxt]=ind
        ind+=1
        Q.append(nxt)
for i in visited:
    print(c[i],end=" ")

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from collections import deque

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)
    
    color = [-1] * n
    s = deque([0])
    i = 0
    while len(s):
        v = s.pop()
        color[v] = c[i]
        for e in G[v]:
            if color[e] != -1:
                continue
            s.append(e)
        i += 1
    
    print(sum(c) - c[0])
    print(*color)
if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

MAXN = 10000
G = [[] for _ in range(MAXN)]
color = [-1] * MAXN

def dfs(i,idx,c):
    color[i] = c[idx]
    for e in G[i]:
        if color[e] != -1:
            continue
        idx = dfs(e,idx + 1,c)
    return idx

def main():
    n = int(input())
    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)

    dfs(0,0,c)
    ans = sum(c) - c[0]
    print(ans)
    print(*color[:n])

if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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=True)
sum_val = sum(c) - max(c)

assign = [0] * N
index = 0

q = deque()
q.append(0)
visited = []

while len(q) != 0:
    cur = q.popleft()
    assign[cur] = c[index]
    index += 1
    for n in graph[cur]:
        if n not in visited:
            q.append(n)
    visited.append(cur)

print(sum_val)
print(" ".join(map(str, assign)))