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(2000000)

N = int(input())
ab = list(list(map(int,input().split())) for i in range(N-1))
c = list(map(int,input().split()))
c.sort(reverse=True)
print(sum(c)-c[0])
tree = [[-1]for i in range(N)]
for a,b in ab:
    tree[a-1].append(b)
    tree[b-1].append(a)
def func(l):
    if tree[l-1][0] != -1:
        return
    tree[l-1][0] = c.pop(0)
    for i in tree[l-1][1:]:
        func(i)
func(1)
for i in tree:
    print(i[0],end = " ")

Submission status: Accepted

Solution code:
# 最小値が端点でないと、隣接とswapして矛盾。
# 最小値は端点としてよい。
# 端点のどれでもよい。
# あとは帰納的に

N = int(input())
score = 0

edge = [set() for _ in range(N+1)]
for _ in range(N-1):
  a,b = map(int,input().split())
  edge[a].add(b)
  edge[b].add(a)

C = [int(x) for x in input().split()]
deg = [len(x) for x in edge]

# degree1の頂点全体
deg_1 = [i for i,x in enumerate(deg) if x == 1]

D = [None]*(N+1)
C.sort(reverse = True)
M = sum(C) - C[0] # score
  
while deg_1:
  v = deg_1.pop()
  if not deg_1:
    D[v] = C.pop()
    break
  w = edge[v].pop()
  edge[w].remove(v)
  deg[w] -= 1
  if deg[w] == 1:
    deg_1.append(w)
  D[v] = C.pop()

  
print(M)
print(' '.join(map(str,D[1:])))

Submission status: Accepted

Solution code:
def sol(_inp=input):
    n=int(_inp())
    tree={i+1:set() for i in range(n)}
    assigned=[0 for _ in range(n)]
    for _ in range(n-1):
        i,j=map(int,_inp().split())
        tree[i].add(j)
        tree[j].add(i)
    cs=sorted(list(map(int,_inp().split())))
    tree_orig={i:tree[i].copy() for i in tree}
    for c in cs[:-1]:
        for v in tree:
            if len(tree[v])==1:
                assigned[v-1]=c
                w=list(tree[v])[0]
                tree[v]=set()
                tree[w].remove(v)
                break
    else:
        assigned[w-1]=cs[-1]
    res=sum(min(assigned[v-1],assigned[w-1]) for v in tree_orig for w in tree_orig[v])//2
    return '{}\n{}'.format(res,' '.join(str(c) for c in assigned))
print(sol())

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    print((n-2)*180)
    return

#B
def B():
    b = S()
    kati = b.count("o")
    kati += 15 - len(b)
    if kati >= 8:
        print("YES")
    else:
        print("NO")
    return

#C
def C():
    return

#D
def D():
    n = II()
    ab = LIR_(n-1)
    C = LI()
    C.sort(reverse=True)
    c = deque()
    for ci in C:
        c.appendleft(ci)
    edg = [[] for i in range(n)]
    for a, b in ab:
        edg[a].append(b)
        edg[b].append(a)
    for num,e in enumerate(edg):
        if len(e) == 1:
            start = num
            break
    q = deque()
    ans = [0 for i in range(n)]
    q.append(start)
    ans[start] = c.pop()
#    print(start)
    while q:
        p = q.pop()
        for e in edg[p]:
            if not ans[e]:
                ans[e] = c.pop()
                q.append(e)
    anssum = 0
    for a, b in ab:
        anssum += min(ans[a], ans[b])
    print(anssum)
    ans = list(map(str, ans))
    print(" ".join(ans))


    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:

from collections import defaultdict

from math import factorial
# 組み合わせ
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))


