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 sys
sys.setrecursionlimit(10**6)

def dfs(v, p):
    for next in link[v]:
        if next == p:
            continue
        res[next] = min(c[v], c[next])
        dfs(next, v)

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

dfs(0, -1)

print(sum(res))
print(*c)

Submission status: Wrong Answer

Solution code:
import heapq as hq

N = int(input())
adj = [set() for _ in range(N)]
deg = [0]*N

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

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

assigned = [None]*N
score = 0
cnt = 0

Q = [(d,i) for i,d in enumerate(deg)]
hq.heapify(Q)

while C:
    nd, v = hq.heappop(Q)
    d = deg[v]
    if nd != d:
        hq.heappush(Q,(d, v))
        continue

    c = C.pop()
    assigned[v] = c
    score += c*d
    deg[v] = 0
    for u in adj[v]:
        deg[u] -= 1
        adj[u].discard(v)

print(score)
print(*assigned)

Submission status: Wrong Answer

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

ans = 0
for i in range(N-1):
    ans += min(c[a[i]-1], c[b[i]-1])

print(ans)
print(*c)

Submission status: Wrong Answer

Solution code:
#n,m=map(int,input().split())
n=int(input())
g=[[] for i in range(1+n)]
v=[0]*(1+n)
p=[0]*(1+n)
for i in range(n-1):
    a,b=map(int,input().split())
    g[a].append(b)
    g[b].append(a)
c=[int(i) for i in input().split()]

c.sort()
g.sort(key=lambda x:len(x))
for i in range(n,0,-1):
    if v[i]==0:
        p[i]=c.pop()
        v[i]=1
        for j in g[i]:
            if v[j]==0:
                p[j]=c.pop()
                v[j]=1

def dfs(q):
    rt=0
    r=[]
    while q:
        c=q.pop()
        r.append(c)
        v[c]=1
        for i in g[c]:
            rt+=min(p[i],p[c])
        for i in g[c]:
            if v[i]==0:
                q.append(i)
    return rt
        
v=[0]*(1+n)
ans=dfs([1])
print(ans,g)
print(p)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

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

for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    neighbors[a].append(b)
    neighbors[b].append(a)
c = list(map(int, input().split()))
sorted_c = sorted(c)
max_c = sorted_c[-1]
max_c_pos = c.index(max_c)

while True:
    q = deque()
    q.append(0)
    M = 0
    closed = [0 for _ in range(N)]
    while len(q) > 0:
        parent = q.pop()
        closed[parent] = c[parent]
        for neighbor in neighbors[parent]:
            if closed[neighbor] == 0:
                c2 = c[parent]
                c1 = c[neighbor]
                w = c1 if c1 < c2 else c2
                M += w
                q.append(neighbor)
    closed[parent] = c[parent]
    if closed[parent] == max_c:
        break
    else:
        tmp = c[parent]
        c[parent] = max_c
        c[max_c_pos] = tmp

print(M)
print(*closed)

Submission status: Wrong Answer

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

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

count = 0
maxCount = 0
maxList = []

for c in itertools.permutations(cs):
    print(c)
    for node in nodes:
        if(c[node[0]-1] < c[node[1]-1]):
            count = count + c[node[0]-1]
        else:
            count = count + c[node[1]-1]
    if(count >= maxCount):
        print("flag")
        maxCount = count
        maxList = c
    count = 0

print(maxCount)
print(' '.join(map(str, maxList)))

Submission status: Wrong Answer

Solution code:
n = int(input())
adj = [[i,0] for i in range(n+1) ]
adj_path = []
for _ in range(n-1):
    a,b = map(int,input().split())
    adj_path.append([a,b])
    adj[a][1] += 1
    adj[b][1] += 1
c_list = sorted(list(map(int,input().split())),reverse=True)
out = [0 for i in range(n+1)]

if len(adj_path) == 0:
    print(0)
