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: Wrong Answer

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)
  for i in range(n):
    now = ans[i]
    flag = True
    for j in range(len(edge[place])):
      newp = edge[i][j]
      ko = ans[newp]
      if i != newp:
       if now > ko:
        flag = False
    if flag:
      ct += now
        
  print(ct)
  print(*ans)
  
solve()

Submission status: Wrong Answer

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)
  for i in range(n):
    now = ans[i]
    flag = True
    for j in range(len(edge[place])):
      newp = edge[i][j]
      ko = ans[newp]
      if now > ko:
        flag = False
    if flag:
      ct += now
        
  print(ct)
  print(*ans)
  
solve()

Submission status: Wrong Answer

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()
      if not parent == -1:
        if ans[place] < ans[parent]:
          ct += ans[place]
      #print(c,place)
  print(ct)
  print(*ans)
  
solve()

Submission status: Wrong Answer

Solution code:
N = int(input())

edges = [[i, []] for i in range(N)]
edgeList = []

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

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

edges.sort(key=lambda A: len(A[1]), reverse=True)
value = [-1] * N
now = N

for i, toNodes in edges:
    value[i] = C.pop()

ans = 0
for fr, to in edgeList:
    ans += min(value[fr], value[to])

print(ans)
print(*value)

Submission status: Wrong Answer

Solution code:
N = int(input())

edges = [[i, []] for i in range(N)]
edgeList = []

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

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

edges.sort(key=lambda A: len(A[1]), reverse=True)
value = [-1] * N
now = N

for i, toNodes in edges:
    if value[i] == -1:
        value[i] = C.pop()
        for to in toNodes:
            if value[to] == -1:
                value[to] = C.pop()
                now -= 1

ans = 0
for fr, to in edgeList:
    ans += min(value[fr], value[to])

print(ans)
print(*value)

Submission status: Wrong Answer

Solution code:
N=int(input())
AB=[list(map(int,input().split())) for _ in range(N-1)]
C=sorted(list(map(int,input().split())),reverse=True)
cnts=[0]*N
for a,b in AB:
    cnts[a-1]+=1
    cnts[b-1]+=1
ps=[0]*N
for j,( _,i) in enumerate(sorted([(c,i) for i,c in enumerate(cnts)],reverse=True)):
    ps[i] += C[j]
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: Wrong Answer

Solution code:
N=int(input())
AB=[list(map(int,input().split())) for _ in range(N-1)]
C=sorted(list(map(int,input().split())))
cnts=[0]*N
for a,b in AB:
    cnts[a-1]+=1
    cnts[b-1]+=1
ps=[0]*N
for j,( _,i) in enumerate(sorted([(c,i) for i,c in enumerate(cnts)])):
    ps[i] += C[j]
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: Wrong Answer

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+1,end=" ")

Submission status: Wrong Answer

Solution code:
import operator

n = int(input())

nodeCount = {i+1 : 0 for i in range(n)}
reqScore = [0 for i in range(n)]

for i in range(n-1):
    a, b = [int(x) for x in input().split()]
    nodeCount[a] += 1
    nodeCount[b] += 1

sortNodes = sorted(nodeCount.items(), key = operator.itemgetter(1))
score = sorted([int(x) for x in input().split()])

for i in range(n):
    reqScore[sortNodes[i][0] - 1] = score[i]

print(sum(score) - max(score))
print(*reqScore)

Submission status: Wrong Answer

Solution code:
import operator

n = int(input())

nodeCount = {i+1 : 0 for i in range(n)}
reqScore = [0 for i in range(n)]

for i in range(n-1):
    a, b = [int(x) for x in input().split()]
    nodeCount[a] += 1
    nodeCount[b] += 1

sortNodes = sorted(nodeCount.items(), key = operator.itemgetter(1))
score = sorted([int(x) for x in input().split()])

for i in range(n):
    reqScore[sortNodes[i][0] - 1] = score[i]