def main():
    num = int(input())

    parent_dic = [-1 for i in range(num)]
    now_dic = defaultdict(set)
    data_dic = []

    for i in range(num - 1):
        a, b = map(int, input().split())
        now_dic[a].add(b)
        now_dic[b].add(a)
        data_dic.append([a, b])

    ans_omomi = [-1 for i in range(num + 1)]

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

    # node_omomi = sorted(node_omomi.items(), key=lambda x: x[1])

    now_data = set()
    now_data.add(1)
    next_data = set()

    count = 0
    ans_omomi[1] = omomi_data[count]

    count += 1



    while len(now_data) > 0:
        for ele_pare in now_data:
            for ele in now_dic[ele_pare]:
                if ans_omomi[ele] != -1:
                    continue
                ans_omomi[ele] = omomi_data[count]
                count += 1
                next_data.add(ele)
        now_data = next_data
        next_data = set()

    # print(ans_omomi)
    # print(data_dic)


    final_omomi = 0
    for i in range(num - 1):
        kari = min(ans_omomi[data_dic[i][0]], ans_omomi[data_dic[i][1]])
        final_omomi += kari
    print(final_omomi)
    print(' '.join(list(map(str, ans_omomi[1:]))))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue

N = int(input())
edge = [set([]) for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].add(b)
    edge[b].add(a)
c = list(map(int, input().split()))
c.sort()
q = queue.Queue()
for i in range(N):
    if len(edge[i]) == 1:
        q.put(i)
ans = [0] * N
i = 0
while not q.empty():
    j = q.get()
    ans[j] = c[i]
    i += 1
    if len(edge[j]) == 0:
        continue
    k = list(edge[j])[0]
    edge[k].remove(j)
    if len(edge[k]) == 1:
        q.put(k)
print(sum(c[:-1]))
for i in ans:
    print(i, end = " ")
print()

Submission status: Accepted

Solution code:
from collections import deque


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

for i in range(n-1):
    tree[info[i][0] - 1].append(info[i][1]-1)
    tree[info[i][1] - 1].append(info[i][0]-1)

for i in range(n):
    if len(tree[i]) == 1:
        leaf = i
        break

q = deque([])
q.append([-1, leaf])
visited = [False]*n
visited[leaf] = True
max_ans = 0
ans = [0]*n
j = 0

while q:
    prev_pos, now_pos = q.pop()
    ans[now_pos] = c[j]
    j += 1
    if prev_pos != -1:
        max_ans += min(ans[prev_pos], ans[now_pos])
    for i in tree[now_pos]:
        if not visited[i]:
            visited[i] = True
            q.append([now_pos, i])
print(max_ans)

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

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
nums = [-1 for _ in range(n)]
edges = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = list(map(lambda x: int(x) - 1, input().split()))
    edges[a].append(b)
    edges[b].append(a)

cs = sorted(list(map(int, input().split())), reverse=True)
cost = sum(cs[1:])
cs = deque(cs)

start = -1
for i, e in enumerate(edges):
    if len(e) == 1:
        start = i
        break

q = deque([start])
while len(q) > 0:
    p = q.popleft()
    c = cs.popleft()
    nums[p] = c
    for np in edges[p]:
        if nums[np] == -1:
            q.append(np)

print(cost)
print(' '.join(map(str, nums)))

Submission status: Accepted

Solution code:
n=int(input())
pair={}
nodes=[0]*n
for _ in range(n-1):
    a,b=map(int,input().split())
    pair.setdefault(a, [])
    pair.setdefault(b, [])
    pair[a]+=[b]
    pair[b] += [a]
c=list(map(int,input().split()))
c.sort()
kei=sum(c[:-1])
cnt=0
nodes[0]=c.pop()
tugi=pair[1]
while c:
    ntugi=[]
    for i in tugi:
        nodes[i-1]=c.pop()
        for ii in pair[i]:
            if nodes[ii-1]>0:continue
            ntugi+=[ii]
    tugi=ntugi
print(kei)
print(*nodes)

Submission status: Accepted

Solution code:
import numpy as np

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 = np.fromiter(map(int, input().split()), np.int)
C = np.sort(C)[::-1]

Z = [-1] * N

stack = [0]
index = 0
while stack:
	v = stack.pop()
	if Z[v] >= 0:
		continue
	Z[v] = C[index]
	index += 1
	stack.extend(E[v])

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