else:
    for i,[name,rank] in enumerate(sorted(adj,key=lambda x:x[1],reverse=True)):
        if name != 0:
            out[name] = c_list[i]
    score = 0
    for a,b in adj_path:
        score += min(out[a],out[b])
    print(score)
    print(" ".join(str(x) for x in out[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()))
side_num = [[0,i] for i in range(N)]
ans = 0
for a,b in ab:
    side_num[a-1][0] +=1
    side_num[b-1][0] +=1

side_num.sort(reverse=True)
c.sort(reverse=True)
for i in range(N):
    side_num[i][0] = c[i]

for a,b in ab:
    ans += min(side_num[a-1][0], side_num[b-1][0])
print(ans)
side_num.sort(key=lambda x:x[1])
for i in range(N):
    print(side_num[i][0],end=" ")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque

N=input()

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

for _ in range(N-1):
	a,b=map(int, sys.stdin.readline().split())
	nl[a].append(b)
	nl[b].append(a)


C=map(int, sys.stdin.readline().split())
C.sort(reverse=True)
C=deque(C)


start=None
max_nl_cnt=0
for i in range(1,N+1):
	nl_cnt=len( nl[i] )
	if max_nl_cnt < nl_cnt:
		start=i
		max_nl_cnt=nl_cnt

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

q=deque()
q.append(start)
val=C.popleft()
Visit[start]=val

 
while q:
	x=q.popleft()
	for to in nl[x]:
		if Visit[to] is None:
			val=C.popleft()
			Visit[to]=val
			q.append(to)

		
print sum(Visit[1:])
for x in Visit[1:]:
	print x,

Submission status: Wrong Answer

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

def ab(i):
    global c,l,x
    while len(l[i])>0:
        try:
            x[l[i][0]]=c.pop(0)
            l[l[i][0]].remove(i)
            ab(l[i][0])
            l[i].pop(0)
        except:
            break
    return

n=int(input())
l = [[] for _ in range(n+1)]
for i in range(n-1):
    a,b=intinput()
    l[a].append(b)
    l[b].append(a)
c = list(intinput())
c.sort(reverse=1)
x = [0 for _ in range(n+1)]
x[1]=c.pop(0)
for i in range(1,n+1):
    ab(i)
print(sum(x[2:]))
f = ""
q= len(x[1:])
for i in range(q):
    if i != q-1:
        f += str(x[i+1])+" "
    else:
        f += str(x[i+1])
print(f)

Submission status: Wrong Answer

Solution code:
from collections import*
n=int(input())
d=defaultdict(list)
s=set(range(1,n+1))

for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    s-={b}
p=sorted(map(int,input().split()))

def DFS(point,TFlist):
    global ans
    global score
    if all(TFlist):
        return 1
    for i in d[point]:
        if TFlist[i-1]:
            continue
        TFlist[i-1]=True
        tmp=p.pop()
        ans[i-1]=tmp
        score.append(tmp)
        #print(score)
        DFS(i,TFlist)
        TFlist[i-1]=False
    return score,ans


start=0
TFlist=[False]*(n)
TFlist[0]=True
ans=[0 for i in range(n)]
score=[]
ans[start]=p.pop()
s,t=DFS(start+1,TFlist)
#print(d)
print(sum(s))
print(*t)

Submission status: Wrong Answer

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

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

count_arr = collections.Counter(h_arr)
c_key = list(count_arr.keys())
c_value = list(count_arr.values())
c_list = []
for i in range(N):
    c_list.append([c_value[i], c_key[i]])

c_list.sort()


c_arr = sorted(c_arr)

for i in range(N):
    c_list[i].append(c_arr[i])

c_list.sort(key=lambda x: x[1])

print(sum(c_arr)-max(c_arr))
for i in range(N):
    print(c_list[i][2])

Submission status: Wrong Answer

Solution code:

N=int(input())
road_list = [[] for i in range(N)]

for i in range(N-1):
    a,b=list(map(int,input().split()))
    a=a-1
    b=b-1
    road_list[a].append(b)
    road_list[b].append(a)
c = list(map(int,input().split()))
from collections import deque
Q = deque([[0,0]])
ans = []
checked_list = [False for i in range(N)]
checked_list[0]=True
count_list = [10**9 for i in range(N)]
count_list[0] = 0

while len(Q)>0:
    v,count = Q.pop()
    count+=1
    for v1 in road_list[v]:        
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.append([v1,count])
            count_list[v1]=count

c.sort()

count_list = [[i,count_list[i]] for i in range(N)]
count_list = sorted(count_list, key=lambda x:x[0],reverse=True)
d = [[count_list[i][0],c[i]] for i in range(N)]
d = sorted(d, key=lambda x:x[0])
d = [d[i][1] for i in range(N)]
print(sum(c[:-1]))
print(*d)

Submission status: Wrong Answer

Solution code:
import heapq as hq

N = int(input())
adj = [set() for _ in range(N)]
deg = [0]*N

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

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

assigned = [None]*N
score = 0
cnt = 0

Q = [(d,i) for i,d in enumerate(deg)]
hq.heapify(Q)

while C:
    nd, v = hq.heappop(Q)
    d = deg[v]
    if nd != -d:
        hq.heappush(Q,(-d, v))
        continue

    c = C.pop()
    assigned[v] = c
    score += c*d
    deg[v] = 0
    for u in adj[v]:
        deg[u] -= 1
        adj[u].discard(v)

print(score)
print(*assigned)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

G = [[] for i in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)
    
C = deque(sorted([int(i) for i in input().split()], reverse = True))
    
Q = deque()
Q.append(N - 1)
order = []
visited = [False] * N
while len(Q) != 0:
    q = Q.popleft()
    visited[q] = True
    c = C.popleft()
    order.append([q, c])
    for g in G[q]:
        if visited[g] == False:
            Q.append(g)
        
ans = 0
visited2 = [False] * N
for i in range(N):
    visited2[i] = True
    for g in G[i]:
        if visited2[g] == False:
            ans += min(order[i][1], order[g][1])
        
print(ans)

sorted_order = sorted(order)
ans2 = []
for i in range(N):
    ans2.append(sorted_order[i][1])
    
print(' '.join(map(str, ans2)))

Submission status: Wrong Answer

Solution code:
n = int(input())
adj = [[i,0] for i in range(n+1) ]
adj_path = []
for _ in range(n-1):
    a,b = map(int,input().split())
    adj_path.append([a,b])
    adj[a][1] += 1
    adj[b][1] += 1
c_list = sorted(list(map(int,input().split())),reverse=True)
out = [0 for i in range(n+1)]

if len(adj_path) == 0:
    print(0)
else:
    for i,[name,rank] in enumerate(sorted(adj,key=lambda x:x[1],reverse=True)):
        if name != 0:
            out[name] = c_list[i]
    score = 0
    for a,b in adj_path:
        score += min(out[a],out[b])
    print(score)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
b = []
for i in range(n-1):
    A,B = map(int,input().split())
    a.append(A)
    b.append(B)
c = list(map(int,input().split()))
array = [0 for i in range(n)]

for i in range(n-1):
    array[a[i]-1] += 1
    array[b[i]-1] += 1
s =[]

for i in range(n):
    s.append(array.index(max(array)))
    array[s[i]] = 0
c.reverse()
for i in range(n):
    array[s[i]] =c[i]
m = []
for i in range(n-1):
    m.append(min(array[a[i]-1],array[b[i]-1]))
print(sum(m))
d = ""
for i in range(n):
    if i != n-1:
        d += str(array[i]) + " "
    else:
        d += str(array[i])
print(d)

Submission status: Wrong Answer

Solution code:
N=int(input())
edges_mat=[]
edges=[]
for _ in range(N):
	edges_mat.append([0]*N)

for _ in range(N-1):
	a,b = map(int,input().split())
	edges.append((a-1,b-1)) # 0-indexed
	edges_mat[a-1][b-1]=1
	edges_mat[b-1][a-1]=1
C = sorted(list(map(int,input().split())))
pinfo=[]

# その頂点から伸びる辺の数
for i in range(N):
	pinfo.append([i, sum(edges_mat[i])])
pinfo = sorted(pinfo, key=lambda x: x[1])

# 接続数の少ない頂点から順に小さい数字を振る
for i in range(N):
	pinfo[i].append(C[i])
pinfo = sorted(pinfo, key=lambda x: x[0])

# 合計値の出力
s = 0
for edge in edges:
	a,b = edge
	s += min(pinfo[a][2], pinfo[b][2])
print(s)

# 並び順
l = []
for p in pinfo:
	l.append(str(p[2]))
print(' '.join(l))

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from heapq import heappush, heappop
from collections import deque
from collections import defaultdict
N = int(input())
l = []
p = [0]*N
lp = [0]*(N)
d =defaultdict(list)
dd =defaultdict(int)
for i in range(N-1):
    ta ,tb = map(int,input().split())
    l.append([ta-1,tb-1])
    dd[ta-1]+=1
    dd[tb-1]+=1    
li = list(map(int,input().split()))


sd = sorted(dd.items(), key=lambda x:x[1], reverse=True)


li.sort()
li = li[::-1]
for m,(i , j) in enumerate(sd):
    lp[i] = li[m]
for i,j in l:
    d[i].append([j,lp[j]])
    d[j].append([i,lp[i]])
q = deque()
q.append(0)
p[0] = 1
c = lp[0]
ll = []
while q:
    if len(q) == 0:break
    t = q.pop()
    c = lp[t]
    p[t] = 1
    for i ,j in d[t]:
        if p[i] == 0:
            ll.append(min(c,j))
            q.appendleft(i)
print(sum(ll))
print(*lp)

Submission status: Wrong Answer

Solution code:
a = int(input())
d = {}
e = [0]*(a-1)
g = [0]*(a-1)
p = 0
for i in range(a-1):
  b,c = map(int,input().split())
  e[i] = [b,c]
  if not b in d.keys():
    d[b] = 1
  if not c in d.keys():
    d[c] = 1
  else:
    d[b] += 1
    d[c] += 1
d = sorted(d.items(), key=lambda x: x[1])
d = dict(d)
f = list(map(int,input().split()))
for j in d.keys():
  d[j] = f[p]
  p += 1
for t in range(a-1):
  g[t] = min(d[e[t][0]],d[e[t][1]])
print(sum(g))
d = sorted(d.items(), key=lambda x: x[0])
d = dict(d)
for l in d.values():
  print(l,end= ' ')

Submission status: Wrong Answer

Solution code:
N = int(input())

que = []
edges = {i:[] for i in range(1,N+1)}
ans = {i:None for i in range(1,N+1)}

while True:
  s = list(map(int,input().split()))
  if len(s) > 2: 
    break
  edges[s[0]].append(s[1])
s = sorted(s)
ans1 = sum(s[:-1])

que.append(1)

while que:
  temp = que.pop(0)
  ans[temp] = s.pop()
  que += edges[temp]

s = ""
for key in ans:
  if key>1:
    s+= " "
  s += str(ans[key])
print(ans1)
print(s)

Submission status: Wrong Answer

Solution code:
def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd_core(b, a % b)


def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g




n = int(input())
freq = [[i,0] for i in range(1,n+1)]
edges = {}
# for i in range(1,n+1):
#     edges[i] = []
for i in range(n-1):
    a,b = map(int,input().split())
    # edges[a].append(b)
    # edges[b].append(a)
    freq[a-1][1]+=1
    freq[b-1][1]+=1
c = list(map(int,input().split()))
c.sort()
ans_sum = sum(c[0:-1])
big = c[-1]
c = c[:-1]

freq.sort(key=lambda x:x[1])
root = freq[0][0]

# print(freq)
# print(c)
#print(edges)

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

for i in range(n):
    if i == 0:
        ans[freq[i][0]-1]=big
    else:
        ans[freq[i][0]-1] = c[i-1]
print(ans_sum)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
num_list = ['']*(n-1)
for i in range(n-1):
	num_list[i] = list(map(int, input().split()))
# print(num_list)
c_list = [0]*n
for i in range(n):
	for j in range(n-1):
		c_list[i] += num_list[j].count(i+1)
# print(c_list)

big_index = [0]*n
c_list_copy = c_list[:]
for i in range(n):
	print(c_list_copy)
	big_index[i] = c_list_copy.index(max(c_list_copy))
	c_list_copy[big_index[i]] = 0
	# print(c_list_copy[big_index[i]])

# print(big_index)

sss = list(map(int, input().split()))
sss.sort()
sss.reverse()
# print(sss)
ssr = [0]*n
for i in range(n):
	ssr[big_index[i]] = sss[i]
# print(ssr)

ans = 0
for i in range(n-1):
	ans += min(ssr[num_list[i][0]-1], ssr[num_list[i][1]-1])

print(ans)
print(ssr)

Submission status: Wrong Answer

Solution code:
#

import itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

def main():
    N = int(input())
    d = [0] * N
    multi = [0] * N

    edges = defaultdict(list)
    edges_l = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        d[a-1] += 1
        d[b-1] += 1
        multi[a-1] += 1
        multi[b-1] += 1

        edges_l.append((a-1, b-1))
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)

    for i in range(len(d)):
        d[i] = (d[i], i)  # 多重度、インデックス
    d.sort(key=lambda v: v[0], reverse=True)

    C = list(map(int, input().split()))
    C.sort(reverse=True)
    # print(d)
    # print(C)
    ans = [0] * N
    used = [False] * N
    i = 0
    count = 0
    while i < N and count < N:
        if not used[i]:
            # print('i = {}, Ci = {}'.format(i, C[i]))
            ans[d[i][1]] = C[count]
            used[i] = True

            count += 1
            if count == N:
                break

        # print(edges[i])
        neighbors = []
        for nei in edges[d[i][1]]:
            neighbors.append((nei, multi[nei]))  # 隣のノードと多重度

        neighbors.sort(key=lambda v: v[1], reverse=True)
        for neighbor, _ in neighbors:
            dd = d.index((multi[neighbor], neighbor))
            if not used[dd]:
                ans[neighbor] = C[count]
                used[dd] = True
                count += 1
                if count == N:
                    break
        i += 1

    # print(d)
    d.sort(key=lambda v: v[1])

    val = 0
    for a, b in edges_l:
        node_val = min(ans[a], ans[b])
        val += node_val

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[70]:


