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:
from bisect import bisect
from heapq import heapify, heappush, heappop
N=int(input())
AB=[tuple(map(int, input().split())) for _ in range(N-1)]
C=sorted(map(int, input().split()), reverse=True)
G=[[] for _ in range(N)]
for a,b in AB:
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
D=sorted(((len(G[i]),i) for i in range(N)), reverse=True)
X=[0]*N
for j,(d,i) in enumerate(D):
    X[i]=C[j]
ans=0
for a,b in AB:
    ans+=min(X[a-1],X[b-1])
print(ans)
print(*X)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
tree = [set() for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    tree[a - 1].add(b - 1)
    tree[b - 1].add(a - 1)
C = sorted(list(map(int, input().split())))

ans = [0] * N

print(sum(C[:-1]))

ans[0] = C.pop()
ans[1] = C.pop()

d = deque([0, 1])
visited = {0, 1}
while d:
    x = d.pop()
    for new_x in tree[x]:
        if new_x not in visited:
            ans[new_x] = C.pop()
            d.append(new_x)
            visited.add(new_x)

print(*ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
count = [0]*n
D = [0]*n
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  count[a] += 1
  count[b] += 1
  T[a].append(b)
  
C = sorted(map(int, input().split()))
L = sorted([(j, i) for i, j in enumerate(count)], reverse=True)
for s, edge in L:
  D[edge] = C.pop()
  
M = 0
for i in range(n):
  for j in T[i]:
    M += min(D[i], D[j])
    
print(M)
print(*D)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

s = {}

cost = [-1]*(N+1)
p = 0
ans = 0
for v, l in sorted(V.items(),key=lambda x:-len(x[1])):
    if cost[v]==-1:
        cost[v] = c[p]
        p += 1

    for i in l:
        if cost[i]!=-1:continue
        cost[i] = c[p]
        s[(v, i)] = min(cost[i], cost[v])
        p += 1

print(sum(s.values()))
print(*cost[1:])

Submission status: Wrong Answer

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

n=int(input())
ab=[list(map(int,input().split())) for i in range(n-1)]
c=list(map(int,input().split()))
c.sort()
lst=[[i+1] for i in range(n)]
nodelst=[0]*n
ans=0
for i in range(n-1):
    a,b=ab[i]
    lst[a-1].append(b)
    lst[b-1].append(a)
# print(lst)
# lst.sort(key=lambda x: len(x))
lst2=sorted(lst, key=lambda x: len(x))
# # print(lst)
# for i in range(n):
#     nodelst[lst[i][0]-1]=c[i]
d=deque()
for i in range(n):
    if len(lst2[i])==2:
        d.append(lst2[i][0])
    else:
        break
# print(lst)
# print(lst2)
# print(d)
cnt=0
while d:
    tmp=d.popleft()-1
    if nodelst[tmp]==0:
        nodelst[tmp]=c[cnt]
        cnt+=1
        d+=lst[tmp][1:]
    else:
        pass
print(sum(c)-c[-1])
print(*nodelst)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)] # [[2,2,2,2],[1,1,1,1],[3,3,3,3]] 
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a = inp()
        a -= 1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    n = inp()
    g=[[] for _ in range(n)]
    ab = []
    for i in range(n-1):
        a,b = inpm()
        a -= 1
        b -= 1
        g[b].append(a)
        g[a].append(b)
        ab.append((a,b))
    cnt = [(len(g[i]),i) for i in range(n)]
    point = [0 for _ in range(n)]
    c = inpl()
    cnt.sort()
    c.sort()
    for i in range(n):
        point[cnt[i][1]] = c[i]
    ans = 0
    for i in range(n-1):
        a,b = ab[i]
        ans += min(point[a],point[b])
    print(ans)
    print(*point)    
 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

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


nl = [(i, list()) for i in range(N)]
for a, b in AB:
    _, x = nl[a - 1]
    x.append(b - 1)
    _, x = nl[b - 1]
    x.append(a - 1)
nl.sort(key=lambda x: len(x[1]), reverse=True)

C.sort(reverse=True)
ans = list()
for i, c in enumerate(C):
    idx, _ = nl[i]
    ans.append((idx, c))
ans.sort()
ans = list(map(lambda x: x[1], ans))

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