N = int(input())
abList = [list(map(int, input().split())) for _ in range(N-1)]
cList = sorted(list(map(int, input().split())), reverse=True)

dd = defaultdict(list)
for ab in abList:
    a, b = ab
    dd[a].append(b)
    dd[b].append(a)

nodeDict = defaultdict(int)
treeQ = deque()
nodeDict[1] = cList[0]
treeQ.append(1)
ci = 1
while(treeQ):
    node = treeQ.popleft()
    for nextNode in dd[node]:
        if not nodeDict[nextNode]:
            treeQ.append(nextNode)
            nodeDict[nextNode] = cList[ci]
            ci += 1

ans1 = sum(cList[1:])
ans2 = ""
for node in nodeDict:
    ans2 += str(nodeDict[node]) + " "

print(ans1)
print(ans2)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
connected_nodes = defaultdict(lambda: {})

for _ in range(n-1):
  a, b = map(int, input().split())
  if a > b:
    a, b = b, a
  connected_nodes[a-1][b-1] = True
  connected_nodes[b-1][a-1] = True

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

if n == 1:
  print(0)
  print(1)
  exit(0)
if n == 2:
  print(min(edges[0]))
  print('1 2')
  exit(0)

# n >= 3

cs = sorted(cs)
answer_sum = sum(cs) - cs[-1]

visiting = [0]
number_map = {}
number_map[0] = cs.pop()

while True:
  if len(number_map.keys()) == n:
    break
  node = visiting.pop()
  #print(f'now in {node}')
  #print(f'look for {connected_nodes[node]}')
  to_search = list(connected_nodes[node].keys())
  for neighbor in to_search:
    if neighbor in number_map:
      continue
    #print(f'look for {neighbor} from {node}')
    number_map[neighbor] = cs.pop()
    connected_nodes[node].pop(neighbor)
    connected_nodes[neighbor].pop(node)
    visiting.append(neighbor)


print(answer_sum)
print(' '.join([str(number_map[k]) for k in sorted(number_map.keys())]))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


N = int_raw()
tree = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = ints_raw()
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

Cs = list(ints_raw())
Cs.sort(reverse=True)
ans_node = [-1]*N
def main():
    max_deg_idx = 0
    max_deg = len(tree[0])
    for idx in range(N):
        if max_deg < len(tree[idx]):
            max_deg = len(tree[idx])
            max_deg_idx = idx
    cur_node_idx = max_deg_idx
    neighbour = []
    ans_node[cur_node_idx] = Cs[0]
    ans = 0
    for c in Cs[1:]:    
        for a in tree[cur_node_idx]:
            if ans_node[a]==-1:
                heappush(neighbour,[-len(tree[a]),a])
        cur_node_idx = heappop(neighbour)[1]
        ans_node[cur_node_idx] = c
        ans += c
    print (ans)
    print (*ans_node,sep=" ")


main()

Submission status: Accepted

Solution code:
from collections import deque
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 = list(map(int,input().split()))
c.sort()
c = c[::-1]
max = c[0]
ans = [0 for i in range(N)]

d = [-1 for i in range(N)]
d[0] = 0
ans[0] = c.pop(0)
q = deque([0 * (N - 1)])
while len(q) > 0:
    u = q.popleft()
    for v in edge[u]:
        if d[v] > -1:
            continue
        d[v] = d[u] + 1
        ans[v] = c.pop(0)
        q.append(v)

print(sum(ans) - max)
print(*ans, sep=" ")

Submission status: Accepted

Solution code:
def li():
    return list(map(int, input().split()))


