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 numpy as np
from sys import stdin

N = int(stdin.readline().rstrip())

vs = np.array([list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)])
cs = np.sort(np.array(list(map(int, stdin.readline().rstrip().split()))))[::-1]

max_score = np.sum(cs[1:])

def make_tree(i):
    global vs
    children = vs[np.any(vs == i, axis=1)].flatten()
    children = children[children != i]
    vs =vs[np.all(vs != i, axis=1)]
    # return np.array([i, list(map(make_tree ,children))])

    # return np.array([i, np.array(list(map(make_tree ,children)))])

tree = make_tree(1)
# c_pos = np.empty_like(cs)
# 
# def show_tree(tree):
#     global cs
#     c_pos[tree[0]-1] = cs[0]
#     cs = np.delete(cs, 0)
#     [show_tree(t) for t in tree[1]]
# 
# show_tree(tree)
# 
# print(max_score)
# print(' '.join([str(c) for c in c_pos]))

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

import collections


class BellmanFord():
    def __init__(self):
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        次のBellmanFord_negative_boolまで考慮した時には、0-indexedであることに注意
        s =  始点
        return: d[i] 始点sから各点iまでの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_bool(self, numNodes, zero_indexed=False):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = collections.defaultdict(lambda: float('inf'))
        d[0] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if i == numNodes-1:
                        return True
        return False

n = ni()
g = BellmanFord()

for i in range(n-1):
  a,b = na()
  g.add(a,b,1)

c = na()
c = sorted(c)[::-1]

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

a = g.BellmanFord_search(1)

ans = [0]*n
f = 0

for i in a:
  ans[i-1] = c[f]
  f+=1

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

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

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

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)
ll = []
while q:
    if len(q) == 0:break
    t = q.popleft()
    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(li)-li[0])
print(*lp)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
A = []
B = []
D = []
for i in range(N-1):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

C = list(map(int, input().split()))
D = C.copy()
_list = []
buff = []
_sum = 0
__d = sorted(D)
__d = __d[::-1]
_c = [[0]*2 for i in range(N)]
for i in range(N-1):
    _c[i][1] = i
    _c[A[i]-1][0] += 1
    _c[B[i]-1][0] += 1
_c[-1][1] = N-1
ans = 0
_c = sorted(_c)
_c = _c[::-1]
ans_list = [0 for i in range(N)]
for i in range(N):
    ans_list[_c[i][1]] = __d[i]

for i in range(N-1):
    _list.append(min(ans_list[A[i]-1], ans_list[B[i]-1]))

print(sum(_list))
print(" ".join([str(n) for n in ans_list]))

Submission status: Wrong Answer

Solution code:
n = int(input())
lis = [list(map(int,input().split())) for x in range(n-1)]
clis = sorted(list(map(int,input().split())),reverse=True)
ans_lis = [0]*n
ans = 0
for x in lis:
    ans += min(clis[x[0]-1],clis[x[1]-1])
    ans_lis[x[0]-1] = clis[x[0]-1]
    ans_lis[x[1]-1] = clis[x[1]-1]
print(ans)
print(*ans_lis)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(neighbor,start):
    order = [0 for i in range(N)]
    visited = [0 for i in range(N)]
    visited[start] = 1
    q = deque([start])
    num = 1
    while q:
        path = q.popleft()
        order[path] = num
        visited[path] = 1
        num += 1
        for v in range(len(neighbor[path])):
            if neighbor[path][v] == 0:
                continue
            if visited[v] == 1:
                continue
            q.append(v)
    order = [[i,order[i]] for i in range(len(neighbor))]
    order.sort(key=lambda x:x[1])
    return [order[i][0] for i in range(len(order))]


N = int(input())
node = [[0,i] for i in range(N)]
ab = []
neigh = [[0 for i in range(N)] for j in range(N)]
for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1][0] += 1
    node[bi-1][0] += 1
    neigh[ai-1][bi-1] = 1
    neigh[bi-1][ai-1] = 1
    ab.append([ai-1,bi-1])
c = list(map(int,input().split()))
c.sort(reverse=True)
node.sort(key=lambda x:x[0],reverse=True)
m = max([node[i][0] for i in range(N)])
max_node = [node[i][1] for i in range(N) if node[i][0] == m]
ans1 = 0
for nn in max_node:
    can = 0
    bbb = bfs(neigh,nn)
    cn = [[c[i],bbb[i]] for i in range(N)]
    #cn.sort(key=lambda x:x[1])
    for i in range(N-1):
        can += min(cn[ab[i][0]][0],cn[ab[i][1]][0])
    if can > ans1:
        ans1 = can
        ans2 = ' '.join([str(cn[i][0]) for i in range(N)])

        
