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 itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

def main():
    N = int(input())
    d = [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

        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)
    used = [False] * N
    i = 0
    count = 0
    while i < N and count < N:
        if not used[i]:
            # print('i = {}, Ci = {}'.format(i, C[i]))
            d[i] = (C[count], d[i][1])
            used[i] = True

            count += 1
            if count == N:
                break

        # print(edges[i])
        for neigbor in edges[i]:
            if not used[neigbor]:
                d[neigbor] = (C[count], d[neigbor][1])
                used[neigbor] = True
                count += 1
                if count == N:
                    break
        i += 1

    # print(d)
    d.sort(key=lambda v: v[1])
    ans = [v[0] for v in d]

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


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

res = []
queue = deque([i for i in range(N) if in_cnt[i] == 0])
while len(queue) != 0:
    v = queue.popleft()
    res.append(v)
    for v2 in outs[v]:
        in_cnt[v2] -= 1
        if in_cnt[v2] == 0:
            queue.append(v2)

tar = defaultdict(int)

for r in res:
    if len(outs[r]) == 0:
        q = c_que.popleft()
        tar[r] = q
    else:
        q = c_que.pop()
        tar[r] = q


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:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))

q = int(input())

k = [[i,0]for i in range(q)]
aa = []
for i in range(q-1):
	a,b  = m()
	k[a-1][1] += 1
	k[b-1][1] += 1
	aa.append([a,b])
k.sort(key = lambda x:x[1],reverse = True)
c  = l()
c.sort(reverse = True)
for i in range(q):
	k[i][1] = c[i]

k.sort()
su = 0
for i in range(q-1):
	su += min(k[aa[i][0]-1][1],k[aa[i][1]-1][1])

print(su)
for i in range(q-1):
	print(k[i][1],end = " ")
print(k[-1][1])

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
g = [[0,[]] for i in range(n)]

for i in range(n-1):
  a,b = na()
  g[a-1][0] += 1
  g[a-1][1].append(b-1)
  g[b-1][0] += 1
  g[b-1][1].append(a-1)

gg = [[0,i] for i in range(n)]

for i in range(n):
  gg[i][0] = g[i][0]
  for j in g[i][1]:
    gg[i][0] += g[j][0]

c = na()
c.sort()
gg.sort()

p = [0]*n

for i in range(n):
  p[gg[i][1]] = c[i]

print(sum(c)-c[-1])
print(' '.join([str(v) for v in p]))

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = []
for _ in range(N-1):
    ab.append([int(i) for i in input().split()])
ab = sorted(ab)
c = [int(i) for i in input().split()]
c = sorted(c,reverse=True)
ans = 0
for abi in ab:
    a_temp = c[abi[0]-1]
    b_temp = c[abi[1]-1]
    ans += min(a_temp,b_temp)