import sys
#input = sys.stdin.readline
N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]
c = list(map(int, input().split()))


# In[ ]:


"""
5
1 2
1 3
1 4
1 5
3141 59 26 53 59
"""


# In[76]:


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


# In[75]:


#sorted(c)[:-1]


# In[61]:


has_edges = [0]*N


# In[63]:


for i in range(N-1):
    a = ab[i][0]
    b = ab[i][1]
    has_edges[a-1] += 1
    has_edges[b-1] += 1


# In[64]:


ba = sorted(zip(has_edges, range(N)))


# In[68]:


ans = [0]*N
sc = sorted(c)
for i in range(N):
    #print(i)
    ans[ba[i][1]] = str(sc[i])
#print(ans)


# In[69]:


print(' '.join(ans))


# In[ ]:

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from heapq import heappush, heappop
from collections import deque
from collections import defaultdict
N = int(input())
l = []
p = [0]*N
lp = [0]*(N)
d =defaultdict(list)
dd =defaultdict(int)
for i in range(N-1):
    ta ,tb = map(int,input().split())
    l.append([ta-1,tb-1])
    dd[ta-1]+=1
    dd[tb-1]+=1    
li = list(map(int,input().split()))


sd = sorted(dd.items(), key=lambda x:x[1], reverse=True)