print(ans1)

print(ans2)

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 a,i in R_len:
	c_ans += str(C[i])+" "
print(c_ans[:-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

edge = [[] for _ in range(N)]
conect = [[i,0] for i in range(N)] # つながる頂点の数 ... 多い頂点に大きい数字を与える

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

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

net = lambda A : A[1]

conect.sort(key=net,reverse=True)

ans = [0] * N

for i in range(N) :
    ans[conect[i][0]] = c[i]

checked = [False] * N
length = 0

for c , check in enumerate(checked) :
    if check :
        continue

    stack = deque([c])

    while stack :
        current = stack.pop()

        if checked[current] :
            continue

        checked[current] = True
        for v in edge[current] :
            if not checked[v] :
                stack.append(v)
                length += min(ans[current] , ans[v])

print(length)

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

print('')

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+1].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(nodeList[i+1].ans, end=" ")
    #print(nodeList[i+1].No, nodeList[i+1].cnt, nodeList[i+1].ans)

Submission status: Wrong Answer

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

def combinations(iterable):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    r = len(pool)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

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 = []

# cLoop = itertools.permutations(cs)
cLoop = combinations(cs)

for c in cLoop:
    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):
        maxCount = count
        maxList = c
    count = 0

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[[] for i in range(n+1)]
ans=[0]*(n)
for i in range(1,n):
    A=list(map(int,input().split()))
    a[A[0]].append([A[1],i])
d=list(map(int,input().split()))
d.sort(reverse=True)
ans[0]=d[0]
d.pop(0)
ans0=sum(d)
for i in range(1,n+1):
    for j in range(len(a[i])):
        ans[a[i][j][1]]=d[0]
        d.pop(0)
print(ans0)
print(*ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
nodes=[0]*(N+1)
edge_list=[]
point_dic={}
for i in range(N-1):
    a,b=map(int,input().split())
    nodes[a]+=1
    nodes[b]+=1
    edge_list.append((a,b))
    point_dic.setdefault(a,[]).append(b)
    point_dic.setdefault(b,[]).append(a)
c=list(map(int,input().split()))
c.sort(reverse=True)
nodes=nodes[1:]
node_dic={}
for i,node in enumerate(nodes):
    node_dic.setdefault(node,[]).append(i)

import collections
node_list = collections.Counter(nodes)

node_dic_sorted=sorted(node_list.items(), key=lambda x:x[0], reverse=True)

def around(posi):
    for around_posi in point_dic[posi+1]:
        if len(c)==0:
            break
        if ans[around_posi-1]==0:
            ans[around_posi-1]=c.pop(0)
            #print(ans)
ans=[0]*N
for i in range(len(node_dic_sorted)):
    for posi in node_dic[node_dic_sorted[i][0]]:
        if ans[posi]==0:
            #print(posi)
            ans[posi]=c.pop(0)
            around(posi)
        if len(c)==0:
            break
ans_N=0
for edge in edge_list:
    ans_N+=min(ans[edge[0]-1],ans[edge[1]-1])
    #print(edge)
print(ans_N)
print(*ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
memo = [[0,i] for i in range(N+1) ]
for i in range(N-1):
    a,b = map(int, input().split())
    memo[a][0] += 1
    memo[b][0] += 1
memo.sort(reverse = True)
memo.remove([0,0])

c = list(map(int, input().split()))
c.sort(reverse = True)
ans = 0
for i in range(1,N):
    ans += c[i]
lans = [0 for i in range(N)]
for i in range(N):
    lans[memo[i][1]-1] = c[i]
print(ans)
print(lans)

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

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

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)
ll = []
while q:
    if len(q) == 0:break
    t = q.popleft()
    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:
import random
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)

copynumlist = numlist
a = 0
for j in range(10000):
    random.shuffle(copynumlist)
    if copynumlist != numlist:
        othermaxcount = 0
        for i in range(N-1):
            othermaxcount += min(numlist[treelist[i][0]-1],numlist[treelist[i][1]-1])
        if othermaxcount == maxcount:
            break
        

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

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

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

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)
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:
N = int(input())
route_list = list()
cross_count_list = [0] * N

for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    cross_count_list[a - 1] += 1
    cross_count_list[b - 1] += 1
    route_list.append({'a': a, 'b': b})

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

