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(10 ** 9)
import heapq

N = int(input())
E = [list(map(lambda x: int(x)-1,input().split())) for _ in range(N-1)]
C = sorted(list(map(lambda x: int(x)*(-1),input().split())))
m = -sum(C[1:])
heapq.heapify(C)

V = [set() for _ in range(N)]
for u,v in E:
  V[u].add(v)
  V[v].add(u)

A = [0 for _ in range(N)]
def dfs(v,s):
  A[v] = -heapq.heappop(C)
  for u in V[v]:
    if u != s:
      dfs(u,v)
dfs(0,-1)

print(m)
print(*A)

Submission status: Accepted

Solution code:
n=int(input())
g=[[] for i in range(n)]
ro=[0]*n
for i in range(n-1):
    a,b=map(int,input().split())
    ro[a-1]+=1
    ro[b-1]+=1
    g[a-1].append(b-1)
    g[b-1].append(a-1)
c=list(map(int,input().split()))
c.sort(reverse=True)
m=max(ro)
mi=ro.index(m)
q=[mi]
ans=[0]*n
v=[0]*n
v[mi]=1
ans[mi]=c.pop(0)
while len(q)>0:
    s=q.pop()
    for i in g[s]:
        if v[i]==0:
            v[i]=1
            ans[i]=c.pop(0)
            q.append(i)
print(sum(ans)-max(ans))
print(*ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)
c=list(map(int,input().split()))
c.sort()
c.reverse()