li.sort()
li = li[::-1]
for m,(i , j) in enumerate(sd):
    
    lp[i] = li[m]
for i,j in l:
    d[i].append([j,lp[j]])
    d[j].append([i,lp[i]])
q = deque()
q.append(0)
p[0] = 1
c = li[0]
ll = []
while q:
    if len(q) == 0:break
    t = q.pop()
    c = lp[t]
    p[t] = 1
    for i ,j in d[t]:
        if p[i] == 0:
            ll.append(min(c,j))
            q.appendleft(i)
print(sum(ll))
print(*lp)

Submission status: Wrong Answer

Solution code:
a = int(input())
d = {}
e = [0]*(a-1)
g = [0]*(a-1)
p = 0
for i in range(a-1):
  b,c = map(int,input().split())
  e[i] = [b,c]
  if not b in d.keys():
    d[b] = 1
  if not c in d.keys():
    d[c] = 1
  else:
    d[b] += 1
    d[c] += 1
print(d)
d = sorted(d.items(), key=lambda x: x[1])
d = dict(d)
print(d)
f = list(map(int,input().split()))
for j in d.keys():
  d[j] = f[p]
  p += 1
for t in range(a-1):
  g[t] = min(d[e[t][0]],d[e[t][1]])
print(sum(g))
d = sorted(d.items(), key=lambda x: x[0])
d = dict(d)
for l in d.values():
  print(l,end= ' ')

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
from heapq import heappush, heappop
from collections import deque
from collections import defaultdict
N = int(input())
l = []
p = [0]*N
lp = [0]*(N)
d =defaultdict(list)
dd =defaultdict(int)
for i in range(N-1):
    ta ,tb = map(int,input().split())
    l.append([ta-1,tb-1])
    dd[ta-1]+=1
    dd[tb-1]+=1    