print(((n-1) * (n)) // 3)
print(reqScore)

Submission status: Wrong Answer

Solution code:
import collections, sys

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

sm = 0
wts = map(int, sys.stdin.readline().rstrip().split(' '))
wts.sort(reverse=True)
vToWt = [0 for _ in range(n+1)]
for i in range(1, highestDegree+1):
    for v in degToV[i]:
        vToWt[v] = wts.pop()
        for nei in g[v]:
            edge = '-'.join(map(str, sorted([nei, v])))
            if edge not in visited:
                sm += vToWt[v]
                visited.add(edge)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = [[int(i) for i in input().split()] for _ in range(N-1)]
c = [int(i) for i in input().split()]

c.sort()
mat = [[0] * (N + 1) for _ in range(N + 1)]
d = [0] * N

for a, b in ab :
    mat[a][b] = mat[b][a] = 1
    mat[a][0] += 1
    mat[b][0] += 1
    
for n in range(N) :
    max_k, max_v = 0, -1
    for i in range(1, N + 1) :
        if mat[i][0] > max_v :
            max_k, max_v = i, mat[i][0]   
    d[max_k - 1] = c[N - n - 1]
    mat[max_k][0] = -1            
            
M = 0
for a, b in ab :
    M += min(d[a - 1], d[b - 1])
    
print(M)
print(' '.join(map(str, d)))

Submission status: Wrong Answer

Solution code:
N=int(input())
edge=[[] for i in range(N+1)]
res=[0 for i in range(N+1)]
for i in range(N-1):
	a,b=[int(i) for i in input().split()]
	edge[min(a,b)].append(max(a,b))
c=[int(i) for i in input().split()]
cs=sorted(c)
res[1]=cs.pop(-1)
def tree(i):
	for e in edge[i]:
		res[e]=cs.pop(-1)
	for e in edge[i]:
		tree(e)
tree(1)
print(sum(c)-max(c))
print(" ".join(map(lambda x:str(x),res[1:])))

Submission status: Wrong Answer

Solution code:
N=int(input())
edge=[[] for i in range(N+1)]
res=[0 for i in range(N+1)]
for i in range(N-1):
	a,b=[int(i) for i in input().split()]
	edge[min(a,b)].append(max(a,b))
c=[int(i) for i in input().split()]
cs=sorted(c)
res[1]=cs.pop(-1)
def tree(i):
	for e in edge[i]:
		res[e]=cs.pop(-1)
		tree(e)
tree(1)
print(sum(c)-max(c))
print(" ".join(map(lambda x:str(x),res[1:])))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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)


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

while child:
    #print(child,cnt,c[cnt])
    pi = int(child.pop())
    d[pi-1] = (c[cnt])
    ans += c[cnt]
    if al[pi]:
        child = child + al[pi]
    cnt += 1
    
print(ans)
print(' '.join(map(str,d)))

Submission status: Wrong Answer

Solution code:
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
# visual studio code shortcut https://qiita.com/TakahiRoyte/items/cdab6fca64da386a690b
# delete line: Ctrl+Shift+k
# choose same words: Ctrl+Shift+l
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

from itertools import combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def combinations_count(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(r))
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)
# set the inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
    # R = lambda: map(int, input().split()) :it's fashionable, isn't it?
    # ex1) n, k = R()
    # ex2) v = list(R())
    # ex3) bc = [list(R()) for i in range(m)]

# n = 9
# ab = [[8,7],[1, 2],[8, 9],[2, 3],[3, 4],[4, 5],[1, 6], [7, 3]]
# c = [1, 21, 3, 15, 600, 5, 8, 4, 8000]
# c.sort(reverse=True)

R = lambda: list(map(int, input().split()))
n = int(input())
ab = [R() for i in range(n-1)]
c = R()
# c = sorted(c, reverse = True)
c.sort(reverse=True)

# calculate
dic = {}
l = deque()
for a, b in ab:
    if a >= b:
        a, b = b, a
    dic.setdefault(a, []).append(b)

m = sum(c) - max(c)
d = [-1] * n
l.extend(dic[1])
d[0] = c[0]
i = 1
while l:
    deq = l.popleft()
    if deq in dic:
        l.extend(dic[deq])
    d[deq-1] = c[i]
    i += 1
print(m)
print(*d)

Submission status: Wrong Answer

Solution code:
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
# visual studio code shortcut https://qiita.com/TakahiRoyte/items/cdab6fca64da386a690b
# delete line: Ctrl+Shift+k
# choose same words: Ctrl+Shift+l
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

from itertools import combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def combinations_count(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(r))
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)
# set the inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
    # R = lambda: map(int, input().split()) :it's fashionable, isn't it?
    # ex1) n, k = R()
    # ex2) v = list(R())
    # ex3) bc = [list(R()) for i in range(m)]

