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:
#!/usr/bin/env python
from collections import Counter
N = int(input())
A, B = [], []
for i in range(1, N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
C = [int(i) for i in input().split()]
C.sort(reverse=True)
com = A + B
cnt = Counter(com)
dict = {}
i = 0
scores = []
for key in cnt.keys():
    dict[key] = C[i]
    i += 1

cost = 0
for a, b in zip(A, B):
    cost += min(dict[a], dict[b])
print(cost)
print(*C)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

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

c.sort(reverse = True)

tree = {}
for i in range(N):
    tree[i] = []
for i in range(N-1):
    a,b = ab[i]
    a -= 1
    b -= 1
    tree[a] += [b]
    tree[b] += [a]

# print(tree)
idx =  sorted(tree, key=lambda k:len(tree[k]))
idx.reverse()

node = [0 for i in range(N)]
for i,index in enumerate(idx):
    node[index] = c[i]

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

n = int(input())

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

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

value = 0
ans = [0] * n
memo = [0] * n
q = deque([0])
i = 0

while q:
    v = q.popleft()
    ans[i] = c[v]
    memo[i] = 1
    if i > 0:
        value += c[i]
    i += 1
    for nv in graph[v]:
        if memo[nv] == 1:
            continue
        memo[nv] = 1
        q.append(nv)

print(value)
print(*ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
cnt = {}
ans = {}
pair = []
for i in range(1, n + 1):
    cnt[i] = 0
    ans[i] = 0

for _ in range(n - 1):
    a, b = list(map(int, input().split()))
    cnt[a] += 1
    cnt[b] += 1
    pair.append([a, b])

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

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

for ci, cnti in zip(c, cnt):
    ans[cnti] = ci

sum = 0
for i in range(n - 1):
    a, b = pair[i]
    sum += min(ans[a], ans[b])

print(sum)
print(*ans.values())

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

Submission status: Wrong Answer

Solution code:
n = int(input())

vertexes = [0 for k in range(n)]

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

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

vertexesKeys = sorted(range(len(vertexes)), key=lambda k: vertexes[k], reverse=True)
c = sorted(c, reverse=True)

ansVertexes = [0 for k in range(n)]
for i in range(n):
    ansVertexes[vertexesKeys[i]] = c[i]

ans = 0
ansStr = ""
for i in range(n-1):
    ans += min(ansVertexes[i], ansVertexes[i+1])
    ansStr += str(ansVertexes[i]) + " "

ansStr += str(ansVertexes[len(ansVertexes)-1])

print(ans)
print(ansStr)

Submission status: Wrong Answer

Solution code:
n = int(input())
list1 = [input().split() for i in range(n-1)]
list2 = list(map(int,input().split()))
print(sum(list2)-max(list2))
print(' '.join(str(a) for a in list2))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    edges = []
    counts = {i: 0 for i in range(N)}

    for i in range(N-1):
        a, b = [int(n) for n in input().split()]
        a, b = a-1, b-1
        edges.append((a,b))
        counts[a] += 1
        counts[b] += 1
    c = [int(n) for n in input().split()]
    c.sort()
    res = [0] * N
    for index, item in enumerate(sorted(list(counts.items()), key=lambda x: x[1])):
        res[item[0]] = c[index]
    score = 0
    for e in edges:
        score += min(res[e[0]], res[e[1]])
    print(score)
    print(" ".join([str(i) for i in res]))
main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
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:
#

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 = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        edges.append((a-1, b-1))
        d[a-1] += 1
        d[b-1] += 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)
    for i in range(N):
        d[i] = (C[i], d[i][1])
    d.sort(key=lambda v: v[1])
    ans = [v[0] for v in d]

    val = 0
    for a, b in edges:
        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 defaultdict

from math import factorial
# 組み合わせ
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))


def main():
    num = int(input())

    node_omomi = defaultdict(int)
    data_dic = []

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

    node_omomi = sorted(node_omomi.items(), key=lambda x: x[1])

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

    ans_omomi = [-1 for i in range(num + 1)]

    for i in range(num):
        node, omomi = node_omomi[i]
        ans_omomi[node] = omomi_data[i]

    final_omomi = 0
    for i in range(num - 1):
        kari = min(ans_omomi[data_dic[i][0]], ans_omomi[data_dic[i][1]])
        final_omomi += kari
    print(final_omomi)
    print(' '.join(list(map(str, ans_omomi[1:]))))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