li = list(map(int,input().split()))


sd = sorted(dd.items(), key=lambda x:x[1], reverse=True)


li.sort()
li = li[::-1]
for m,(i , j) in enumerate(sd):
    
    lp[i] = li[m]
for i,j in l:
    d[i].append([j,lp[j]])
    d[j].append([i,lp[i]])
q = deque()
q.append(0)
p[0] = 1
c = li[0]
ll = []
while q:
    if len(q) == 0:break
    t = q.pop()
    c = li[t]
    p[t] = 1
    for i ,j in d[t]:
        if p[i] == 0:
            ll.append(min(c,j))
            q.appendleft(i)
print(sum(ll))
print(*lp)

Submission status: Wrong Answer

Solution code:
def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd_core(b, a % b)


def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g




n = int(input())
freq = [[i,0] for i in range(1,n+1)]
edges = {}
# for i in range(1,n+1):
#     edges[i] = []
for i in range(n-1):
    a,b = map(int,input().split())
    # edges[a].append(b)
    # edges[b].append(a)
    freq[a-1][1]+=1
    freq[b-1][1]+=1
c = list(map(int,input().split()))
c.sort()
big = c[-1]
c = c[:-1]

freq.sort(key=lambda x:x[1])
root = freq[0][0]

print(freq)
print(c)
#print(edges)

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