if __name__ == "__main__":
    n = int(input())
    edge_list = [li() for _ in range(n - 1)]
    c_list = li()

    tree_dict = {}
    for edge in edge_list:
        if edge[0] not in tree_dict:
            tree_dict[edge[0]] = [edge[1]]
        else:
            tree_dict[edge[0]].append(edge[1])
        if edge[1] not in tree_dict:
            tree_dict[edge[1]] = [edge[0]]
        else:
            tree_dict[edge[1]].append(edge[0])

    dim1_list = []
    for key, value in tree_dict.items():
        if len(value) == 1:
            dim1_list.append(key)

    c_list.sort()

    score = sum(c_list) - c_list[-1]
    cost_dict = {}
    # print(dim1_list)
    # print(tree_dict)
    # print(cost_dict)
    # print()
    for c in c_list[:-1]:
        node = dim1_list.pop()
        cost_dict[node] = c
        connected = tree_dict[node][0]
        tree_dict[connected].remove(node)
        if len(tree_dict[connected]) == 1:
            dim1_list.append(connected)
    node = dim1_list.pop()
    cost_dict[node] = c_list[-1]

    print(score)
    for i in range(1, n):
        print(cost_dict[i], end=" ")
    print(cost_dict[n])

Submission status: Accepted

Solution code:
import collections
import sys
input = sys.stdin.readline
n=int(input())
E=[[] for i in range(n)]
EE=[]
P=collections.defaultdict(int)
for i in range(n-1):
  a,b=map(int,input().split())
  E[a-1]+=[b-1]
  E[b-1]+=[a-1]
  EE.append([a,b])
  P[a-1]+=1
  P[b-1]+=1
C=[int(i) for i in input().split()]
C.sort(reverse=True)
P=sorted(P.items(), key=lambda x:x[1],reverse=True)
CC=[0]*n
stack=[P[0][0]]
CC[P[0][0]]=C[0]
ct_p,ct_c=1,1
while stack:
  label=stack.pop(-1)
  for i in E[label]:
    if CC[i]==0:
      CC[i]=C[ct_c]
      ct_c+=1
      stack+=[i]
ans=0
for i in range(n-1):
  a,b=EE[i][0],EE[i][1]
  ans+=min(CC[a-1],CC[b-1])
print(ans)
print(*CC)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun  1 20:46:37 2019