print(ans)
print(c)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import*
n=int(input())
d=defaultdict(list)
s=set(range(1,n+1))
ans=[0 for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    s-={b}
p=sorted(map(int,input().split()))
score=0
def dfs(point):
    global score
    for i in d[point]:
        tmp=p.pop()
        ans[i-1]=tmp
        score+=tmp
        dfs(i)


ans[list(s)[0]-1]=p.pop()
dfs(list(s)[0])
print(score)
print(*ans)

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

    edges = defaultdict(list)
    edges_l = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        d[a-1] += 1
        d[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)
    used = [False] * N
    i = 0
    count = 0
    while i < N and count < N:
        if not used[i]:
            # print('i = {}, Ci = {}'.format(i, C[i]))
            d[i] = (C[count], d[i][1])
            used[i] = True

            count += 1
            if count == N:
                break

            # print(edges[i])
            for neigbor in edges[i]:
                if not used[neigbor]:
                    d[neigbor] = (C[count], d[neigbor][1])
                    used[neigbor] = True
                    count += 1
                    if count == N:
                        break
        i += 1

    # print(d)
    d.sort(key=lambda v: v[1])
    ans = [v[0] for v in d]

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

d = [0] * (N)
import collections

COL = collections.Counter(a+b)
countlist = COL.most_common()

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

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
ab = [[int(_) for _ in input().split()] for _ in range(N - 1)]
c = [int(_) for _ in input().split()]
c.sort(reverse=True)

AB = []
ans = [0] * N
for a, b in ab:
    AB += a, b

counterAB = Counter(AB)

val, count = zip(*counterAB.most_common())
for i, v in enumerate(val):
    ans[v - 1] = c[i]

cnt = 0
for A, B in ab:
    cnt += min(ans[A - 1], ans[B - 1])

print(cnt)
print(" ".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
N = int(input())
G = [[] for i in range(N)]
deg = [0] * N
E = []
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)
    E.append((a, b))
    deg[a] += 1
    deg[b] += 1

C = list(map(int, input().split()))
C = sorted(C)
que = []
for i in range(N):
    que.append((deg[i], i))

que = sorted(que)
D = [-1] * N
used = [0] * N
i = 0
while que:
    k = heappop(que)
    if used[k[1]] > 0:
        heappush(que, (k[0] - used[k[1]], k[1]))
        used[k[1]] = 0
        continue
    else:
        D[k[1]] = C[i]
        i += 1
        for w in G[k[1]]:
            used[w] += 1

ans = 0
for i in range(len(E)):
    ans += min(D[E[i][0]], D[E[i][1]])

print(ans)
print(*D)

Submission status: Wrong Answer

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

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

maxcount = 0

for i in range(N-1):
    maxcount += min(numlist[treelist[i][0]-1],numlist[treelist[i][1]-1])

print(maxcount)

print(" ".join(map(str,numlist)))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
R = [[] for i in range(n)]
road = []
for i in range(n-1):
	a,b = (x-1 for x in map(int,input().split()))
	R[a] += [b]
	R[b] += [a]
	road.append([a,b])
C = sorted(map(int,input().split()),reverse=1)

###どこにC置くか偏
R_len = []
for i,r in enumerate(R):
	R_len.append([len(r),i])

R_len.sort(reverse=1)

town = [0 for _ in range(n)]
for i,r in enumerate(R_len):
	town[r[1]] = C[i]

###隣町から最小数を探す
ans = 0
for r in road:
	ans += min(C[r[0]],C[r[1]])
print(ans)
c_ans = ""
for c in C:
	c_ans += str(c)+" "
print(c_ans[:-1])

Submission status: Wrong Answer

Solution code:


def main():
    n = input()
    edges = []
    nodes = [0] * n
    for _ in xrange(n - 1):
        a, b = map(int, raw_input().split())
        a -= 1
        b -= 1
        edges.append([a, b])
        nodes[a] += 1
        nodes[b] += 1
    nodes = sorted([nodes[node], node] for node in xrange(n))
    cc = map(int, raw_input().split())
    cc.sort()
    ans = [0] * n
    for (_, node), c in zip(nodes, cc):
        ans[node] = c
    score = 0
    for a, b in edges:
        score += min(ans[a], ans[b])
    print score
    print ' '.join(map(str, ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
road_list = [[] for i in range(N)]
"""
leaf_list = []
for i in range(N):
    a,b=list(map(int,input().split()))
    a=a-1
    b=b-1
    if reged[a]!=-1:
        reged[b]=a
        leaf_list.append()
    elif reged[b]!=-1:
        reged[a]=b
        leaf_list.append(a)
    else:
        reged[b]=a
        reged[a]=N
        leaf_list.append(a)
        leaf_list.append(b)
"""
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)]
count_list = [0 for i in range(N)]

while len(Q)>0:
    q = Q.pop()
    v=q[0]
    count=q[1]
    checked_list[v]=True
    count+=1
    for v1 in road_list[v]:        
        if not checked_list[v1]:
            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:
N = int(input())
d = {}
for _ in range(N - 1):
    a, b = map(int, input().split())
    if a not in d:
        d[a] = 1
    else:
        d[a] += 1
    if b not in d:
        d[b] = 1
    else:
        d[b] += 1
c = list(map(int, input().split()))
c.sort()
dd = sorted(d.items(), key=lambda x:x[1])
ddd = {}

t = 0
for i in dd:
    ddd[i[0]] = c[t]
    t += 1

print(sum(c) - max(c))
for value in ddd.values():
    print(value, end=' ')

Submission status: Wrong Answer

Solution code:
n = int(input())
edge =[]
use =[[0,i] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    use[a][0] += 1
    use[b][0] += 1
    edge.append([a,b])

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

ans =[0 for i in range(n)]
for i in range(n):
    ans[use[i][1]] = c[i]


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

print(m)
for i in range(n):
    print(ans[i],end=' ')

print()

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))