node_count_info_list = sorted([{'node': i, 'cross_count': cross_count_list[i]}
                               for i in range(N)], key=lambda x: x['cross_count'], reverse=True)
node_number_list = [0] * N
for i in range(N):
    node_count_info = node_count_info_list[i]
    node_number_list[node_count_info['node']] = c_list[i]

answer = 0
for route in route_list:
    answer += min(node_number_list[route['a'] - 1], node_number_list[route['b'] - 1])

print(answer)
print(' '.join(list(map(str, node_number_list))))

Submission status: Wrong Answer

Solution code:
n=int(input())
num=[[0,i] for i in range(n)]
d=[0 for i in range(n)]

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

c=list(map(int,(input().split())))
c.sort()
c.reverse()
num.sort()
for i in range(n):
  d[num[i][1]]=c[i]
print(sum(c)-c[0])
print(d)

Submission status: Wrong Answer

Solution code:
n = int(input())
lines = []
line_dat = []

for i in range(n + 1):
    lines.append((i, 0))

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

lines.sort(key=lambda x: -x[1])
dat_c = list(map(int, input().split()))
dat_c.sort(reverse=True)

cans = []
dat_cans = []
for i in range(100001):
    cans.append((i, 0))
for i in range(len(dat_c)):
    cans[dat_c[i]] = (cans[dat_c[i]][0], cans[dat_c[i]][1] + 1)

for i in range(100001):
    if cans[i][1] != 0:
        dat_cans.append((i, cans[i][1]))






res = [-1] * (n + 1)

for i in range(n):
    res[lines[i][0]] = dat_c[i]

c = 0
orig = []
"""
print("")
print("dat_cans")
print(dat_cans)
print("lines")
print(lines)
print("line_dat")
print(line_dat)
print("dat_c")
print(dat_c)
"""

for i in range(len(dat_cans)):
    t = []
    for j in range(dat_cans[i][1]):
        t.append( lines[c][0] )
        c=c+1
    orig.append(t)


# コスト計算
lines.remove((0, 0))
cost = 0
for i in range(len(line_dat)):
    cost += min( res[line_dat[i][0]], res[line_dat[i][1]])

res = res[1:]
print(cost)
print(" ".join(list(map(lambda x:str(x), res))))

Submission status: Wrong Answer

Solution code:
n = int(input())

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

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

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

sh = []

def delete(edges):
    sh.append(edges)

    for i in range(len(edges)):
        la = adj[edges[i]][0]
        adj[la].remove(edges[i])
        if len(adj[la]) == 0:
            sh.append([la])
        adj[edges[i]] = []
    return

def search(adj):
    k = []
    for i in range(len(adj)):
        if len(adj[i]) == 1:
            k.append(i)
    return k

ed = search(adj)

while len(ed):
    delete(ed)
    ed = search(adj)
    if len(ed) == 1:
        sh.append(ed)
        break
    if len(ed) == 2:
        if adj[ed[0]] and adj[ed[0]][0] == ed[1]:
            sh.append(ed)
            break

sug = []
for i in range(len(sh)):
    for m in sh[i]:
        sug.append(m)


for i in range(len(sug)):
    ans[sug[i]] = c[i]



for i in range(n-1):
    anum += c[i]
print(anum)
print(ans)

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(key=lambda x:x[0],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)
for i in range(N):
    print(side_num[i][0],end=" ")

Submission status: Wrong Answer

Solution code:
from collections import deque
import heapq


N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    # グラフに頂点と距離を追加
    G[u-1].append((v-1))
    G[v-1].append((u-1))
cs = sorted(list(map(int,input().split())))

gs = []
heapq.heapify(gs)
# Gを大きい順に並べ替える
for i,g in enumerate(G):
    n = len(g)
    heapq.heappush(gs,(n,i))

ds = [0]*N
for i in range(N):
    n, j = heapq.heappop(gs)
    ds[j] = cs[i]

used = [False] * N
used[0] = True 
ans = 0

q = deque([0])
while len(q) > 0:
    a = q.popleft()
    Vs = G[a]
    for u in Vs:
        if not used[u]:
            q.append(u)
            ans += min(ds[a],ds[u])
            used[u] = True
ansd = ""
for d in ds:
    ansd += str(d)+" "

print(ans)
print(ansd)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