x = []
d = []
for i in range(n-1):
    a,b = map(int,input().split())
    l.append(a)
    x.append(b)
c = list(map(int,input().split()))
for i in range(len(l)):
    d.append(min(c[l[i]-1],c[x[i]-1]))
print(sum(d))
print(*c)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[]
for i in range(n-1):
    a=list(map(int,input().split()))
    l.append(a)
s=list(map(int,input().split()))
memo=[[i,0] for i in range(n)]
for i  in range(n-1):
    memo[l[i][1]-1][1]+=1
    memo[l[i][0]-1][1]+=1
s.sort()
ans=0
for i in range(n-1):
    ans+=s[i]
print(ans)
memo.sort(key=lambda x:x[1])
ansl=[0 for i in range(n)]
for i in range(n):
    ansl[memo[i][0]]=s[i]
for i in range(n):
    print(ansl[i],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()
use.sort()

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:
from collections import Counter
n = int(input())
num = []
for _ in range(n-1):
    a, b = map(int,input().split())
    num.append(a)
    num.append(b)
    
c = list(map(int,input().split()))
c.sort(reverse=True)
ct = Counter(num)
most = ct.most_common()

ans = [0 for _ in range(n)]
for x, (d, e) in zip(c, most):
    ans[d-1] = x
print(sum(c[1:]))
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


n = int(input())
info = [list(map(int, input().split())) for i in range(n-1)]
c = list(map(int, input().split()))
c = sorted(c)
pos = [[0,i] for i in range(n)]
tree = [[] for i in range(n)]

for i in range(n-1):
    tree[info[i][0] - 1].append(info[i][1]-1)
    pos[info[i][0] - 1][0] += 1
    tree[info[i][1] - 1].append(info[i][0]-1)
    pos[info[i][1] - 1][0] += 1

pos = sorted(pos)
ans = []
for i in range(n):
    ans.append([pos[i][1],c[i]])
ans = sorted(ans)
max_ans = 0

q = deque()
q.append([-1, 0])
visited = [False]*n
visited[0] = True
while q:
    prev_pos, now_pos = q.popleft()
    if prev_pos != -1:
        max_ans += min(ans[prev_pos][1], ans[now_pos][1])
    for i in tree[now_pos]:
        if not visited[i]:
            visited[i] = True
            q.append([now_pos, i])
print(max_ans)
for i in range(n-1):
    print(str(ans[i][1]) + " ", end="")
print(ans[n-1][1], end="")
print()

Submission status: Wrong Answer

Solution code:
import heapq

N = int(input())
branches = [0 for _ in range(N)]
branch_pairs = []

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

branche_queue = []
for i, branch in enumerate(branches):
    heapq.heappush(branche_queue, (branch, i))

C = list(map(int, input().split()))
c_queue = []
for c in C:
    heapq.heappush(c_queue, c)

ans = [0 for _ in range(N)]
for _ in range(N):
    _, i = heapq.heappop(branche_queue)
    c = heapq.heappop(c_queue)
    ans[i] = c

max_ans = 0
for a, b in branch_pairs:
    max_ans += min(ans[a], ans[b])

print(max_ans)
print(*ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = list(list(map(int,input().split())) for i in range(N-1))
c = list(map(int,input().split()))
c.sort()
print(sum(c)-c[-1])
tree = []
for i in range(N):
    tree.append([0,i])
for a,b in ab:
    tree[a-1][0] += 1
    tree[b-1][0] += 1
tree.sort()
ans = [0]*N
for j,i in tree:
    ans[i] = c.pop(0)
for i in ans:
    print(i,end = " ")

Submission status: Wrong Answer

Solution code:
n=int(input())
a,b=[],[]
m=[[0,i+1]for i in range(n)]
for i in range(n-1):
  aa,bb=map(int,input().split())
  a.append(aa);b.append(bb)
  m[aa-1][0]+=1;m[bb-1][0]+=1
m.sort()
c=list(map(int,input().split()))
c.sort()
mm=[0 for _ in range(n)]
for i in range(n):mm[m[i][1]-1]=c[i]
ans=0
for i in range(n-1):ans+=min(mm[a[i]-1],mm[b[i]-1])
print(ans)
print(*mm)

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

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

c.sort()

tree = {}
for i in range(N):
    tree[i] = []
for i in range(N-1):
    a,b = ab[i]
    a -= 1
    b -= 1
    tree[a] += [b]
    tree[b] += [a]

# print(tree)
idx =  sorted(tree, key=lambda k:len(tree[k]))

node = [0 for i in range(N)]
for i,index in enumerate(idx):
    node[index] = c[i]

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

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

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

c.sort()

tree = {}
for i in range(N):
    tree[i] = []
for i in range(N-1):
    a,b = ab[i]
    a -= 1
    b -= 1
    tree[a] += [b]
    tree[b] += [a]

print(tree)
idx =  sorted(tree, key=lambda k:len(tree[k]))

node = [0 for i in range(N)]
for i,index in enumerate(idx):
    node[index] = c[i]

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

Submission status: Wrong Answer

Solution code:

def main():
    buf = input()
    N = int(buf)
    edge = dict()
    ab = []
    for i in range(N):
        edge[i] = [] # zero index
    for i in range(N-1):
        buf = input()
        buflist = list(buf.split())
        a = int(buflist[0])-1 # zero index
        b = int(buflist[1])-1 # zero index
        edge[a].append(b)
        edge[b].append(a)
        ab.append((a, b))
    buf = input()
    buflist = buf.split()
    c = list(map(int, buflist))
    c = list(sorted(c, reverse=True))
    point = 0
    assigned = []
    weight = []
    for i in range(N):
        assigned.append(False)
        weight.append(0)
    for k, v in sorted(edge.items(), key=lambda x: -len(x[1])):
        if not assigned[k]:
            weight[k] = c[point]
            assigned[k] = True
            point += 1
        for node in v:
            if not assigned[node]:
                weight[node] = c[point]
                assigned[node] = True
                point += 1
    total = 0
    for x in ab:
        total += min(weight[x[0]], weight[x[1]])
    print(total)
    print(' '.join(list(map(str, weight))))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(1000000) #再帰の深さを十分深く設定


n=int(input())
ab = [sorted([int(i)-1 for i in input().split()]) for j in range(n-1)]
c = [int(i) for i in input().split()]
c.sort(reverse = True)

print(sum(c)-max(c))

ko = [[] for i in [0]*n]

for a,b in ab:
    ko[a].append(b)
    
ans = [0]*n
pt=0 
#print(ab)
#print(ko)
def dfs(x):
    global pt #numbたちがグローバル変数だと教えてあげる
    #(x,y)地点を訪問済みにする
    #(x,y)地点での処理を行う（マスの色をカウントするなど）
    ans[x] = c[pt]
    pt+=1
    #foreach((nx,ny) \in (x,y)のお隣さん){(nx,ny)に訪問していないとき、dfs(nx,ny)} 
    for i in ko[x]:
        dfs(i)
        
dfs(0)

print(*ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

ab = []

for i in range(N-1):
    ab.append(list(map(int, input().split())))

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

Nnum = [0]*N

for a, b in ab:
    Nnum[a-1] += 1
    Nnum[b-1] += 1

print(Nnum)

d = [-1]*N

for i in c:
    idx = Nnum.index(min(Nnum))
    d[idx] = i
    Nnum[idx] = N

score = 0

for a, b in ab:
    score += min(d[a-1],d[b-1])

print(score)
s = ""
for i in d:
    s += str(i) + " "
print(s)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N = _i()

n_edges = [0] * N
edge_list = []
for _ in range(N-1):
    a, b = _li_()
    edge_list.append((a, b))
    n_edges[a] += 1
    n_edges[b] += 1

c_list = _li()
c_list.sort(reverse=True)
c_list = np.array(c_list)
index = np.argsort(n_edges)[::-1]
ans_edges = np.zeros(N, dtype=int)
ans_edges[index] = c_list
ans = 0
for edge in edge_list:
    ans += min(ans_edges[edge[0]], ans_edges[edge[1]])

print(ans)
print(*ans_edges)

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()
c.reverse()
L=[[0,i+1] for i in range(10000)]
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()
L.reverse()
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:
def getN():
    return int(input())

def getMN():
    return list(map(int, input().split()))

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

n =getN()

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

for i in range(n-1):
    a, b = getlist()
    nodes[a-1] += 1
    nodes[b-1] += 1


nodes = [(node, i) for i, node in enumerate(nodes)]
scores = sorted(getlist(), reverse=True)
nodes = sorted(nodes, key=lambda x: -x[0])
#print(nodes, scores)

print(sum(scores[1:]))
prlist = [0 for i in range(n)]
for i, j in zip(scores, nodes):
    prlist[j[1]] = i

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


"""
5
2 1
2 3
2 4
2 5
1 2 3 4 5
"""

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

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

for ai, bi in ab:
    table[ai - 1].append(bi)
    table[bi - 1].append(ai)

itab = list(enumerate(table))
itab.sort(key=lambda x: -len(x[1]))
c.sort(key=lambda x: -x)

nodes = [None] * N
for ci, (i, row) in zip(c, itab):
    nodes[i] = ci

ans = 0
for ai, bi in ab:
    ans += min(nodes[ai - 1], nodes[bi - 1])

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

Submission status: Wrong Answer

Solution code:
N = int(input())
es = [[idx, []] for idx in range(N)]
# es[idx]:=[idx,[隣接リスト]]

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

c = list(map(int, input().split()))
c.sort()
# スコアが小さい順にソート

es.sort(key=lambda x: len(x[1]))
# print(es)
# 隣接頂点数が少ない順にソート

# 隣接頂点数が少ない頂点から順に、小さなスコアを書き込む
# 小さなスコアが採用されるので、小さなスコアが関わる回数を減らしたいということ

v = [-1] * N
cur = 0

ans = 0
score = [[-1] * N for _ in range(N)]
for idx, lst in es:
    v[idx] = c[cur]
    for nv in lst:
        if idx < nv:
            v_from, v_to = idx, nv
        else:
            v_from, v_to = nv, idx
        if score[v_from][v_to] == -1:
            score[v_from][v_to] = v[idx]
            ans += v[idx]
    cur += 1
print(ans)
print(*v)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())

edge = [[] for _ in range(N)]
for _ 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()
c = c[::-1]
ans = [0 for i in range(N)]

d = [-1 for i in range(N)]
d[0] = 0
ans[0] = c[0]
q = deque([0 * (N - 1)])
while len(q) > 0:
    u = q.popleft()
    for v in edge[u]:
        if d[v] > -1:
            continue
        d[v] = d[u] + 1
        ans[v] = c[v]
        q.append(v)

print(sum(c) - c[0])
print(*ans, sep=" ")

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)


def main():
    n = I()
    aa = [LI_() for _ in range(n-1)]
    c = sorted(LI(), reverse=True)
    e = collections.defaultdict(set)
    for a,b in aa:
        e[a].add(b)
        e[b].add(a)

    ci = 0
    q = [0]
    v = set([0])
    r = [0] * n
    while q:
        nq = []
        for t in q:
            print(t,ci)
            r[t] = c[ci]
            ci += 1
            for nt in e[t]:
                if nt in v:
                    continue
                v.add(nt)
                nq.append(nt)
        q = nq

    return '{}\n{}'.format(sum(c[1:]), ' '.join(map(str, r)))


print(main())

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    print(180*(n-2))
    return

#B
def B():
    s = S()
    res = 15-len(s)
    k = s.count("o")
    if k+res >= 8:
        print("YES")
    else:
        print("NO")
    return

#C
def C():
    n,a,b,c = LI()
    return

#D
def D():
    n = I()
    v = [[] for i in range(n)]
    f = [[0,i] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        f[a][0] += 1
        f[b][0] += 1
    f.sort(key = lambda x:-x[0])
    c = LI()
    c.sort(key = lambda x:-x)
    for i in range(n):
        f[i][0] = c[i]
    f.sort(key = lambda x:x[1])
    ans = 0
    q = deque()
    q.append(0)
    bfs = [1 for i in range(n)]
    bfs[0] = 0
    while q:
        x = q.popleft()
        for y in v[x]:
            ans += min(f[x][0],f[y][0])
            if bfs[y]:
                bfs[y] = 0
                q.append(y)
    print(ans//2)
    for i, j in f[:-1]:
        print(i,end = " ")
    print(f[-1][0])
    return

#E
def E():
    n = I()
    return

#F
def F():
    n = I()
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Wrong Answer

Solution code:
I=lambda:map(int,input().split())
N = int(input())
T = {i+1:[] for i in range(N)}
E = []
for _ in range(N-1):
    a,b = I()
    E += [[a,b]]
    T[a] += [b]
    T[b] += [a]
Cs = sorted(list(I()))
l = sorted(T.keys(), key=lambda k:len(T[k]))
#print(l)
S = {l[i]:Cs[i] for i in range(N)}
M = 0
for a,b in E:
    M += min(S[a], S[b])
print(M)
print(*[S[i+1] for i in range(N)])

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    print(180*(n-2))
    return

#B
def B():
    s = S()
    res = 15-len(s)
    k = s.count("o")
    if k+res >= 8:
        print("YES")
    else:
        print("NO")
    return

#C
def C():
    n,a,b,c = LI()
    return

#D
def D():
    n = I()
    v = [[] for i in range(n)]
    f = [[0,i] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        f[a][0] += 1
        f[b][0] += 1
    f.sort(key = lambda x:-x[0])
    c = LI()
    for i in range(n):
        f[i][0] = c[i]
    f.sort(key = lambda x:x[1])
    ans = 0
    q = deque()
    q.append(0)
    bfs = [1 for i in range(n)]
    bfs[0] = 0
    while q:
        x = q.popleft()
        for y in v[x]:
            ans += min(f[x][0],f[y][0])
            if bfs[y]:
                bfs[y] = 0
                q.append(y)
    print(ans//2)
    for i, j in f[:-1]:
        print(i,end = " ")
    print(f[-1][0])
    return

#E
def E():
    n = I()
    return

#F
def F():
    n = I()
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Wrong Answer

Solution code:
N = int(input())
T = [[] for i in range(N)]
Edge = []
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append(b)
    T[b].append(a)
    Edge.append((a, b))
C = sorted(list(map(int, input().split())), reverse=True)

out = [(i, len(T[i])) for i in range(N)]
out.sort(key=lambda x: x[1], reverse=True)

P = [-1] * N
for (i, x), c in zip(out, C):
    P[i] = c


ans = 0
for a, b in Edge:
    ans += min(P[a], P[b])

print(ans)
print(*P, sep=' ')

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    print(180*(n-2))
    return

#B
def B():
    s = S()
    res = 15-len(s)
    k = s.count("o")
    if k+res >= 8:
        print("YES")
    else:
        print("NO")
    return

#C
def C():
    n,a,b,c = LI()
    return

#D
def D():
    n = I()
    v = [[] for i in range(n)]
    f = [[0,i] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        f[a][0] += 1
        f[b][0] += 1
    f.sort(key = lambda x:x[0])
    c = LI()
    for i in range(n):
        f[i][0] = c[i]
    f.sort(key = lambda x:x[1])
    ans = 0
    q = deque()
    q.append(0)
    bfs = [1 for i in range(n)]
    bfs[0] = 0
    while q:
        x = q.popleft()
        for y in v[x]:
            ans += min(f[x][0],f[y][0])
            if bfs[y]:
                bfs[y] = 0
                q.append(y)
    print(ans//2)
    for i, j in f[:-1]:
        print(i,end = " ")
    print(f[-1][0])
    return

#E
def E():
    n = I()
    return

#F
def F():
    n = I()
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(1000000)


def depth(n):
    if d[n]!=-1:
        return d[n]
    seen[n]=1
    ret=0
    for g in G[n]:
        if seen[g]==1:continue
        seen[g]=1
        temp=1+depth(g)
        ret=max(ret,temp)
    return ret

dep=[]
for i in range(N):
    d=[-1]*N
    seen=[0]*N
    de=depth(i)
    d[i]=de
    dep.append([de,i])

dep.sort()
c.sort(reverse=True)

ans=[-1]*N
for i in range(N):
    ans[dep[i][1]]=c[i]

print(sum(c)-max(c))
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
C = sorted(map(int, input().split()), reverse=True)
print(sum(C[1:]))
L = [-1]*n
L[0] = C[0]
L[T[0][0]] = C[1]
used = [0, T[0][0]]
for i in range(2, n):
  for v in used:
    for nv in T[v]:
      if L[nv] == -1:
        L[nv] = C[i]
        used.append(nv)
        break
    else:
      continue
    break
print(*L)