q = int(input())

k = [[i,0]for i in range(q)]
aa = []
for i in range(q-1):
	a,b  = m()
	k[a-1][1] += 1
	k[b-1][1] += 1
	aa.append([a,b])
k.sort(key = lambda x:x[1],reverse = True)
c  = l()
c.sort(reverse = True)
for i in range(q):
	k[i][1] = c[i]

k.sort()
su = 0
for i in range(q-1):
	su += min(k[aa[i][0]-1][1],k[aa[i][1]-1][1])

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

Submission status: Wrong Answer

Solution code:
from collections import deque
N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    if a<b:
        G[a].append(b)
    else:
        G[b].append(a)
c=sorted([int(i) for i in input().split()])
d=[0 for i in range(N)]
M=sum(c)-max(c)
q=deque([0])
while(len(q)>0):
    r=q.popleft()
    d[r]=c.pop()
    for p in G[r]:
        q.append(p)
print(M)
print(" ".join([str(i) for i in d]))

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
edges = [tuple(li_()) for _ in range(n-1)]
c = list(li())
c.sort()

ins = []
node = [0]*n

graph = [[] for _ in range(n)]
for l, r in edges:
    graph[l].append(r)
    graph[r].append(l)

for i, gi in enumerate(graph):
    ins.append((len(gi), i))

ins.sort()

for j, (_, i) in enumerate(ins):
    node[i] = c[j]

ans = 0
for l, r in edges:
    ans += min(node[l], node[r])

print(ans)
print(*node)

Submission status: Wrong Answer

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

    p = [len(edge[i]) for i in range(n)]

    res = 0
    ans = []
    for i in range(n):
        q = 0
        while len(h)>0:
            q,ten = heapq.heappop(h)
            if not used[ten]:
                used[ten] = True
                ans.append(ten+1)
                break

        res += q*c[i]
        for e in edge[ten]:
            if not used[e]:
                p[e]-=1
                heapq.heappush(h,[p[e],e])
    print(res)
    for e in ans:
        print(e,end = ' ')

if __name__ == '__main__':
    main()

Submission status: 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 = []
for k, v in adjacent_dict.items():
  if len(v)==1:
    leafs.append(k)

nodes = leafs.copy() #小さい値を入れたい順のノード
visited = [0] * (N+1) # visited[i]: 頂点i
for n in nodes:
  visited[n] = 1
  
stack = leafs.copy()
while stack:
  new_stack=[]
  for v in stack:
    for u in adjacent_dict[v]:
      if visited[u]==1:
        continue
      else:
        visited[u]=1
        nodes.append(u)
        new_stack.append(u)
  stack = new_stack
  
ans = [0]*(N)
for i in range(N):
  ans[nodes[i]-1] = C[i]
  