for i in range(n):
    if i == 0:
        ans[freq[i][0]-1]=big
    else:
        ans[freq[i][0]-1] = c[i-1]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
INPUT = sys.stdin.readline

def SINGLE_INT(): return int(INPUT())
def NULTIPLE_INT_LIST(): return list(map(int, INPUT().split()))
def NULTIPLE_INT_NAP(): return map(int, INPUT().split())
def SINGLE_STRING(): return INPUT()
def NULTIPLE_STRING(): return INPUT().split()

class Node():
    def __init__(self, a,b):
        self.id = a
        self.marked = False
        self.adjacent = [b]
        self.n_adjacent = 1

    def add_edge(self, n):
        self.adjacent.append(n)
        self.n_adjacent += 1

N = SINGLE_INT()
leaf = set(range(N))
node = {}
node_marking = [0] * N

for _ in range(N-1):
    a, b = NULTIPLE_INT_NAP()
    a -= 1
    b -= 1

    if a in node:
        node[a].add_edge(b)
        try:
            leaf.remove(a)
        except:
            pass
    else:
        node[a] = Node(a,b)

    if b in node:
        node[b].add_edge(a)
        try:
            leaf.remove()
        except:
            pass
    else:
        node[b] = Node(b,a)

figures = NULTIPLE_INT_LIST()
figures.sort(reverse=True)
max_of_min = sum(figures[1:])