N = int(input())
g = defaultdict(list)
K = []
for i in range(N-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
    K.append((a,b))

C = deque(sorted([int(i) for i in input().split()]))

c = sorted([(i, len(g[i])) for i in range(1,N+1)], key=lambda x: x[1])

a = {i: 0 for i in range(1, N+1)}

for i, k in c:
    #if i % 2:
    a[i] = C.popleft()
    #else:
    #a[i] = C.popleft()

ans = 0
for b, c in K:
    ans += min(a[b],a[c])

print(ans)
l=[str(a[i]) for i in sorted(a.keys())]
print(' '.join(l))

Submission status: Wrong Answer

Solution code:
n=int(input())
num=[[0,i] for i in range(n)]
d=[0 for i in range(n)]
print(num)
for i in range(n-1):
  a,b=map(int,input().split())
  num[a-1][0]+=1
  num[b-1][0]+=1
print(num)
c=list(map(int,(input().split())))
c.sort()
c.reverse()
num.sort()
for i in range(n):
  d[num[i][1]]=c[i]
print(sum(c)-c[0])
print(d)

Submission status: Wrong Answer

Solution code:
n = int(input())
e = [[int(i) for i in input().split()] for i in range(n-1)]
c = [int(i) for i in input().split()]


import numpy as np
keys = []
for i in range(1,n+1):
    keys.append(str(i))
dic = dict(zip(keys, np.zeros(n)))
    
for node in e:
    if str(node[0]) in dic:
        dic[str(node[0])] += 1
    if str(node[1]) in dic:
        dic[str(node[1])] += 1
max_k = max(dic, key=dic.get)
output_sum = sum(c) - max(c)

output_order = []
for v in c:
    if v != max(c):
        output_order.append(v)

output_order.insert(int(max_k),max(c))
output_str = ""
for i in output_order:
  output_str += str(i) + " "
print(output_sum)
print(output_str)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs(neighbor,start):
    order = [0 for i in range(N)]
    visited = [0 for i in range(N)]
    visited[start] = 1
    q = deque([start])
    num = 1
    while q:
        path = q.popleft()
        order[path] = num
        visited[path] = 1
        num += 1
        for v in neighbor[path]:
            if visited[v] == 1:
                continue
            q.append(v)
    order = [[i,order[i]] for i in range(len(neighbor))]
    order.sort(key=lambda x:x[1])
    return [order[i][0] for i in range(len(order))]


N = int(input())
node = [[0,i] for i in range(N)]
ab = []
neigh = [[0 for i in range(N)] for j in range(N)]
for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1][0] += 1
    node[bi-1][0] += 1
    neigh[ai-1][bi-1] = 1
    neigh[bi-1][ai-1] = 1
    ab.append([ai-1,bi-1])
c = list(map(int,input().split()))
c.sort(reverse=True)
node.sort(key=lambda x:x[0],reverse=True)
m = max([node[i][0] for i in range(N)])
max_node = [node[i][1] for i in range(N) if node[i][0] == m]
ans1 = 0
for nn in max_node:
    can = 0
    bbb = bfs(neigh,nn)
    cn = [[c[i],bbb[i]] for i in range(N)]
    #cn.sort(key=lambda x:x[1])
    for i in range(N-1):
        can += min(cn[ab[i][0]][0],cn[ab[i][1]][0])
    if can > ans1:
        ans1 = can
        ans2 = ' '.join([str(cn[i][0]) for i in range(N)])

        
print(ans1)

print(ans2)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
dd = defaultdict(list)
pair_list = []
for i in range(N-1):
  a,b = map(int, input().split())
  pair = []
  pair.append(a)
  pair.append(b)
  pair_list.append(pair)
  dd[a].append(b)
  dd[b].append(a)
lst = list(map(int, input().split()))
sorted_lst = sorted(lst, reverse=True)
q = {}
for k, v in sorted(dict(dd).items(), key=lambda x: -len(x[1])):
  if (k not in q):
    q[k] = sorted_lst.pop(0)
  for i in v:
    if (i not in q):
      q[i] = sorted_lst.pop(0)
sum = 0
for i in pair_list:
  if (q[i[0]] > q[i[1]]):
    sum += q[i[1]]
  else:
    sum += q[i[0]]
print(sum)
str_lst = [str(v) for v in q.values()]
print(' '.join(str_lst))

Submission status: Wrong Answer

Solution code:
n = int(input())

graph = [[x+1] for x in range(n)]
ans = [[] for x in range(n)]

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

for i in range(n):
    graph[i].insert(0, len(graph[i]))

graph.sort()
nums = sorted(list(map(int,input().split())))
for i in range(n):
    ans[graph[i][1] - 1].append(nums[i])


print(sum(nums)-max(nums))

for i in range(n):
    print(ans[i][0], end=" ")

print()