def bfs(v):
  ans=[-1]*n
  ans[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    for i in range(len(next)):
      if visited[next[i]]==-1:
        ct+=1
        ans[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return ans

ans=bfs(0)
print(sum(c)-c[0])
for i in range(n):
  ans[i]=str(c[ans[i]])
print(' '.join(ans))

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
edge=[]
graph=[[] for i in range(n)]
point=[-1]*n
for i in range(n-1):
  a,b=map(int,input().split())
  a-=1;b-=1
  edge.append([a,b])
  graph[a].append(b)
  graph[b].append(a)
num=list(map(int,input().split()));num.sort()
start=0
for i in range(n):
  if len(graph[i])==1:
    start=i
    break
dfs=deque([start])
while dfs:
  v=dfs.popleft()
  point[v]=num.pop()
  for i in graph[v]:
    if point[i]!=-1:continue
    dfs.appendleft(i)
ans=0
for i in edge:
  ans+=min(point[i[0]],point[i[1]])
print(ans)
print(*point)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())

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

ans=[0]*n

from collections import deque

c=list(map(int,input().split()))
c.sort(reverse=True)
c=deque(c)
q=deque()
q.append([0])
while q:
    ll=q.popleft()
    for v in ll:
        if ans[v]!=0:
            continue
        ans[v]=c.popleft()
        q.append(l[v])

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

print(x)
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
dic = {}
lnum = [0] * N
q = deque([])
alis = [0] * N


for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    lnum[a] += 1
    lnum[b] += 1

    if a not in dic:
        dic[a] = []

    if b not in dic:
        dic[b] = []

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

for i in range(N):

    if lnum[i] == 1:
        q.append(i)

c = list(map(int,input().split()))
c.sort()
#print (c)
for i in range(N):

    now = q.popleft()
    lnum[now] = 0

    alis[now] = c[i]
    #print (q,now,alis)

    for nex in dic[now]:

        lnum[nex] -= 1
        if lnum[nex] == 1:
            q.append(nex)

print (sum(c) - c[-1])
print (" ".join(map(str,alis)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():
    from collections import deque

    n = int(input())
    graph = [list() for _ in range(n)]

    for i in range(n - 1):
        ai, bi = map(int, input().split())
        graph[ai - 1].append(bi - 1)
        graph[bi - 1].append(ai - 1)

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

    # スコアの最大値：数列cのうち，最大値を除いた合計
    print(sum(c[1:]))

    # 書き込み方：根から大きな値を割り当てるとよさそう
    visited = [False for _ in range(n)]
    visited[0] = True
    d = deque()
    d.append(0)
    ans = [0 for _ in range(n)]
    ans[0] = c[0]
    count = 1

    while d:
        di = d.popleft()

        for dii in graph[di]:
            if not visited[dii]:
                ans[dii] = c[count]
                count += 1
                visited[dii] = True
                d.append(dii)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n+1)]
    for i in range(len(s)):
        pt[s[i]].append(t[i])
        if directed==False:
            pt[t[i]].append(s[i])
    return pt

N = I()
a,b = Line(N-1,2)
c = III()

if N==1:
    print(c[0])
    print(c[0])
    exit()

c.sort()
M = sum(c[:-1])

pt = edges_to_pt(a,b,N)

used = [False]*(N+1)
ans = [0]*(N+1)
used[1] = True
ans[1] = c.pop()
q = [1]
while q:
    q1 = []
    for i in q:
        for j in pt[i]:
            if used[j]==False:
                used[j] = True
                ans[j] = c.pop()
                q1.append(j)
    q = q1

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

Submission status: Accepted

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

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

c = sorted([int(i) for i in input().split()], reverse=True)

visited = [-1] * N
cnt = 0
que = deque([1])

while que:
    i = que.popleft()
    visited[i-1] = c[cnt]
    cnt += 1

    for j in G[i]:
        if visited[j-1] == -1:
            que.append(j)

# print(visited)
print(sum(c[1:]))
print(*visited)

Submission status: Accepted

Solution code:
# m-solutions2019D - Maximum Sum of Minimum
def bfs(start: int) -> None:
    q = [start]
    nodes[start] = C.pop()
    while q:
        v = q.pop(0)
        for u in T[v]:
            if not nodes[u]:
                nodes[u] = C.pop()
                q.append(u)


def main():
    # adjacent edges should have close numbers as much as possible -> sort, bfs
    global T, C, nodes
    N, *ABC = map(int, open(0).read().split())
    AB, C = ABC[:-N], ABC[-N:]
    C.sort()
    T = [[] for _ in range(N + 1)]
    for v, u in zip(*[iter(AB)] * 2):
        T[v].append(u), T[u].append(v)
    score, nodes = sum(C) - C[-1], [0] * (N + 1)  # max of C will not be used
    for i, t in enumerate(T[1:], 1):
        if len(t) == 1:
            start = i  # start from any node with degree 1
            break
    bfs(start)
    print(score)
    print(*nodes[1:])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
c=list(map(int,input().split()))
c.sort()
connection=[[] for i in range(n)]
ans=[0 for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)
next=[0]
next=deque(next)
check=[-1 for i in range(n)]
check[0]=1
ct=n
while ct>0:
  ct-=1
  x=next.popleft()
  ans[x]=str(c[ct])
  for i in range(len(connection[x])):
    if check[connection[x][i]]==-1:
      next.append(connection[x][i])
      check[connection[x][i]]=1
print(sum(c)-c[n-1])
print(' '.join(ans))

Submission status: Accepted

Solution code:
# m-solutions2019D - Maximum Sum of Minimum
def bfs(start: int) -> None:
    q = [start]
    nodes[start] = C.pop()
    while q:
        v = q.pop(0)
        for u in T[v]:
            if not nodes[u]:
                nodes[u] = C.pop()
                q.append(u)


def main():
    global T, C, nodes
    N, *ABC = map(int, open(0).read().split())
    AB, C = ABC[:-N], ABC[-N:]
    C.sort()
    T = [[] for _ in range(N + 1)]
    for v, u in zip(*[iter(AB)] * 2):
        T[v].append(u), T[u].append(v)
    score, nodes = sum(C) - C[-1], [0] * (N + 1)  # max of C will not be used
    for i, t in enumerate(T[1:], 1):
        if len(t) == 1:
            start = i
            break
    bfs(start)
    print(score)
    print(" ".join(map(str, nodes[1:])))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections

n=int(input())
g=[[] for _ in range(n+1)]
for _ 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=sorted(c,reverse=True)
m=sum(c)-c[0]
ans=[0]*(n+1)
ans[1]=c[0]
q=collections.deque()
q.append(1)
checked=[0]*(n+1)
checked[1]=1
cnt=1
while len(q):
  tmp=q.popleft()
  for v in g[tmp]:
    if checked[v]==0:
      checked[v]=1
      q.append(v)
      ans[v]=c[cnt]
      cnt+=1
print(m)
print(*ans[1:])

Submission status: Accepted

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

q = [0]
checked = [False]*N
checked[0] = True
ans = 0
c = 0
score = [None for _ in range(N)]
score[0] = C[c]

while q:
    qq = []
    for p in q:
        for np in graph[p]:
            if not checked[np]:
                qq.append(np)
                checked[np] = True
                c += 1
                score[np] = C[c]
                ans += min(score[np], score[p])
    q = qq

print(ans)
for s in score:
    print(s, end=' ')
print()

Submission status: Accepted

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

C = list(map(int, input().split()))
C.sort(reverse=True)
D = [0 for _ in range(N)]
stack = es[0]
D[0] = C[0]
cnt_c = 1
while stack:
    new_stack = []
    for i in stack:
        if D[i] == 0:
            D[i] = C[cnt_c]
            cnt_c += 1
            new_stack.extend(es[i])
    if len(new_stack) == 0:
        break
    else:
        stack = new_stack

print(sum(D) - C[0]) # ｃの最大のやつは辺の値になれないので引く
print(*D)

Submission status: Accepted

Solution code:
N = int(input())
E = [set() for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  E[a].add(b)
  E[b].add(a)
cs = list(map(int, input().split()))
cs.sort()
M = sum(cs[:-1])
ds = [-1]*N
ds[0] = cs.pop()
q = [0]
while q:
  c = q.pop()
  ns = E[c]
  for n in ns:
    if ds[n] < 0:
      ds[n] = cs.pop()
      q.append(n)
print(M)
print(" ".join(map(str, ds)))

Submission status: Accepted

Solution code:
import collections
import sys
input = sys.stdin.readline
import heapq
def solve():
  n = int(input())

  query2 = []
  edge = [[] for _ in range(n)]
  ans = [ 0 for i in range(n)]
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query2.append(a)
    query2.append(b)
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
  c = list(int(i) for i in input().split())
  if n == 1:
    print(0)
    print(c[0])
    exit()
  c = collections.deque(sorted(c,reverse =True))
  d = collections.Counter(query2)
  d2 = d.most_common()
  bfs = []
  heapq.heappush(bfs,(-1*d2[0][1],d2[0][0]-1))#回数,場所、親
  ct = 0
  visit = [False]*n
  
  while bfs:
    times,place = heapq.heappop(bfs)
    if visit[place]:
      continue
    else:
      visit[place] = True

      for i in range(len(edge[place])):
        newp = edge[place][i]
        newtimes = len(edge[newp])
        if not visit[newp]:
          heapq.heappush(bfs,(-1*newtimes,newp))
      #print(place,parent,times)
      ans[place] = c.popleft()

      #print(c,place)

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

Submission status: Accepted

Solution code:
import collections
import sys
input = sys.stdin.readline
import heapq
from array import array
def solve():
  n = int(input())

  query2 = collections.deque([])
  edge = [[] for _ in range(n)]
  ans = array('I', [ 0 for i in range(n)])
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query2.append(a)
    query2.append(b)
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
  c = list(int(i) for i in input().split())
  if n == 1:
    print(1)
    print(c[0])
    exit()
  c = collections.deque(sorted(c,reverse =True))
  d = collections.Counter(query2)
  d2 = d.most_common()
  bfs = []
  heapq.heappush(bfs,(-1*d2[0][1],d2[0][0]-1,-1))#回数,場所、親
  ct = 0
  visit = [False]*n
  while bfs:
    times,place,parent = heapq.heappop(bfs)
    if visit[place]:
      continue
    else:
      visit[place] = True

      for i in range(len(edge[place])):
        newp = edge[place][i]
        newtimes = len(edge[newp])
        if not visit[newp]:
          heapq.heappush(bfs,(-1*newtimes,newp,place))
      #print(place,parent,times)
      ans[place] = c.popleft()

      #print(c,place)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#M-SOLUTIONS プロコンオープン D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
cnt = [0]*n
graph = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = LI()
    cnt[a-1] += 1
    cnt[b-1] += 1
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
c = LI()
m = sum(c) - max(c)
print(m)
d = [0]*n
for i in range(n):
    if cnt[i] == 1:
        d[i] = max(c)
        break
c.sort(reverse = True)
c = c[1:]
que = deque(c)
def dfs(x,p):
    for v in graph[x]:
        if v != p:
            if d[v] == 0:
                d[v] = que.popleft()
                dfs(v,x)
dfs(i,-1)
print(*d)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

edges = [[] for _ in range(N)]
edgeList = []
for _ in range(N - 1):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edges[to].append(fr)
    edgeList.append((fr, to))

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

M = sum(C) - C[-1]

values = [-1] * N
que = deque([0])

while que:
    now = que.popleft()
    values[now] = C.pop()
    for to in edges[now]:
        if values[to] == -1:
            que.append(to)

print(M)
print(*values)

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(100000)

N=int(input())
AB=[list(map(int,input().split())) for _ in range(N-1)]
C=deque(sorted(map(int,input().split())))
edges=[[] for _ in range(N)]
for a,b in AB:
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

ps=[0]*N

def dfs(prev, curr):
    ps[curr]=C.pop()
    for dst in edges[curr]:
        if prev==dst:
            continue
        dfs(curr,dst)
dfs(-1,0)

ans=0
for a,b in AB:
    ans += min(ps[a-1],ps[b-1])

print(ans)
print(" ".join([str(p) for p in ps]))

Submission status: Accepted

Solution code:
#解説チラ見
n = int(input())
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
now = [0]
scr = list(map(int,input().split()))
scr.sort()
scr.reverse()
ans = [0 for _ in range(n)]
ans[0] = scr[0]
pin = 1
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if ans[y] == 0:
        ans[y] = scr[pin]
        pin += 1
        now.append(y)
print(sum(scr[1:]))
print(' '.join(list(map(str,ans))))

Submission status: Accepted

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

vi = 0 #時と場合によってここを変える
from collections import deque
Q = deque([vi])
checked_list = [False for i in range(N)]
checked_list[vi]=True
min_path_list = [10**27 for i in range(N)] #問題によりここを変える
min_path_list[vi] = 0
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.appendleft(v1)
            min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) #問題によりここを変える


min_i_list = [[i,min_path_list[i]] for i in range(N)]
min_i_list.sort(key=lambda x:x[1],reverse=True)

c.sort()

ans = [[min_i_list[i][0]+1, c[i]] for i in range(N)]

ans.sort(key=lambda x:x[0])
ans = [ans[i][1] for i in range(N)]
print(sum(c[:-1]))
print(*ans)

Submission status: Accepted

Solution code:
n = int(input())
tree = [set() for i in range(n)]
con = [0]*n
ans = [0]*n
scr = 0
for _ in range(n-1):
  a,b = map(lambda x:int(x)-1, input().split())
  tree[a].add(b)
  tree[b].add(a)
  con[a] += 1
  con[b] += 1
st = []
for i in range(n):
  if con[i] == 1:
    st.append(i)
c = list(map(int, input().split()))
c.sort(reverse=True)
while st:
  v = st.pop()
  if ans[v]:
    continue
  ans[v] = c.pop()
  scr += ans[v]*con[v]
  con[v] = 0
  for x in tree[v]:
    if ans[x]:
      continue
    con[x] -= 1
    if con[x] <= 1:
      st.append(x)
print(scr)
print(" ".join(map(str,ans)))

Submission status: Accepted

Solution code:
#D問題
import heapq
N = int(input())
AB = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    AB[a].append(b)
    AB[b].append(a)
    
C = list(map(int,input().split()))
C.sort(reverse=True)

var = [0 for i in range(N)]
var[0] = C[0]
Q = []
heapq.heappush(Q,0)
ind = 1

for i in range(N-1):
    q = heapq.heappop(Q)
    for j in AB[q]:
        if var[j] == 0:
            var[j] = C[ind]
            ind+=1
            heapq.heappush(Q,j)
            
print(sum(C)-C[0])
for v in var:
    print(v,end=" ")

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n = i()
ab = mip(n - 1)
c = wi()
c.sort(reverse=True)

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

for x, y in ab:
    connect[x].append(y)
    connect[y].append(x)

flagli = [0] * n
ansli = [0] * n

queue = deque()
queue.append(0)
cnt = 0
while queue != deque():
    kk = queue.popleft()
    flagli[kk] = 1

    ansli[kk] = c[cnt]
    cnt += 1

    for root in connect[kk]:
        if flagli[root] == 0:
            queue.append(root)

sumans = sum(c) - max(c)
print(sumans)
print(*ansli)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
d = defaultdict(list)
n = int(input())
for i in range(n-1):
    u, v = map(int, input().split())
    u-=1
    v-=1
    d[u].append(v)
    d[v].append(u)
c = list(map(int, input().split()))
c.sort(reverse = True)
vis = [0 for i in range(n)]
q = deque([])
q.append(0)
vis[0] = c[0]
ind = 1
while(q):
    f = q.popleft()
    for i in d[f]:
        if not vis[i]:
            vis[i] = c[ind]
            ind+=1
            q.append(i)
print(sum(vis) - c[0])
print(*vis)

Submission status: Accepted

Solution code:
N = int(input())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]
*C, = sorted(map(int,input().split()))
print(sum(C[:-1]))
E = [[] for _ in [0]*N]
d = [0]*N
for a,b in AB:
    E[a-1].append(b-1)
    E[b-1].append(a-1)