q = [(1, n) for n in leaf]

while figures:
    _, id = heapq.heappop(q)
    #print('visiting', id)

    visiting = node[id]

    if visiting.marked:
        continue

    visiting.marked = True
    node_marking[visiting.id] = figures.pop()

    for n in visiting.adjacent:
        adj = node[n]
        if not adj.marked:
            adj.n_adjacent -= 1
            heapq.heappush(q, (adj.n_adjacent, n))
            #print('added (', adj.n_adjacent, n, ')')

print(max_of_min)
print(' '.join(map(str, node_marking)))

Submission status: Wrong Answer

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

M = sum(C[:-1])

adjacent_dict={}
for a,b in AB:
  adjacent_dict.setdefault(a, set()).add(b)
  adjacent_dict.setdefault(b, set()).add(a)
  

leafs = []
adjacents = [0] * (N+1) # a[i]: 頂点i
for k, v in adjacent_dict.items():
  adjacents[k] = len(v)
  if len(v)==1:
    leafs.append(k)

nodes = leafs.copy() #小さい値を入れたい順のノード
visited = [0] * (N+1) # visited[i]: 頂点i
for n in nodes:
  visited[n] = 1
  
#while leafs:
#  next_leafs = set()
#  for l in leafs:
#    for u in adjacent_dict[l]:
#      acjacents[u] -= 1
#      next_leafs.add(u)
  
  
while leafs:
  new_stack = []
  for v in leafs:
    for u in adjacent_dict[v]:
      adjacents[u] -= 1
      if visited[u]==0:
        visited[u]=1
        new_stack.append(u)
  leafs = [v for v in new_stack if adjacents[v]==1]
  nodes.extend(leafs)
  if not leafs:
    nodes.extend(new_stack) #最後に隣接0のノードが残ったとき
    break
  for u in [v for v in new_stack if adjacents[v]!=0]:
    visited[u] = 0
    
  
ans = [0]*(N)
for i in range(N):
  ans[nodes[i]-1] = C[i]
  
print(M)
print(*ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[59]:


import sys
#input = sys.stdin.readline
N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]
c = list(map(int, input().split()))


# In[60]:


print(sum(sorted(list(c)[:-1])))


# In[61]:


has_edges = [0]*N


# In[63]:


for i in range(N-1):
    a = ab[i][0]
    b = ab[i][1]
    has_edges[a-1] += 1
    has_edges[b-1] += 1


# In[64]:


ba = sorted(zip(has_edges, range(N)))


# In[68]:


ans = [0]*N
sc = sorted(c)
for i in range(N):
    #print(i)
    ans[ba[i][1]] = str(sc[i])
#print(ans)


# In[69]:


print(' '.join(ans))


# In[ ]:

Submission status: Wrong Answer

Solution code:

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()


N = n()
M = 0
ds = [None] * N

ranks = [0] * N
for i in range(N-1):
    a, b = nl()
    ranks[a-1] += 1
    ranks[b-1] += 1
cs = sorted(nl())
M = sum(cs[:-1])

ranks = [[i, ranks[i]] for i in range(N)]
ranks = sorted(ranks, key=lambda r: r[1])

for i in range(N):
    ds[ranks[i][0]] = cs[i]

print(M)
print(' '.join([str(d) for d in ds]))

Submission status: Wrong Answer

Solution code:
N = int(input())

a = []
b=[]

for i in range(N-1):
    str = input().split()
    a.append(int(str[0]))
    b.append(int(str[1]))

str = input().split()
c = []
for i in range(N):
    c.append(int(str[i]))

c.sort()
SUM  = 0

for i in range(N-1):
    SUM = SUM + c[i]
    
print(SUM)

Submission status: Wrong Answer

Solution code:

import copy
import time
import random

arc_ = []


N = int(input())