Submission status: Wrong Answer

Solution code:
n = int(input())

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

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

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

sh = []

def delete(edges):
    sh.append(edges)

    for i in range(len(edges)):
        la = adj[edges[i]][0]
        adj[la].remove(edges[i])
        if len(adj[la]) == 0:
            sh.append([la])
        adj[edges[i]] = []
    return

def search(adj):
    k = []
    for i in range(len(adj)):
        if len(adj[i]) == 1:
            k.append(i)
    return k

ed = search(adj)

while len(ed):
    delete(ed)
    ed = search(adj)
    if len(ed) == 1:
        sh.append(ed)
        break
    if len(ed) == 2:
        if adj[ed[0]] and adj[ed[0]][0] == ed[1]:
            sh.append(ed)
            break

sug = []
for i in range(len(sh)):
    for m in sh[i]:
        sug.append(m)


for i in range(len(sug)):
    ans[sug[i]] = c[i]


print(ans)

for i in range(n-1):
    anum += c[i]
print(anum)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from sys import stdin

N = int(stdin.readline().rstrip())

vs = np.array([list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)])
cs = np.sort(np.array(list(map(int, stdin.readline().rstrip().split()))))[::-1]

max_score = np.sum(cs[1:])

# def make_tree(i):
#     global vs
#     children = vs[np.any(vs == i, axis=1)].flatten()
#     children = children[children != i]
#     vs =vs[np.all(vs != i, axis=1)]
# 
#     return np.array([i, np.array(list(map(make_tree ,children)))])
# 
# tree = make_tree(1)
# c_pos = np.empty_like(cs)
# 
# def show_tree(tree):
#     global cs
#     c_pos[tree[0]-1] = cs[0]
#     cs = np.delete(cs, 0)
#     [show_tree(t) for t in tree[1]]
# 
# show_tree(tree)
# 
# print(max_score)
# print(' '.join([str(c) for c in c_pos]))

Submission status: Wrong Answer

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

ab = a+b
cnt_list = [0]*n
l = []
for num in list(set(ab)):
    l  += [[num-1, ab.count(num)]]
l = sorted(l, key=lambda x:x[1], reverse=True)

for i in range(len(d)):
    d[l[i][0]] = c[i]

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

Submission status: Wrong Answer

Solution code:
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
# import statistics
import bisect
import copy
import fractions
import math
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) 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 MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))
def unite(x, y):
    # それぞれのノードの根を求める
    x = root(x)
    y = root(y)
    if x == y:
        return
    # node[x]の根をyに変更する
    node[x] = y
def same(x,y): return bool(root(x) == root(y))
def root(x):
    if node[x] == x:  # xが根の場合
        return x
    else:
        node[x] = root(node[x])  # 経路圧縮
        return node[x]
def dfs(v):
    # ノードに訪れた
    visited[v] = True
    for v2 in range(n):
        if graph[v][v2] == False:  # そもそもvとv2が辺でつながっていない
            continue
        if visited[v2] == True:  # もう見た
            continue
        dfs(v2)


n = II()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = MI()
    graph[u-1].append(v-1)
    graph[v-1].append(u-1)
c = sorted(LI(), reverse=True)
ans = [-1] * n
length = [[i, len(graph[i])] for i in range(n)]
length = sorted(length, key=lambda x: x[1], reverse=True)
# print(length)
for i, node in enumerate(length):
    ans[node[0]] = c[i]
print(sum(c[1::]))
for i in range(n):
    print(ans[i], end=' ')
print()

Submission status: Wrong Answer

Solution code:
N =int(raw_input())
for i in range(N-1):
    a,b = map(int,raw_input().split())
S = list(map(int,raw_input().split()))
S.sort()
A = sum(S)-S[-1]
print A

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
c = list(map(int, input().split()))
c.sort(reverse=True)

nodes = [[0, i] for i in range(n)]
for a, b in ab:
  nodes[a-1][0] += 1
  nodes[b-1][0] += 1
nodes2 = nodes[::]
nodes.sort(key=lambda x: -x[0])
# print(nodes)

for a, b in ab:
  nodes[a-1][0] += nodes2[b-1][0]
  nodes[b-1][0] += nodes2[a-1][0]
# print(nodes)

# index, c
r = list(zip(map(lambda x: x[1], nodes), c))
r.sort(key=lambda x: x[0])
# print(r)
count = 0
for a, b in ab:
  count += min(r[a-1][1], r[b-1][1])
print(count)
print(' '.join(map(lambda x: str(x[1]), r)))