print(M)
print(*ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
nodes = {}
for _ in range(n-1):
  a, b = map(int, input().split())
  if a-1 in nodes:
    nodes[a-1].append(b-1)
  else:
    nodes[a-1] = [b-1]
  if b-1 in nodes:
    nodes[b-1].append(a-1)
  else:
    nodes[b-1] = [a-1]
clist = list(map(int, input().split()))
clist.sort()
clist.reverse()

scores = [-1 for _ in range(n)]
ci = 0
for i, (k, edge) in enumerate(sorted(nodes.items(), key=lambda x: len(x[1]))):
  if scores[i] == -1:
    scores[i] = clist[ci]
    ci += 1
    for e in edge:
      if scores[e] == -1:
        scores[e] = clist[ci]
        ci += 1

ans = 0
for f, edge in nodes.items():
  for to in edge:
    ans += min(scores[f], scores[to])
print(ans//2)
print(*scores)

Submission status: Wrong Answer

Solution code:
n = int(input())
#tree = [[0 for i in range(n)] for i in range(n)]
count = []

for i in range(n):
    count.append([0, 0, i])

for i in range(n - 1):
    a, b = map(int, input().split())
    #tree[a-1][b-1], tree[b-1][a-1] = 1, 1
    count[a-1][0] += 1
    count[b-1][0] += 1
#print(count)
c = list(map(int, input().split()))
c.sort(reverse = True)
count.sort()
count.reverse()
#print(count)
for i in range(n):
    count[i][1] = c[i]
count = sorted(count, key = lambda x: x[2])

print(sum(c) - max(c))
#print(count)
for i in range(n):
    print("{} ".format(count[i][1]), end = "")

print("\n")

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [list(map(int, input().split())) for _ in range(n-1)]
c = list(map(int, input().split()))
c.sort(reverse=True)
print(sum(c[1:]))
print(' '.join(map(str, c)))

Submission status: Wrong Answer

Solution code:
import heapq

n = int(input())
edge = [[] for _ in range(n)]
e = []
for i in range(n - 1):
    a, b = map(int, input().split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
    e.append((a - 1, b - 1))
c = list(map(int, input().split()))
c.sort(reverse=True)
d = [0] * n

edge_num = []
for i in range(n):
    edge_num.append((len(edge[i]), i))

edge_num.sort(key=lambda x: x[0], reverse=True)

for i in range(n):
    d[edge_num[i][1]] = c[i]

m = 0
for a, b in e:
    m += min(d[a], d[b])
print(m)
print(" ".join(map(str, d)))

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
g = [[0,i] for i in range(n)]

for i in range(n-1):
  a,b = na()
  g[a-1][0] += 1
  g[b-1][0] += 1

c = na()
c.sort()
g.sort()

p = [0]*n

for i in range(n):
  p[g[i][1]] = c[i]

print(sum(c)-c[-1])
print(' '.join([str(v) for v in p]))

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
ab = [[int(_) for _ in input().split()] for _ in range(N - 1)]
c = [int(_) for _ in input().split()]
c.sort(reverse=True)

AB = []
ans = [0] * N
for a, b in ab:
    AB += a, b

counterAB = Counter(AB)

val, count = zip(*counterAB.most_common())
for i, v in enumerate(val):
    ans[v - 1] = c[i]

cnt = 0
for A, B in ab:
    cnt += min(ans[A - 1], ans[B - 1])

print(cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
adj_list = defaultdict(list)
E = []
V_number = [None]*N
for _ in range(N-1):
    a, b = map(int, input().split())
    E.append((a, b))
    adj_list[a].append(b)
    adj_list[b].append(a)
C = sorted(list(map(int, input().split())))
V_deg = sorted([(len(e), i) for i, e in enumerate(adj_list.values())])
for c, (_, i) in zip(C, V_deg):
    V_number[i] = c
ans = 0
for u, v in E:
    ans += min(V_number[u-1], V_number[v-1])
print(ans)
print(*V_number)

Submission status: Wrong Answer

Solution code:
N = int(input())
tree = [[] for i in range(N+1)]
hen = []
tyouten = [0 for i in range(N+1)]
dig = []
for i in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
    hen.append(sorted([a,b]))
c = list(map(int, input().split()))
c.sort()

for i in range(1,N+1):
    dig.append([len(tree[i]),i])

dig.sort()

for i in range(N):
    tyouten[dig[i][1]] = c[i]


ans = 0
for i in range(len(hen)):
    ans += min(tyouten[hen[i][0]], tyouten[hen[i][1]])

print(ans)
print(" ".join(map(str, tyouten[1:])))

Submission status: Wrong Answer

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

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

C = sorted(inpl())
ans = [-1]*(N+1)
ans[1] = C.pop()

def dfs(i):
    for j in D[i]:
        if ans[j] == -1:
            ans[j] = C.pop()
            dfs(j)

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

Submission status: Wrong Answer

Solution code:
import itertools;
N = int(input())
ab_list=list()
count_list = [0]*N
for _ in range(N-1):
    a, b = map(int, input().split())
    ab_list.append([a,b])
c_list = list(map(lambda x: int(x), input().split()))

ans = 0
for i in itertools.permutations(c_list, N):
    score = 0
    for ab in ab_list:
        a, b = ab
        score += min(i[a-1], i[b-1])
    ans = max(ans, score)  

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

met = [[0,i] for i in range(N)]
link = [set() for i in range(N)]
ans = [0 for i in range(N)]
ab = [[0,0] for i in range(N-1)]

for i in range(N-1):
    a, b = map(int, input().split())
    met[a-1][0] += 1
    met[b-1][0] += 1
    link[a-1].add(b-1)
    link[b-1].add(a-1)
    ab[i][0] = a-1
    ab[i][1] = b-1

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

c = sorted(c, reverse=True)
met = sorted(met, reverse=True)

for i in range(N):
    ans[met[i][1]] = c[i]

m = 0
for i in range(N-1):
    m += min(ans[ab[i][0]], ans[ab[i][1]])

print(m)
for i in range(N-1):
    print(ans[i], end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
n=int(input())
m = {}
cnt = [0] * (n+1)
edges = []

for i in range(n-1):
    a,b=map(int, input().split())
    edges.append((a, b))
    m[a] = m.get(a, set())
    m[a].add(b)
    m[b] = m.get(b, set())
    m[b].add(a)
    cnt[a] += 1
    cnt[b] += 1

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

from collections import deque

q = deque()
current = 0
ans = [0] * (n+1)
for i in range(1, n+1):
    if cnt[i] == 1:
        q.append(i)

while q:
    node = q.pop()
    ans[node] = c[current]
    current += 1
    for i in m[node]:
        cnt[i] -= 1
        if cnt[i] == 1:
            q.append(i)

print(sum(min([ans[i[0]], ans[i[1]]]) for i in edges))
for i in range(1, n+1):
    print(i)

Submission status: Wrong Answer

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

ct=0
for i in range(n-1):
  ct+=min(ans[l[i][0]-1],ans[l[i][1]-1])
for i in range(n):
  ans[i]=str(ans[i])
print(ct)
print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
import os
import sys
import numpy as np

sys.setrecursionlimit(2147483647)
INF = float('inf')

if os.getenv('LOCAL'):
    sys.stdin = open('_in.txt')

N = int(sys.stdin.readline())
A, B = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N - 1)]))
C = list(map(int, sys.stdin.readline().split()))


def shortest_path(start, graph):
    stack = [(start, 0)]
    dists = [INF] * (N + 1)
    dists[start] = 0
    while stack:
        v, vw = stack.pop()
        for u, w in graph[v]:
            if dists[u] == INF:
                dists[u] = vw + w
                stack.append((u, vw + w))
    return dists


#: :type: list of (list of (int, int))
graph = [[] for _ in range(N + 1)]
for a, b in zip(A, B):
    graph[a].append((b, 1))
    graph[b].append((a, 1))

# 適当に root 決める
root = 1
distances = shortest_path(root, graph)[1:]

# 葉から小さい順に埋めてく
ans = np.zeros(N, dtype=int)
C.sort(reverse=True)
for i, di in enumerate(np.argsort(distances)):
    ans[di] = C[i]

print(*ans)

Submission status: Wrong Answer

Solution code:
from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N = int(input())
d=[0]*(N)
vcost=[0]*(N)
degree =[]
edge = []
for i in range(N-1):
    a,b = map(int,input().split())
    edge.append((a,b))
    d[a-1]+=1
    d[b-1]+=1
for i in range(N):
    degree.append((d[i],i))
degree.sort()
c = list(map(int,input().split()))
c.sort()
for i in range(N):
    vcost[degree[i][1]]=c[i]
ans = 0
for e in edge:
    ans +=min(vcost[e[0]-1],vcost[e[1]-1])
print(ans)
print(*vcost,sep=" ")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)
        self.node = defaultdict(int)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def get_nodes(self):
        return self.graph.keys()