for i in range(N):
    if len(E[i])>1:break
q = [i]
while q:
    i = q.pop()
    d[i] = C.pop()
    for j in E[i]:
        if d[j] != 0:continue
        q.append(j)
print(*d)

Submission status: Accepted

Solution code:
from collections import deque

class Node:
    def __init__(self):
        self.val = -1
        self.link = []

def main():
    N = int(input())
    nodes = [Node() for i in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1; b -= 1;
        nodes[a].link.append(nodes[b])
        nodes[b].link.append(nodes[a])
    c = list(map(int, input().split()))
    c = sorted(c, reverse=True)
    count = 0
    q = deque()
    q.append(nodes[0])
    while len(q) > 0:
        node = q.popleft()
        node.val = c[count]
        count += 1
        for next in node.link:
            if next.val == -1:
                q.append(next)
    print(sum(c) - c[0])
    for i in range(N):
        print(nodes[i].val, end="")
        if i != N-1:
            print(" ",end="")
        else:
            print()

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


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

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

# heapqで大きい順に取り出したいから、マイナスにしておく。
L = list(map(lambda x: -int(x), input().split()))
heapq.heapify(L)
# Maxは一番大きい数字以外の和.(全体の和-最大の整数)でも止める。
# Lはマイナスがかけてあるので、min(L)で最大の和が求まる
score = -sum(L)+min(L)


# nodeに書く数字
node = [-1]*N

# leafを探す,leafからbfsして訪問順に大きい数字を入れていく
leaf = -1
for i, a in enumerate(adj):
    if len(a) == 1:
        leaf = i
        break

# bfs
Q = [leaf]
while Q:
    cur = Q.pop()
    for a in adj[cur]:
        if node[a] == -1:  # まだたどり着いてないとこには、数字を入れる。
            node[a] = - heapq.heappop(L)
            Q.append(a)
print(score)
print("\n".join(map(str, node)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n=int(input())

g=[[] for _ in range(n+1)]
v=[0 for _ 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=sorted([int(i) for i in input().split()])[::-1]

def bfs(x):
    p=[]
    q=[x]
    while q:
        y=q.pop()
        v[y]=1
        p.append(y)
        for nb in g[y]:
            if v[nb]!=1:
                q.append(nb)
    return p

l=bfs(1)
ans=[0]*(n)
for i in range(n):
    ans[l[i]-1]=c[i]

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

Submission status: Accepted

Solution code:
import collections, heapq, sys

n = int(sys.stdin.readline().rstrip())
g = collections.defaultdict(list)
visited = set()
deg = collections.defaultdict(int)
for i in range(n-1):
    a, b = map(int, sys.stdin.readline().rstrip().split(' '))
    deg[a] += 1
    deg[b] += 1
    g[a].append(b)
    g[b].append(a)

pq = []
for i in range(1, n+1):
    heapq.heappush(pq, [deg[i], i])
wts = map(int, sys.stdin.readline().rstrip().split(' '))
wts.sort(reverse=True)
    
vToWt = [-1 for _ in range(n+1)]
sm = 0
while len(pq):
    _, v = heapq.heappop(pq)
    
    if vToWt[v] != -1:
        continue
    vToWt[v] = wts.pop()
    for nei in g[v]:
        if vToWt[nei] != -1:
            continue
        sm += vToWt[v]
        deg[nei] -= 1
        heapq.heappush(pq, [deg[nei], nei])

print(sm)
print(' '.join(map(str, [x for x in vToWt[1:]])))

Submission status: Accepted

Solution code:
from collections import deque

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

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

c = list(map(int, input().split()))
c = sorted(c, reverse=True)
sums = sum(c) - max(c)

q = deque([0])
d = [-1] * N

num = 0
while len(q) > 0:
    x = q.popleft()
    d[x] = c[num]
    num += 1
    for y in link[x]:
        if d[y] < 0:
            q.append(y)

print(sums)
print(*d)

Submission status: Accepted

Solution code:
N=int(input())
from collections import defaultdict
branch=defaultdict(set)
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    branch[a]|={b}
    branch[b]|={a}
C=list(map(int,input().split()))
C.sort()
ans=[0]*N
used={0}
check={0}
M=sum(C[:-1])
while len(check)>0:
    now=check.pop()
    ans[now]=C.pop()
    for nex in branch[now]:
        if nex not in used:
            check|={nex}
            used|={nex}
print(M)
print(" ".join([str(x) for x in ans]))

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
G = [[] for i in range(N)]
D = [0]*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)
    D[a-1] += 1
    D[b-1] += 1
*C, = map(int, input().split())
C.sort()

U = [1]*N
que = deque()
for i in range(N):
    if D[i] <= 1:
        que.append(i)
        U[i] = 0
it = iter(C).__next__
ans = [0]*N
R = 0
while que:
    v = que.popleft()
    ans[v] = r = it()
    R += r
    for w in G[v]:
        if U[w] == 0:
            continue
        D[w] -= 1
        if D[w] <= 1:
            U[w] = 0
            que.append(w)
print(R - C[-1])
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
ab = [[int(i)-1 for i in input().split()] for _ in range(N-1)]
c = [int(i) for i in input().split()]
                
c.sort()
d = [0] * N

vector = [[] for _ in range(N)]
for a, b in ab :
    vector[a].append(b)
    vector[b].append(a)

ret = sum(c[:-1]) 
queue = deque([0])
visited = [False] * N
visited[0] = True

while queue :
    q = queue.popleft()
    for v in vector[q] :
        if not visited[v] :
            queue.append(v)
            visited[v] = True
    d[q] = c.pop()
    
print(ret)
print(' '.join(map(str, d)))

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)

al = [[] for _ in range(N+1)]
for a,b in ab:
    al[a].append(b)
    al[b].append(a)

d = [0] * (N)
d[ab[0][0]-1] = c[0]
cnt = 1
child = al[ab[0][0]]
ans = 0
Check = [True] * (N+1)
Check[ab[0][0]] = False

while child and cnt < N:
    pi = int(child.pop())
    Check[pi] = False
    d[pi-1] = (c[cnt])
    ans += c[cnt]
    for i in al[pi]:
        if Check[i]:child.append(i)
    cnt += 1
    
print(ans)
print(' '.join(map(str,d)))