len_l = 2
# N = 2 
while len_l == 2:
    line = input().split()
    len_l = len(line)
    if len_l == 2:
        arc_.append([int(line[0]), int(line[1])])
    else:
        c_ = [int(v) for v in line]
start = time.time()
      
max_value = 0
max_c = []

def get_result(arc, c_set):
    sum_v = 0
    for i in range(len(arc)):
        sum_v += min(c_set[arc[i][0]-1], c_set[arc[i][1]-1])
    return sum_v
  

while time.time() - start <= 1.9:
    random.shuffle(c_)
    sum_v = get_result(arc_, c_)
    if sum_v > max_value:
        max_value = sum_v
        max_c = copy.deepcopy(c_)


print(max_value)
print(' '.join([str(v) for v in max_c]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
connection = defaultdict(lambda: [])

n = int(input())

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

l = []
for i in range(1, n+1):
    l.append([i, len(connection[i])])

l.sort(key=lambda x: x[1])

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

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


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

print(score)
print(" ".join(map(str, c)))

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict

N = int(input())
ab = []
for i in range(N - 1):
    ab.append(tuple(map(int, input().split())))

c_list = list(map(int, input().split()))
c_list.sort()
c_que = deque(c_list)

out_cnt = defaultdict(int)
outs = defaultdict(list)
for a, b in ab:
    out_cnt[a - 1] += 1
    outs[a - 1].append(b - 1)


tar = defaultdict(lambda: 0)
out_cnt = sorted(out_cnt.items(), key=lambda x: -x[1])
for v, num in out_cnt:
    if len(c_que) == 0:
        continue
    if tar[v] != 0:
        continue
    q = c_que.pop()
    tar[v] = q
    for v2 in outs[v]:
        if tar[v2] != 0:
            continue
        q2 = c_que.pop()
        tar[v2] = q2

for i in range(N):
    if tar[i] == 0:
        q2 = c_que.pop()
        tar[i] = q2

ans = 0
for a, b in ab:
    a -= 1
    b -= 1
    ans += min(tar[a], tar[b])
print(ans)
for i in range(N):
    print(tar[i], end=" ")

Submission status: Wrong Answer

Solution code:
class Apex:

    def __init__(self, no):
        self.no = no
        self.count = 1
        self.value = 0


class Edge:

    def __init__(self, a, b):
        self.a = a
        self.b = b


N = int(input())
apexes = {}
edges = [0] * (N - 1)
for i in range(N - 1):
    a, b = list(map(int, input().split()))
    apex_a = apexes.get(a)
    if apex_a is None:
        apex_a = Apex(a)
        apexes[a] = apex_a
    else:
        apex_a.count += 1
    apex_b = apexes.get(b)
    if apex_b is None:
        apex_b = Apex(b)
        apexes[b] = apex_b
    else:
        apex_b.count += 1
    edge = Edge(apex_a, apex_b)
    edges[i] = edge

values = apexes.values()
values = list(values)
values.sort(key=lambda x: x.count, reverse=True)
c = list(map(int, input().split()))
c = sorted(c, reverse=True)

for i in range(N):
    values[i].value = c[i]

sumv = 0
for edge in edges:
    sumv += min(edge.a.value, edge.b.value)
print(sumv)
print(" ".join(map(str, c)))

Submission status: Wrong Answer

Solution code:
from operator import itemgetter, attrgetter

class Node:
    def __init__(self, No):
        self.No = No
        self.cnt = 0
        self.ans = 0

    def plus(self):
        self.cnt += 1
    def setAns(self, i):
        self.ans = i

    def __lt__(self, other):
        return self.cnt > other.cnt

N = int(input())
nodeList = []
for i in range(10001):
    nodeList.append(Node(i))

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

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

nodeList.sort()
cList.sort()
cList.reverse()

for i in range(N):
    nodeList[i].setAns(cList[i])
total = 0
for i in range(N-1):
    total += cList[i+1]

result = sorted(nodeList, key=attrgetter('No'))

print(total)
for i in range(N):
    print(result[i+1].ans, end=" ")
#    print(result[i+1].No, result[i+1].cnt, result[i+1].ans)