# n = 9
# ab = [[8,7],[1, 2],[8, 9],[2, 3],[3, 4],[4, 5],[1, 6], [7, 3]]
# c = [1, 21, 3, 15, 600, 5, 8, 4, 8000]
# c.sort(reverse=True)

R = lambda: list(map(int, input().split()))
n = int(input())
ab = [R() for i in range(n-1)]
c = R()
# c = sorted(c, reverse = True)
c.sort(reverse=True)

# calculate
dic = {}
l = deque()
for a, b in ab:
    if a >= b:
        a, b = b, a
    dic.setdefault(a, []).append(b)

m = sum(c) - max(c)
d = [0] * n
l.extend(dic[1])
d[0] = c[0]
i = 1
while l:
    deq = l.pop()
    if deq in dic:
        l.extend(dic[deq])
    d[deq-1] = c[i]
    i += 1
print(m)
print(*d)

Submission status: Wrong Answer

Solution code:
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
# visual studio code shortcut https://qiita.com/TakahiRoyte/items/cdab6fca64da386a690b
# delete line: Ctrl+Shift+k
# choose same words: Ctrl+Shift+l
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

from itertools import combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def combinations_count(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(r))
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)
# set the inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
    # R = lambda: map(int, input().split()) :it's fashionable, isn't it?
    # ex1) n, k = R()
    # ex2) v = list(R())
    # ex3) bc = [list(R()) for i in range(m)]

R = lambda: list(map(int, input().split()))
n = int(input())
ab = [R() for i in range(n-1)]
c = R()
# c = sorted(c, reverse = True)
c.sort(reverse=True)

# calculate
dic = {}
l = deque()
for a, b in ab:
    if a >= b:
        a, b = b, a
    dic.setdefault(a, []).append(b)

m = sum(c) - max(c)
d = [0] * n
l.extend(dic[1])
d[0] = c[0]
i = 1
while l:
    deq = l.popleft()
    if deq in dic:
        l.extend(dic[deq])
    d[deq-1] = c[i]
    i += 1
print(m)
print(*d)

Submission status: Wrong Answer

Solution code:
n = int(input())
path = [[x, 0] for x in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    path[a-1][1] += 1
    path[b-1][1] += 1
c = list(map(int, input().split()))
c.sort(reverse=True)
path.sort(key=lambda x:x[1], reverse=True)
result = [-1 for _ in range(n)]
for x in range(len(c)):
    result[path[x][0]] = c[x]

large = max(c)
c.remove(large)
print(sum(c))
print(' '.join([str(v) for v in result]))

Submission status: Wrong Answer

Solution code:
n = int(input())
path = []
for _ in range(n - 1):
    a, b = map(int, input().split())
    path.append((a,b))
c = list(map(int, input().split()))
c.remove(max(c))
print(sum(c))

Submission status: Wrong Answer

Solution code:
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
# visual studio code shortcut https://qiita.com/TakahiRoyte/items/cdab6fca64da386a690b
# delete line: Ctrl+Shift+k
# choose same words: Ctrl+Shift+l
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

from itertools import combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def combinations_count(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(r))
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)
# set the inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
    # R = lambda: map(int, input().split()) :it's fashionable, isn't it?
    # ex1) n, k = R()
    # ex2) v = list(R())
    # ex3) bc = [list(R()) for i in range(m)]

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

# n = 5
# ab = [[1, 2],[2, 3],[3, 4],[4, 5]]
# c = [1, 2, 3, 4, 5]

# calculate
dic = {}
l = deque()
for a, b in ab:
    if a >= b:
        a, b = b, a
    dic.setdefault(a, []).append(b)

m = sum(c) - max(c)
d = [0] * n
l.extend(dic[1])
d[0] = c[0]
i = 1
while l:
    deq = l.popleft()
    if deq in dic:
        l.extend(dic[deq])
    d[deq-1] = c[i]
    i += 1
print(m)
print(*d)

Submission status: Wrong Answer

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

c.sort()

d = [0] * (N)

import collections

COL = collections.Counter(a+b)
countlist = COL.most_common()
countlist.reverse()
for i in range(N):
    d[countlist[i][0]-1] = c[i]
    
M = 0

for i in range(N-1):
    M += min(d[a[i]-1],d[b[i]-1])
    
print(M)
print(' '.join(map(str,d)))