print(M)
print(' '.join([str(x) for x in ans]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
A = sorted([(a,len(G[a])) for a in G],key=lambda x:x[1],reverse=True)
C = sorted(list(map(int,input().split())),reverse=True)
B = [0 for _ in range(N+1)]
for i in range(N):
    a,_ = A[i]
    B[a] = C[i]
cnt = 0
hist = {(i,j):0 for i in range(1,N+1) for j in G[i]}
for i in range(1,N+1):
    for j in G[i]:
        if hist[(i,j)]==0:
            cnt += min(B[i],B[j])
            hist[(i,j)] = 1
            hist[(j,i)] = 1
print(cnt)
print(*B[1:])

Submission status: Wrong Answer

Solution code:
import sys
#import numpy as np

stdin = sys.stdin

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

N = ri()
nodes = [0] * (N+1)
for _ in range(N-1):
    a, b = rl()
    nodes[a] += 1
    nodes[b] += 1

C = rl()
C.sort(reverse=True)
l = []
for i in range(1, N+1):
    l.append((nodes[i], i))

l.sort(reverse=True)
answer = [0] * (N+1)
for i in range(1, N+1):
    answer[l[i-1][1]] = C[i-1]

print(sum(C[1:]))
print(*answer[1:])
# 02

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

depth = [0] * (N + 1)
q = deque()
for i, g in enumerate(graph):
  if len(g) == 1:
    depth[i] = 1
    q.append(i)
#print("q:", q)

while q:
  qq = q.popleft()
  for g in graph[qq]:
    if depth[g] == 0:
      depth[g] = depth[qq] + 1
      q.append(g)
#print("depth:", depth)

C.sort()
nd = []
for i in range(1, N + 1):
  nd.append([i, depth[i]])
nd.sort(key = lambda x: x[1])
for i in range(N):
  nd[i] = nd[i] + [C[i]]
#print(nd)

nd.sort()
answer = []
for i in range(N):
  answer.append(nd[i][2])
print(sum(answer) - max(answer))
print(*answer)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

depth = [0] * (N + 1)
q = deque()
for i, g in enumerate(graph):
  if len(g) == 1:
    depth[i] = 1
    q.append(i)
#print("q:", q)

while q:
  qq = q.popleft()
  for g in graph[qq]:
    if depth[g] == 0:
      depth[g] = depth[qq] + 1
      q.append(g)
#print("depth:", depth)

C.sort()
nd = []
for i in range(1, N + 1):
  nd.append([i, depth[i]])
nd.sort(key = lambda x: x[1])
for i in range(N):
  nd[i] = nd[i] + [C[i]]
#print(nd)

nd.sort()
answer = []
for i in range(N):
  answer.append(nd[i][2])
print(*answer)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
N = int(input())
Cts = [0] * N
for _ in range(N - 1):
    a, b = map(int, input().split())
    Cts[a - 1] += 1
    Cts[b - 1] += 1
Cs = list(map(int, input().split()))
Cs.sort()
for i in range(N):
    Cts[i] = (Cts[i], i)
Cts.sort()
As = [0] * N
for i in range(N):
    As[Cts[i][1]] = Cs[i]
print(sum(Cs) - max(Cs))
print(" ".join(map(str, As)))

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
N = int(input())
Cts = [0] * N
Ls = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    Cts[a - 1] += 1
    Cts[b - 1] += 1
    Ls.append((a - 1, b - 1))
Cs = list(map(int, input().split()))
Cs.sort()
for i in range(N):
    Cts[i] = (Cts[i], i)
Cts.sort()
As = [0] * N
for i in range(N):
    As[Cts[i][1]] = Cs[i]
M = 0
for a, b in Ls:
    M += min(As[a], As[b])
print(M)
print(" ".join(map(str, As)))

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys
import copy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n=inp()
    edge_num=[[0,i] for i in range(n)]
    ab=[]
    for _ in range(n-1):
        a,b=inpm()
        edge_num[a-1][0]+=1
        edge_num[b-1][0]+=1
        ab.append((a-1,b-1))
    edge_num.sort()
    c=inpl()
    c.sort()
    point = [0 for _ in range(n)]
    write = [0 for _ in range(n)]
    for i in range(n):
        write[edge_num[i][1]]=c[i]
    for i in range(n-1):
        point[i]=min(write[ab[i][0]],write[ab[i][1]])
    print(sum(point))
    print(*write)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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


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


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

ans = [""]*N
for i in range(N):
    ans[i] = str(d[i][0])
print(" ".join(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = [tuple(map(int, input().split())) for i in range(N-1)]
c = list(map(int, input().split()))
c.sort(reverse=True)
d = [[0, i] for i in range(N)]
g = [set() for i in range(N)]
for a, b in ab:
    d[a-1][0] += 1
    d[b-1][0] += 1
    g[a-1].add(b-1)
    g[b-1].add(a-1)
d.sort(reverse=True, key=lambda x: x[0])
for i in range(N):
    d[i][0] = c[i]


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

Submission status: Wrong Answer

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

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

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

q.appendleft(1)

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

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

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

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

m = sum(c_arr) - max(c_arr)
ans = [0]*(n + 1)
a,b = edge.pop()
ans[a] = c_arr.pop()
ans[b] = c_arr.pop()
uf = UnionFind(n)
uf.union(a,b)
while edge:
    for i in range(len(edge)):
        if uf.same_check(a,edge[i][0]):
            if not uf.same_check(a,edge[i][1]):
                ans[edge[i][1]] = c_arr.pop()
                uf.union(edge[i][0],edge[i][1])
                edge.pop(i)
                break
        elif uf.same_check(a,edge[i][1]):
            ans[edge[i][0]] = c_arr.pop()
            uf.union(edge[i][0],edge[i][1])
            edge.pop(i)
            break
print(m)
print(*ans[1:])

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

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

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

m = sum(c_arr) - max(c_arr)
ans = [0]*(n + 1)
a,b = edge.pop()
ans[a] = c_arr.pop()
ans[b] = c_arr.pop()
uf = UnionFind(n)
uf.union(a,b)
while edge:
    for i in range(len(edge)):
        if uf.same_check(a,edge[i][0]):
            if not uf.same_check(a,edge[i][1]):
                ans[edge[i][1]] = c_arr.pop()
                uf.union(edge[i][0],edge[i][1])
                edge.pop(i)
                break
        elif uf.same_check(a,edge[i][1]):
            ans[edge[i][0]] = c_arr.pop()
            uf.union(edge[i][0],edge[i][1])
            edge.pop(i)
            break
print(*ans[1:])

Submission status: Wrong Answer

Solution code:
n = int(input())
edge = []
for i in range(n-1):
    edge.append(list(map(int,input().split())))

c_arr = sorted(list(map(int,input().split())))
m = sum(c_arr) - max(c_arr)
n_in = [[i,0] for i in range(n)]
ans = [0]*n
for a,b in edge:
    n_in[a-1][1] += 1
    n_in[b-1][1] += 1
n_in.sort(key = lambda x:x[1])
for [i,j],k in zip(n_in,range(n)):
    ans[i] = c_arr[k]
print(m)
print(*ans)

Submission status: Wrong Answer

Solution code:
def main():

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
G = [ set() for _ in range(n+1) ]
s = []
for _ in range(n-1):
  a, b = map(int, input().split())
  G[a].add(b)
  G[b].add(a)
  s.append({a, b})
l = [ [i, G[i]] for i in range(n+1) ]
l.sort(key=lambda x:len(x[1]))
C = sorted(list(map(int, input().split())))
seen = [False]*n
ans = 0
d = [0]*(n+1)
for i in range(1, n+1):
  d[l[i][0]] = str(C[i-1])
  temp = 0
  for j in l[i][1]:
    if not seen[s.index({l[i][0], j})]:
      seen[s.index({l[i][0], j})] = True
      temp += 1
  ans += C[i-1]*temp
print(ans)
print(" ".join(d[1:]))

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[]
for i in range(n+1):
    l.append([0,i])
ab=[]
for i in range(n-1):
    a,b=[int(j) for j in input().split()]
    l[a][0]+=1
    l[b][0]+=1
    ab.append((a,b))
l.sort()
l.reverse()
c=[int(j) for j in input().split()]
c.sort()
c.reverse()
for i in range(n):
    l[i][0]=c[i]
from operator import itemgetter
l.sort(key=itemgetter(1)) 
ans=0
d=[]
for i,j in l[1:]:
    d.append(i)
for i,j in ab:
    ans+=min(l[i][0],l[j][0])

print(ans)
print(*d)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[]
for i in range(n+1):
    l.append([0,i])
ab=[]
for i in range(n-1):
    a,b=[int(j) for j in input().split()]
    l[a][0]+=1
    l[b][0]+=1
    ab.append((a,b))
l.sort()
l.reverse()
c=[int(j) for j in input().split()]
c.sort()
c.reverse()
for i in range(n):
    l[i][0]=c[i]
from operator import itemgetter
l.sort(key=itemgetter(1)) 
ans=0
d=[]
print(l)
for i,j in l[1:]:
    d.append(i)
for i,j in ab:
    ans+=min(l[i][0],l[j][0])

print(ans)
print(*d)

Submission status: Wrong Answer

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

print(sum(sorted(num_list[:-1])))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
E = [list(map(lambda x: int(x)-1,input().split())) for _ in range(N-1)]
C = sorted(list(map(int,input().split())))

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

VC = []
for i in range(N):
  VC.append((len(V[i]),i))
VC.sort()

A = [0 for _ in range(N)]
for i in range(N):
  A[VC[i][1]] = C[i]

print(sum(C[:-1]))
print(*A)

Submission status: Wrong Answer

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()
while len(q)>0:
    s=q.pop()
    for i in g[s]:
        if v[i]==0:
            v[i]=1
            ans[i]=c.pop()
            q.append(i)
print(sum(ans)-max(ans))
print(*ans)

Submission status: Wrong Answer

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(n*(n-1)//2)
for i in range(n):
  ans[i]=str(c[ans[i]])
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
G = {}
for _ in range(N-1):
    a,b = map(int,input().split())
    if a not in G:
        G[a] = []
    G[a].append(b)
    if b not in G:
        G[b] = []
    G[b].append(a)
rank = []
for a in G:
    rank.append((a,len(G[a])))
rank = sorted(rank,key=lambda x:x[1])
C = sorted(list(map(int,input().split())),reverse=True)
A = {}
for i in range(N):
    A[rank[i][0]]=C.pop()
F = {}
for a in G:
    F[a] = []
    for b in G[a]:
        F[a].append((b,min(A[a],A[b])))
cnt = 0
for a in F:
    for b in F[a]:
        cnt += b[1]
print(cnt//2)
B = sorted(list(A.items()),key=lambda x:x[0])
B1 = [B[i][1] for i in range(N)]
print(*B1)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
N = int(input())
node = [[i,0] for i in range(N)]
D = [0] * N
for i in range(N-1):
  a,b = map(int,input().split())
  node[a-1][1] += 1
  node[b-1][1] += 1
d = sorted(list(map(int,input().split())))[::-1]
node.sort(key=itemgetter(1),reverse=True)
for i in range(N):
  D[node[i][0]] = d[i]
tmp = D[0]
ans = 0
for i in range(1,N):
  ans += min(tmp,D[i])
  tmp = D[i]
print(ans)
print(*D)

Submission status: Wrong Answer

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

c.sort(reverse=True)
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: Wrong Answer

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

VC = []
for i in range(N):
  VC.append([i+1,0])
for e1,e2 in E:
  VC[e1-1][1] += 1
  VC[e2-1][1] += 1
#print(VC)

VC.sort(key=lambda x:(x[1],x[0]))
#print(VC)
C.sort()
D = []
for i in range(N):
  D.append([VC[i][0],C[i]])
D.sort()
#print(D)
M = 0
for e1,e2 in E:
  M += min(D[e1-1][1],D[e2-1][1])
print(M)
ans = []
for _,c in D:
  ans.append(c)
print(*ans)

Submission status: Wrong Answer

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

VC = []
for i in range(N):
  VC.append([i+1,0])
for e1,e2 in E:
  VC[e1-1][1] += 1
  VC[e2-1][1] += 1
#print(VC)

VC.sort(key=lambda x:(x[1],x[0]))
#print(VC)
C.sort()
D = []
for i in range(N):
  D.append([VC[i][0],C[i]])
D.sort()
print(D)
M = 0
for e1,e2 in E:
  M += min(D[e1-1][1],D[e2-1][1])
print(M)
ans = []
for _,c in D:
  ans.append(c)
print(*ans)

Submission status: Wrong Answer

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

VC = []
for i in range(N):
  VC.append([i+1,0])
for e1,e2 in E:
  VC[e1-1][1] += 1
  VC[e2-1][1] += 1
#print(VC)

VC.sort(key=lambda x:(x[1],x[0]))
#print(VC)
C.sort()
D = []
for i in range(N):
  D.append([VC[i],C[i]])
D.sort()
M = 0
for e1,e2 in E:
  M += min(D[e1-1][1],D[e2-1][1])
print(M)
ans = []
for _,c in D:
  ans.append(c)
print(*ans)

Submission status: Wrong Answer

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, cnt)])

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

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


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

Submission status: Wrong Answer

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
que = deque([1])
cnt = 0

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

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


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

Submission status: Wrong Answer

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()
c.reverse()
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[0])
print(' '.join(ans))

Submission status: Wrong Answer

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)]
checked = [False for _ in range(N)]
stack = es[0]
cnt_c = 0
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)