def getlist():
	return map(int, input().split())


G = Graph()
L = []
N = int(input())
for i in range(N - 1):
	a, b = getlist()
	G.add_edge(a - 1, b - 1)
	G.node[a - 1] += 1
	G.node[b - 1] += 1
	L.append([a - 1, b - 1])
c = getlist()
c = sorted(c)

cnt = []
for i in G.node:
	cnt.append([G.node[i], i])

cnt = sorted(cnt)

D = defaultdict(int)
for i in range(N):
	D[cnt[i][1]] = c[i]

M = sum(c) - c[-1]
print(M)

ansL = []
for i in D:
	ansL.append(D[i])

ansL = list(map(str, ansL))
print(" ".join(ansL))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
b = []
for i in range(n-1):
    a1, b1 = map(int, input().split())
    a.append(a1)
    b.append(b1)

c = list(map(int, input().split()))
c.sort()
s = 0
for i in range(len(c)-1):
    s += c[i]

print(s)

Submission status: Wrong Answer

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

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

    return

main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3


def main():
    n = int(input())
    # 次数
    d = [0] * n
    a = []
    b = []
    for i in range(n - 1):
        ai, bi = list(map(int, input().split()))
        d[ai-1] += 1
        d[bi-1] += 1
        a.append(ai-1)
        b.append(bi-1)
    c = list(map(int, input().split()))

    dandi = []
    for i, di in enumerate(d):
        dandi.append((i, di))
    sortedd = sorted(dandi, reverse=True, key=lambda x: x[1])
    result = [0] * n
    sortedc = sorted(c, reverse=True)
    for i, _ in sortedd:
        result[i] = sortedc.pop(0)

    resultSum = 0
    for i in range(n-1):
        resultSum += min(result[a[i]], result[b[i]])
    print(resultSum)
    print(' '.join(map(str, result)))



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