Submission status: Wrong Answer

Solution code:
n=int(input())
ab=[[int(i) for i in input().split()]for i in range(n-1)]
c=[int(i) for i in input().split()] 
hen=[10**5+1 for i in range(n)]
for a,b in ab:
    hen[a-1]=min(c[a-1],c[b-1],hen[a-1])
    hen[b-1]=min(c[a-1],c[b-1],hen[b-1])
x=hen.index(min(hen))
hen[x]=0
print(sum(hen))
hen[x]=max(c)
print(' '.join([str(i) for i in hen]))

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = [[int(_) for _ in input().split()] for _ in range(N-1)]
c = [int(_) for _ in input().split()]
c = sorted(c)
connectnum = []
for i in range(N+1):
    connectnum.append([0, 0, i])

for i in ab:
    connectnum[i[0]][0] += 1
    connectnum[i[1]][0] += 1

connectnum = sorted(connectnum)
for i in range(1, N+1):
    connectnum[i][1] = c[i-1]

connectnum = sorted(connectnum, key = lambda x: x[2])

print(sum(c[:-1]))
for i in range(1, N+1):
    print(connectnum[i][1], end = ' ')

Submission status: Wrong Answer

Solution code:
n = int(input())

adjacent = [[0] for i in range(n)]
tips = [0] * n
query = []
ans = 0

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

c = list(map(int, input().split()))
c.sort()
ans = sum(c) - max(c)

for i in adjacent:
    for j in i:
        if tips[j] == 0:
            tips[j] = c.pop()

print(ans)

for i in tips:
    print("{} ".format(i), end = "")

print("\n")

Submission status: Wrong Answer

Solution code:
n = int(input())

adjacent = [[0] for i in range(n)]
tips = [0] * n
query = []
ans = 0

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

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

for i in adjacent:
    for j in i:
        if tips[j] == 0:
            tips[j] = c.pop()

print(ans)

for i in tips:
    print("{} ".format(i), end = "")

print("\n")

Submission status: Wrong Answer

Solution code:
from collections import deque

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.sort(reverse=True)

ans=0 
used=[0]*(N+1)
number=[0]*(N+1)
que=deque([1])
used[1]=1

ccount=0
while que:
  v=que.popleft()
  if number[v]==0:
    number[v]=c[ccount]
    ccount+=1
  for e in G[v]:
    if used[e]:
      continue
    if number[e]==0:
      number[e]=c[ccount]
      ccount+=1
    ans+=min(number[v],number[e])
print(ans)
print(*number[1:])

Submission status: Wrong Answer

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 = [0]
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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000)

def add_node_2_tree_dic(tree_dic, x, y):
    if x not in tree_dic:
        tree_dic[x] = [y]
    else:
        tree_dic[x].append(y)

#   深さ優先探索で行けそう

N = int(input())
tree_dic = {}
for _ in range(N-1):
    a, b = map(int, input().split())
    add_node_2_tree_dic(tree_dic, a, b)
    add_node_2_tree_dic(tree_dic, b, a)

c_lst = list(map(int, input().split()))
c_lst.sort()
ans_lst = [0]*N

def search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst):
    next_node_lst = tree_dic[current_node][:]

    for next_node in next_node_lst:
        c = c_lst.pop()
        ans += c
        ans_lst[next_node - 1] = c

        tree_dic[current_node].remove(next_node)    #   今回通った枝を取り払う
        tree_dic[next_node].remove(current_node)

        if len(tree_dic[current_node]) == 0:
            del tree_dic[current_node]#   探索し終えたノードの削除
        if len(tree_dic[next_node]) == 0:
            del tree_dic[next_node]#   探索し終えたノードの削除
        else:   #   次のノードにつながっている辺があるとき
            try:
                ###################   この行でランタイムエラーが発生する    #######################
                ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)

            except:
                print("saiki error happened !")

    return ans


ans = 0
current_node = 1
ans_lst[0] = c_lst.pop()
ans = search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst)


ans_str = ""
for i in range(N):
    ans_str += str(ans_lst[i])
    if i != N - 1:
        ans_str += " "


print(ans)
print(ans_str)

#   解いてたらパフォーマンスが 500 → 1200 だった問題　テストケース25個中23個通って、2個通らなかった
#   M-SOLUTIONS プロコンオープン　AtCoder 屈辱の記憶