@author: Yamazaki Kenichi
"""
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)

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

for b in ab:
    T[b[1]].append(b[0])
    T[b[0]].append(b[1])

ans = [-1 for i in range(N+1)]
q = deque(T[1])
ans[1] = C[0]

i = 0
while len(q) > 0:
    tmp = q.pop()
    if ans[tmp] == -1:
        ans[tmp] = C[i+1]
        for c in T[tmp]:
            q.append(c)
#        print(q,i,tmp,ans)
        i += 1

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(11000)

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

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

dic = {}
for i in range(n):
    dic[i] = []

cnt = [0]*n
for a,b in ab:
    dic[a].append(b)
    dic[b].append(a)
    cnt[a] += 1
    cnt[b] += 1

c_idx = 0
res = 0
res_arr = [""]*n
used = [0]*n
def f(idx):
    global c_idx, res, used
    used[idx] = 1
    res_arr[idx] = str(c[c_idx])
    for x in dic[idx]:
        if used[x] == 0:
            c_idx += 1
            res += c[c_idx]
            f(x)

f(cnt.index(1))
print(res)
print(" ".join(res_arr))

Submission status: Accepted

Solution code:
N = int(input())
Node = [[] for _ in range(N+1)]
P = []
for _ in range(N-1):
    a, b = map(int, input().split())
    Node[a].append(b)
    Node[b].append(a)
    P.append((a, b))
C = sorted(list(map(int, input().split())))
check = [0]*(N+1)
value = [0]*(N+1)
Q = [1]
cnt = 0
while Q:
    u = Q.pop()
    check[u] = 1
    value[u] = C[N-1-cnt]
    cnt += 1
    for v in Node[u]:
        if check[v]:
            continue
        else:
            Q.append(v)

ans = 0
for a, b in P:
    ans += min(value[a], value[b])

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

Submission status: Accepted

Solution code:
def main():
    import sys,heapq
    input = sys.stdin.readline
    n = int(input())
    edge = [[] for i in range(n)]
    for i in range(n-1):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    
    c2 = list(map(int,input().split()))
    
    c = sorted(c2)
    
    h = []
    for i in range(n):
        heapq.heappush(h,[len(edge[i]),i])
    
    used = [False]*n

    p = [len(edge[i]) for i in range(n)]
    res = 0
    ans = [-1]*n
    for i in range(n):
        q = 0
        while len(h)>0:
            q,ten = heapq.heappop(h)
            if not used[ten]:
                used[ten] = True
                ans[ten] = c[i]
                break
        res += q*c[i]
        for e in edge[ten]:
            if not used[e]:
                p[e]-=1
                heapq.heappush(h,[p[e],e])
    print(res)


    for e in ans:
        print(e,end = ' ')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque


def main():
    input = sys.stdin.readline
    d = defaultdict(list)
    N = int(input())
    ans = [0] * N
    for _ in range(N-1):
        a, b = map(int, input().split())
        d[a-1].append(b-1)
        d[b-1].append(a-1)

    C = list(map(int, input().split()))
    C = sorted(C, key=lambda x: -x)
    score = sum(C[1:])

    ans[0] = C[0]
    cnt = 1
    visited = set([0])
    q = deque()
    q.extend(d[0])
    while len(q) > 0:
        a = q.popleft()

        if a in visited:
            continue

        ans[a] = C[cnt]
        visited.add(a)
        cnt += 1

        q.extend(d[a])

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

n = int(raw_input())

edges = []
g = [[] for i in xrange(n)]

d = [0 for i in xrange(n)]
for i in xrange(n - 1):
    (a, b) = map(int, raw_input().split())
    a -= 1
    b -= 1
    edges.append((a, b))
    g[a].append(b)
    g[b].append(a)
    d[a] += 1
    d[b] += 1

vs = sorted(map(int, raw_input().split()))
vidx = 0
ns = [-1 for i in xrange(n)]

q = deque()

for i in xrange(n):
    if d[i] == 1:
        q.append(i)

while q:
    cur = q.popleft()
    #print q, cur, d
    ns[cur] = vs[vidx]
    vidx += 1

    for nxt in g[cur]:
        d[nxt] -= 1
        #print nxt, d
        if d[nxt] == 1:
            q.append(nxt)

ans = 0
for (a, b) in edges:
    ans += min(ns[a], ns[b])
print ans

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

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()))
cnt = [[0, i] for i in range(N+1)]
adj = [[] for _ in range(N+1)]
for a, b in AB:
    cnt[a][0] += 1
    cnt[b][0] += 1
    adj[a].append(b)
    adj[b].append(a)
cnt.sort(reverse=True)
C.sort(reverse=True)
D = [0]*N
from collections import deque
used = [False] * (N+1)
n_used = 0
def bfs(s):
    global n_used, used
    q = deque()
    q.append(s)
    while q:
        v = q.pop()
        if used[v]:
            continue
        used[v] = True
        D[v-1] = C[n_used]
        n_used += 1
        for nv in adj[v]:
            if not used[nv]:
                q.append(nv)
    return
bfs(cnt[0][1])
ans = 0
for a, b in AB:
    ans += min(D[a-1], D[b-1])

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

Submission status: Accepted

Solution code:
import heapq
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N-1)]
C = list(map(int,input().split()))
C.sort(reverse=True)

es = [[] for i in range(N)]
for a,b in src:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

maxdeg = root = 0
for i,ee in enumerate(es):
    if len(ee) > maxdeg:
        maxdeg = len(ee)
        root = i

hq = [(-maxdeg, root)]
heapq.heapify(hq)

ans = [None] * N
ci = 0
ansval = -C[0]
while hq:
    d,v = heapq.heappop(hq)
    ans[v] = C[ci]
    ansval += C[ci]
    ci += 1
    for to in es[v]:
        if ans[to] is not None: continue
        heapq.heappush(hq, (-len(es[to]),to))

print(ansval)
print(*ans)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
N =int(input())
adj = [set() for i in range(N)]

lis =[[int(i)-1 for i in input().split()]for _ in range(N-1)]

ans =["" for i in range(N)]

D =[int(i) for i in input().split()]
D.sort()
wa = sum(D[:-1])

que =[]

for (i,j) in lis:
    adj[i].add(j)
    adj[j].add(i)

for i,se in enumerate(adj):
    if len(list(se))==1:
        que.append(i)

for _ in range(N-1):
    i = que.pop(0)
    j = list(adj[i])[0]
    ans[i] = str(D.pop(0))
    adj[j].remove(i)
    if len(list(adj[j]))==1:
        que.append(j)
i =que.pop(0)
ans[i] = str(D.pop(0))

print(wa)
print(" ".join(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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

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

height = [None for _ in range(n)]
root = 0
height[root] = 0

def build(node):
    for to in edges[node]:
        if height[to] == None:
            height[to] = height[node] + 1
            build(to)

build(root)

enum = [(-h, i) for i, h in enumerate(height)]
enum.sort()

tree = [None] * n
clst = sorted(map(int, input().split()))

for c, hi in zip(clst, enum):
    h, i = hi
    tree[i] = c

print(sum(clst[:-1]))
print(*tree)

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
A = [[int(i) for i in input().split()] for j in range(n - 1)]
C = [int(i) for i in input().split()]
C.sort(reverse=True)

E = [[] for i in range(n + 1)]
V = [0] * (n + 1)

for a, b in A:
    E[a].append(b)
    E[b].append(a)

t = 0
ma = 0

for i, e in enumerate(E):
    if len(e) > ma:
        t = i
        ma = len(e)

Q = deque()
Q.append((t, 0))
i = 0
visited = [False] * (n + 1)
ans = 0

while Q:
    v, c = Q.popleft()
    if visited[v]:
        continue
    visited[v] = True
    V[v] = C[i]
    ans += min(c, C[i])
    for e in E[v]:
        Q.append((e, C[i]))
    i += 1

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import deque
n=int(input())
Edges=[[] for _ in range(n)]
Cnt=[0]*n
for _ in range(n-1):
    a,b=map(int,input().split())
    Edges[a-1].append(b-1)
    Edges[b-1].append(a-1)
C=list(map(int,input().split()))
C.sort()
print(sum(C)-C[-1])
Used=[False]*n
for i,e in enumerate(Edges):
    if len(e)==1:
        start=i
        break
Ans=[0]*n
q=deque()
q.append(start)
Used[start]=True
while q:
    v=q.popleft()
    Ans[v]=C.pop()
    for u in Edges[v]:
        if not Used[u]:
            Used[u]=True
            q.append(u)
print(*Ans)

Submission status: Accepted

Solution code:
n = int(input())
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
graph = defaultdict(list)
edge = []
for i in range(n-1):
  a, b = list(map(int, input().split()))
  edge.append((a, b))
  graph[a].append(b)
  graph[b].append(a)
c = list(map(int, input().split()))
c.sort(reverse=True)
visited = [0 for i in range(n+1)]
ans = [0 for i in range(n+1)]
score = 0

def dfs(x):
  visited[x] = 1
  for next_ in graph[x]:
    if visited[next_]:
      continue
    dfs(next_)
  if all(visited[i] for i in graph[x]):
    ans[x] = c.pop()
    return
  visited[x] = 0

dfs(1)
for a, b in edge:
  score += min(ans[a], ans[b])
print(score)
print(*ans[1:])

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

table = [[] for _ in range(N)]

for ai, bi in ab:
    table[ai - 1].append(bi - 1)
    table[bi - 1].append(ai - 1)


for i_root, row in enumerate(table):
    # print("##", row)
    if len(row) > 1: break

from collections import deque

c.sort(key=lambda x: -x)

# print("#", i_root)
nodes = [None] * N

q = deque([(i_root, 0)])
nodes[i_root] = c[0]
idx_c = 1
while len(q) > 0:
    src, d = q.popleft()
    for dst in table[src]:
        if nodes[dst] == None:
            q.append((dst, d + 1))
            nodes[dst] = c[idx_c]
            idx_c += 1

# print("#", nodes)
print(sum(c) - c[0])
print(' '.join(map(str, nodes)))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(1000000) #再帰の深さを十分深く設定


n=int(input())
ab = [sorted([int(i)-1 for i in input().split()]) for j in range(n-1)]
c = [int(i) for i in input().split()]
c.sort(reverse = True)

print(sum(c)-max(c))

ko = [[] for i in [0]*n]

for a,b in ab:
    ko[a].append(b)
    ko[b].append(a)
    
ans = [0]*n
pt=0 
used = [0]*n
#print(c)
#print(ab)
#print(ko)
def dfs(x):
    global pt #numbたちがグローバル変数だと教えてあげる
    used[x]=1
    #(x,y)地点を訪問済みにする
    #(x,y)地点での処理を行う（マスの色をカウントするなど）
#    print(x,pt)
    ans[x] = c[pt]
    pt+=1
    #foreach((nx,ny) \in (x,y)のお隣さん){(nx,ny)に訪問していないとき、dfs(nx,ny)} 
    for i in ko[x]:
        if used[i] == 0:
            dfs(i)
        
dfs(0)

print(*ans)

Submission status: Accepted

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

Closed = [False] * (N+1)
q = [1]
A = [0] * (N)
Closed[1] = True
for c in C:
    v = q.pop()
    A[v-1] = c
    for u in E[v]:
        if not Closed[u]:
            q.append(u)
            Closed[u] = True
print(sum(C[1:]))

print(*A)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from sys import setrecursionlimit
setrecursionlimit(10**9)

def inpl(): return list(map(int, input().split()))
N = int(input())
D = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = inpl()
    D[a].append(b)
    D[b].append(a)

C = sorted(inpl())
ans = [-1]*(N+1)
ans[1] = C.pop()
score = 0
def dfs(i):
    global score
    for j in D[i]:
        if ans[j] == -1:
            ans[j] = C.pop()
            score += min(ans[i], ans[j])
            dfs(j)

dfs(1)
print(score)
print(*ans[1:])

Submission status: Accepted

Solution code:
import sys

def main():
    sys.setrecursionlimit(1000000) # recursion limit hack
    buf = input()
    N = int(buf)
    edge = dict()
    ab = []
    for i in range(N):
        edge[i] = [] # zero index
    for i in range(N-1):
        buf = input()
        buflist = list(buf.split())
        a = int(buflist[0])-1 # zero index
        b = int(buflist[1])-1 # zero index
        edge[a].append(b)
        edge[b].append(a)
        ab.append((a, b))
    buf = input()
    buflist = buf.split()
    c = list(map(int, buflist))
    c = list(sorted(c, reverse=True))
    point = 0
    assigned = []
    weight = []
    for i in range(N):
        assigned.append(False)
        weight.append(0)
    start = None
    for k, v in edge.items():
        if len(v) == 1:
            start = k
            break
    recursion_graph(point, start, edge, c, weight, assigned)
    total = 0
    for x in ab:
        total += min(weight[x[0]], weight[x[1]])
    print(total)
    print(' '.join(list(map(str, weight))))

def recursion_graph(point, k, edge, c, weight, assigned):
    weight[k] = c[point]
    assigned[k] = True
    point += 1
    for node in edge[k]:
        if not assigned[node]:
            point = recursion_graph(point, node, edge, c, weight, assigned)
    return point

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

ansd=[0]*(n)
score=0

stack = deque()
stack.append(1)
ansd[0]=cs.pop()
visitted=[]

while stack:
    cur = stack.popleft()
    visitted.append(cur)
    for v in tree[cur]:
        if v in visitted:
            continue
        stack.append(v)
        ansd[v-1]=cs.pop()
        score += min(ansd[cur-1], ansd[v-1])

print(score)
print(*ansd, sep=' ')
#print(visitted)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N = II()
    edges = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = LI_()
        edges[a].append(b)
        edges[b].append(a)
    C = LI()
    C.sort(reverse=True)
    visited = [0] * N
    D = [0] * N
    def solve(v, i):
        visited[v] = 1
        D[v] = C[i]
        for to in edges[v]:
            if not visited[to]:
                i += 1
                i = solve(to, i)
        return i
    solve(0, 0)
    M = sum(C[1:])
    print(M)
    print(*D)

    return

main()