nei_list = [[i , 0] for i in range(N)]
for edge in edges:
    a = edge[0]-1
    b = edge[1]-1
    nei_list[a][1] += 1
    nei_list[b][1] += 1

nei_list.sort(key=lambda x: x[1], reverse=True)

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

for i in range(N):
    idx = nei_list[i][0]
    ans[idx] = c[i]
m = 0
for edge in edges:
    a = edge[0] - 1
    b = edge[1] - 1
    m += min(ans[a], ans[b])
print(m)
ans_str = ""
for i in range(len(ans)):
    ans_str += str(ans[i])
    if i < len(ans)-1:
        ans_str += " "
print(ans_str)

Submission status: Wrong Answer

Solution code:
#!venv/bin/python
 
import math
import numpy as np
import random
import copy
import statistics 
import bisect
import heapq
from collections import defaultdict 

#N, K = [ int(x) for x in input().split() ]
#V = [ int(x) for x in input().split() ]

N = int(input())
Lines = []
for _i in range(N-1):
    Lines.append([ int(x) - 1 for x in input().split() ])
C = [ int(x) for x in input().split() ]

C = sorted(C)
cntC = defaultdict(int)
for l in Lines:
    cntC[l[0]] += 1
    cntC[l[1]] += 1

point_orderd = sorted(cntC.keys(), key=lambda x: cntC[x])

scores = [None for i in range(N)]
for i in range(N):
    scores[point_orderd[i]] = C[i]

max_score = 0
for l in Lines:
    max_score += min(scores[l[0]], scores[l[1]])

print(max_score)
print(" ".join([str(x) for x in scores]))