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:
N = int(input())

tree_hash = {}

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

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

c.sort()
c.reverse()
tree_hash = sorted(tree_hash.items(), key=lambda x: -len(x[1]))

point_list = [0] * N
#keysはノードの番号が入っている。ノード番号のいち＝ポイントの配列を作る
for i in range(len(tree_hash)):
    point_list[tree_hash[i][0] - 1] = c[i]

ans = 0
for i in tree_hash:
    for j in i[1]:
        ans += min(point_list[i[0] - 1], point_list[j - 1])
print(int(ans / 2)) 
print(" ".join(map(str, point_list)))

Submission status: Wrong Answer

Solution code:
N = int(input())
eg = []
v = [0 for i in range(N)]

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

c = [int(i) for i in input().split()]

for i in range(N):
    v[i] = (v[i], i)

v.sort()
c.sort()

ans2 = [0 for i in range(N)]
for i, p in enumerate(v):
    val, idx = p
    ans2[idx] = c[i]

ans = 0
for a, b in eg:
    ans += min(ans2[a], ans2[b])

print(ans)
print(*ans2)

Submission status: Wrong Answer

Solution code:
n = int(input())
edge = [list(map(int, input().split())) for _ in range(n - 1)]
c = sorted(map(int, input().split()))
count = dict(zip([key for key in range(1, n + 1)], [0 for _ in range((n))]))
for v, u in edge:
    count[v] += 1
    count[u] += 1
keys = [key for key, value in sorted(count.items(), key=lambda x: x[1])]
M = 0
w = dict(zip([key for key in range(1, n + 1)], [0 for _ in range((n))]))
for key, x in zip(keys, c):
    w[key] = x
for u, v in edge:
    M += min(w[u], w[v])
print(M)
for key in range(1, n + 1):
    print(w[key], end=' ')

Submission status: Wrong Answer

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

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n=I()
  p=[]
  for _ in range(n-1):
    p.append(LI())

  l=[[] for i in range(n+1)]
  for pi in p:
    l[pi[0]].append(pi[1])
    l[pi[1]].append(pi[0])

  l2=LI()
  l2.sort()
  print(sum(l2[:-1]))
  print(' '.join(str(x) for x in l2))

main()

Submission status: Wrong Answer

Solution code:
N = int(input())
ab_list=list()
count_list={str(i+1): 0 for i in range(N)}

for _ in range(N-1):
    a, b = map(int, input().split())
    count_list[str(a)] += 1
    count_list[str(b)] += 1
    ab_list.append([a,b])
c_list = list(map(lambda x: int(x), input().split()))
c_list.sort(reverse=True)
count_list = sorted(count_list.items(), key=lambda x:-x[1])
ans = 0
ans_list = [0]*N
i = 0
for ll in count_list:
    ans_list[int(ll[0])-1] += c_list[i]
    i += 1

for ab in ab_list:
    a, b = ab
    ans += min(ans_list[a-1], ans_list[b-1])
print(ans)
ans_str = ""
for i in ans_list:
    ans_str += str(i)+ " "
print(ans_str)

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][::-1]:
        tmp=p.pop()
        ans[i-1]=tmp
        score+=min(tmp,ans[point-1])
        dfs(i)


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

Submission status: Wrong Answer

Solution code:


def main():
    n = input()
    edges = []
    nodes = [0] * n
    children = {i: [] for i in xrange(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
        children[a].append(b)
        children[b].append(a)
    nodes = sorted([node for node in xrange(n)],
                   key=lambda i: (nodes[i], sum(nodes[j] for j in children[i])))
    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:
import numpy as np
N = int(input())
number_count = np.zeros(N)

a_b = []
for i in range(N-1):
	a , b = map(int,input().split())
	a_b.append([a,b])
	number_count[a - 1] += 1
	number_count[b - 1] += 1
temp_ans = (np.argsort(number_count))
c = list(map(int,input().split()))
c.sort()

ans = np.zeros(N)
for i in range(N):
	ans[temp_ans[i]] = c[i]
total = 0
for i in range(N-1):
	total += int(min(ans[a_b[i][0]-1],ans[a_b[i][1]-1]))
print(total)
for ans_ in ans:
	print(int(ans_),end=" ")

Submission status: Wrong Answer

Solution code:
N = int(input())
if N == 1:
    C1, C2 = map(int, input().split())
    print(min(C1, C2))
    print(str(C1) + ' ' + str(C2))
    quit()

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

T = [[i, 0] for i in range(N)]
for a, b in AB:
    T[a-1][1] += 1
    T[b-1][1] += 1

T = sorted(T, key=lambda x: x[1])
C = sorted(C)
ans_d = sorted([[C[i], T[i][0]] for i in range(N)], key=lambda x: x[1])
ans_d = [str(a[0]) for a in ans_d]
M = 0
for a, b in AB:
    M += min(int(ans_d[a-1]), int(ans_d[b-1]))

print(M)
print(' '.join(ans_d))

Submission status: Wrong Answer

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

count=[0]*n
for i in range(1,n):
  count[i-1]=A.count(i)

rank=[0]*n
k=0
num=0
for i in range(n):
  k=count.index(max(count))
  count[k]=-1
  rank[k]=num
  num+=1
  
d=[0]*n
for i in range(n):
  d[i]=c[rank[i]]
m=0
for i in range(n-1):
  m+=min(d[a[i][0]-1],d[a[i][1]-1])
print(m)
for i in range(n):
  print(d[i],end=' ')

Submission status: Wrong Answer

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

edge_count = [[0, i] for i in range(N)]

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


for i in range(N-1):
    ai, bi = edge[i]
    edge_count[ai][0] += 1
    edge_count[bi][0] += 1

edge_count = sorted(edge_count)

for i, eg in enumerate(edge_count):
    ans[eg[1]] = c[i]

ans_sum = 0

for i in range(N-1):
    ai, bi = edge[i]
    ans_sum += min(ans[ai], ans[bi])

print(ans_sum)
print(*ans)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy as dp
n = int(input())
a = []
b = []
count = [0]*n
for _ in range(n-1):
  aa,bb = map(int,input().split())
  count[aa-1] += 1
  count[bb-1] += 1
  a.append(aa)
  b.append(bb)
c = list(map(int,input().split()))
count2 = dp(count)
for _ in range(n):
  tmp = str(max(c))
  c.remove(max(c))
  temp = count.index(max(count2))
  count[temp] = tmp
  count2.remove(max(count2))
s = 0
countint = [0]*n
for _ in range(n):
  countint[_] = int(count[_])
for _ in range(n-1):
  s += min(countint[a[_]-1],countint[b[_]-1])
print(s)
print(' '.join(count))

Submission status: Wrong Answer

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

num = max(c)
goukei = sum(c)

print(goukei - num)
c.sort()
print(*c)

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][::-1]:
        tmp=p.pop()
        ans[i-1]=tmp
        score+=tmp
        dfs(i)


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

Submission status: Wrong Answer

Solution code:
N = int(input())
ab_list=list()
count_list={str(i+1): 0 for i in range(N)}

for _ in range(N-1):
    a, b = map(int, input().split())
    count_list[str(a)] += 1
    count_list[str(b)] += 1
    ab_list.append([a,b])
c_list = list(map(lambda x: int(x), input().split()))
c_list.sort(reverse=True)
count_list = sorted(count_list.items(), key=lambda x:-x[1])
ans = 0
ans_list = [0]*N
i = 0
for ll in count_list:
    ans_list[int(ll[0])-1] += c_list[i]
    i += 1

for ab in ab_list:
    a, b = ab
    ans += min(ans_list[a-1], ans_list[b-1])
print(ans)
print(ans_list)

Submission status: Wrong Answer

Solution code:
N = int(input())

pairs = []
ref = [0] * N
for _ in range(N-1):
    a, b = map(int, input().split())
    pairs.append((a, b))
    ref[a - 1] = ref[a - 1] + 1
    ref[b - 1] = ref[b - 1] + 1

ref_map = []
for i in range(N):
    ref_map.append((ref[i], i))
ref_map = sorted(ref_map)

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

ans = [0] * N
for i in range(N):
    ans[ref_map[i][1]] = c[i]

score = 0
for a, b in pairs:
    if ans[a - 1] >= ans[b - 1]:
        score = score + ans[b - 1]
    else:
        score = score + ans[a - 1]

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

Submission status: Wrong Answer

Solution code:
N = int(input())
L = [list(map(int,input().split())) for k in range(N-1)]
c = list(map(int,input().split()))
G = [[0,k] for k in range(N)]
for e in L:
    G[e[0]-1][0] += 1
    G[e[1]-1][0] += 1
c = sorted(c)
G = sorted(G)
ans = [0 for k in range(N)]
for k in range(N-1):
    ans[G[k][1]] = c[k]
ans[G[N-1][1]] = c[-1]

print(sum(c)-max(c))
print(*ans, sep = " ")

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in range(n-1)]

    count = [[i, 0] for i in range(n)]
    for i in range(n-1):
        count[ab[i][0]-1][1] += 1
        count[ab[i][1]-1][1] += 1
    c = sorted(list(map(int, input().split())), reverse=True)
    count = sorted(count, reverse=True, key=lambda x:x[1])

    d = [[count[i][0], c[i]] for i in range(n)]
    d = sorted(d, key=lambda x:x[0])
    d_ = [dd[1] for dd in d]

    sum = 0
    for i in range(n-1):
        sum += min(d[ab[i][0]-1][1], d[ab[i][1]-1][1])
    print(sum)
    print(*d_)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# ナイーブに書く
N = int(input())
conn = [[0,0] for _ in range(N)]# 加算していくので、list内包表記で定義
edge = []
write = [0]*N
score = [0]*(N-1)

# edgeの受け取り
for i in range(N-1):
    conn[i][0] = i
    a, b = map(int, input().split())
    edge.append((a-1, b-1))
    conn[a-1][1] += 1
    conn[b-1][1] += 1
conn[N-1][0] += N-1

# 整数の格納、降順ソート
num = list(map(int, input().split()))
num.sort(reverse=True)

# 接続数で降順ソート
conn.sort(key=lambda x: x[1], reverse=True)

# 接続数の多い順に値を格納
for i, c in enumerate(conn):
    write[c[0]] = num[i]

# スコア計算
for i, (a, b) in enumerate(edge):
    score[i] = min(write[a], write[b])

# 結果の出力
print(sum(score))
print(" ".join([str(i) for i in write]))

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


D = defaultdict(int)
val = 0
while True:
	LL = []
	for i in G.node:
		if G.node[i] == 1:
			LL.append(i)
	for i in LL:
		 D[i] = c[val]
		 val += 1
		 G.node[i] -= 1
		 for j in G.graph[i]:
		 	G.node[j] -= 1
	if LL == []:
		break


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

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

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

Submission status: Wrong Answer

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

edge_count = [[0, i] for i in range(N)]

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

print(edge)

for i in range(N-1):
    ai, bi = edge[i]
    edge_count[ai][0] += 1
    edge_count[bi][0] += 1

edge_count = sorted(edge_count)

for i, eg in enumerate(edge_count):
    ans[eg[1]] = c[i]

ans_sum = 0

for i in range(N-1):
    ai, bi = edge[i]
    ans_sum += min(ans[ai], ans[bi])

print(ans_sum)
print(*ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
B = []
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()))

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

print(sum(_list))

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()))
from queue import Queue
import copy
n =getN()

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

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


nodes = [(node, i) for i, node in enumerate(nodes)]
serve = copy.deepcopy(nodes)
scores = sorted(getlist(), reverse=True)
nodes = sorted(nodes, key=lambda x: -len(x[0]))
start = nodes[0][1]
# print(nodes, start)

def bfs(nodes, start, n):
    state = [0] * n
    state[start] = 1
    prior = [0] * n
    q = Queue()
    pridx = 0
    q.put(start)
    while(not q.empty()):
        next = q.get()
        for nx in serve[next][0]:
            if state[nx] == 0:
                q.put(nx)
                state[nx] = 1
                pridx += 1
                prior[nx] = pridx

    return prior

prior = bfs(nodes, start, n)
#print(prior)

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

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


"""
7
1 2
3 2
2 4
4 5
5 6
5 7
1 2 3 4 5 6 7
"""

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [0]*(N-1)
b = [0]*(N-1)
for i in range(N-1):
  a[i],b[i] = map(int,input().split())
c = list(map(int,input().split()))
index = 0
sorted(c,reverse= True)
edges = []
nodes = dict()
for i in range(N-1):
  if a[i] not in nodes:
    nodes[a[i]] = c[index]
    index += 1
  if b[i] not in nodes:
    nodes[b[i]] = c[index]
    index += 1
  edges.append(min(nodes[a[i]], nodes[b[i]]))

print(sum(edges))
for i in range(N):
  if i:
    print(" ",end="")
  print(nodes[i+1], end="")
print()

Submission status: Wrong Answer

Solution code:
from collections import deque
N=int(input())
A=[0 for i in range(N-1)]
B=[0 for i in range(N-1)]
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    A[i],B[i]=a,b
    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)]
q=deque([0])
while(len(q)>0):
    r=q.popleft()
    d[r]=c.pop()
    for p in G[r]:
        q.appendleft(p)
M=0
for i in range(N-1):
    M+=min(d[A[i]],d[B[i]])
print(M)
print(" ".join([str(i) for i in d]))

Submission status: Wrong Answer

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

count=[0]*n
for i in range(1,n):
  count[i-1]=A.count(i)

rank=[0]*n
k=0
num=0
for i in range(n):
  k=count.index(max(count))
  count[k]=-1
  rank[k]=num
  num+=1
  
d=[0]*n
for i in range(n):
  d[i]=c[rank[i]]
m=0
for i in range(n-1):
  m+=min(d[a[i][0]-1],d[a[i][1]-1])
print(m)
for i in range(n):
  print(d[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import Counter
import heapq

N = int(input())

sides = []
cnts = []
for _ in range(N-1):
    a, b = map(int, input().split())
    # cnts.append("{}".format(a))
    # cnts.append("{}".format(b))
    cnts.append(a)
    cnts.append(b)
    if a > b:
        a, b = b, a
    sides.append((a, b))

counts = Counter()
counts.update(cnts)
counts = counts.most_common()

cs = [int(c) for c in input().split()]
cs.sort(reverse=True)
cs = deque(cs)

cnts = {}
for index, _ in counts:
    # print(index)
    num = cs.popleft()
    cnts[index] = num

sum = 0
for side_a, side_b in sides:
    a = cnts[side_a]
    b = cnts[side_b]
    sum += min(a, b)

s = "{}".format(cnts[1])
for i in range(2, N+1):
    s += " {}".format(cnts[i])

print(sum)
print(s)

# print(sides)
# print(counts)
# print(cs)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

def readInt():
    return int(input())

def readList():
    return list(input().split())

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

def main():
    n = readInt()
    edges = {}
    edges2 = []
    for _ in range(n-1):
        a, b = readListI()
        edges.setdefault(a, set())
        edges.setdefault(b, set())
        edges[a].add(b)
        edges[b].add(a)
        edges2.append((a, b))
    lc = sorted(readListI())
    ret = {}
    for c in lc:
        tmp = sorted(edges.items(), key=lambda x: len(x[1]))
        e = tmp[0][0]
        ret[e] = c
        for e2 in edges[e]:
            edges[e2].remove(e)
        del edges[e]
    ans = 0
    for a, b in edges2:
        ans += min(ret[a], ret[b])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
node = [[0,i] for i in range(N)]
ab = []
for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1][0] += 1
    node[bi-1][0] += 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)

cn = [[c[i],node[i][1]] for i in range(N)]
cn.sort(key=lambda x:x[1])
ans = 0

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

print(' '.join([str(cn[i][0]) for i in range(N)]))

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(d)
print(score)
print(*ans[::-1])

Submission status: Wrong Answer

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

num = max(max(a), max(b))
goukei = sum(c)

print(goukei - num)
k = c[-1]
c.pop()
c = [k] + c
print(*c)

Submission status: Wrong Answer

Solution code:
N = int(input())

pair = []
dic = {}

for _ in range(N-1):
    a, b = list(map(int, input().split(" "))) 
    if a in dic.keys():
        dic[a] += 1
    else:
        dic[a] =1
        
    if b in dic.keys():
        dic[b] += 1
    else:
        dic[b] =1
    pair.append([a, b])

c = list(map(int, input().split(" ")))
c.sort(reverse=True)
c = c[:N+1]

ans = {}
i = 0
for k, v in sorted(dic.items(), key=lambda x: -x[1]):
    ans[k] = c[i]
    i += 1

total = 0
for a, b in pair:
    if ans[a] > ans[b]:
        total += ans[b]
    else:
        total += ans[a]

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

print(ans[N])

Submission status: Wrong Answer

Solution code:
N = int(input())

ab = []
for _ in range(N-1):
    ab += list(map(int, input().split()))

count = []
for i in range(1, N+1):
    a = ab.count(i)
    count += [[a, i]]

count.sort()


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

#scoreの最大値
score = 0
for i in c:
    score += i
print (score-i)

# print (ab)
# print ('count', count)
# print ('c', c)
ans = [0] * N
for i in range(N):
    ans[count[i][1]-1] = c[i]
str_ans = map(str, ans)
print (' '.join(str_ans))

Submission status: Wrong Answer

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

T = [[i, 0] for i in range(N)]
for a, b in AB:
    T[a-1][1] += 1
    T[b-1][1] += 1

T = sorted(T, key=lambda x: x[1])
C = sorted(C)
ans_d = sorted([[C[i], T[i][0]] for i in range(N)], key=lambda x: x[1])
ans_d = [str(a[0]) for a in ans_d]
M = 0
for a, b in AB:
    M += min(int(ans_d[a-1]), int(ans_d[b-1]))

print(M)
print(' '.join(ans_d))

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([a,b])
c = list(map(int, input().split()))
c.sort(reverse = True)

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

dig.sort(reverse = True)

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:
N=int(input())
sum=0
data=[]
data1=[]
for i in range(0,N-1):
  A,B=map(int,input().split())
  data.append(A)
  data.append(B)
  data1.append([A,B])

dcount=[]
for i in range(0,N):
  s=i+1
  dcount.append([data.count(s),s])
  
dcount.sort()  

  
C=list(map(int,input().split()))
C.sort()
data2=[]
for i in range(0,N):
  num1=dcount[i][1]
  num2=C[i]
  data2.append([num1,num2])
data2.sort()


ss=""
for i in range(0,N-1):
  ss=ss+str(data2[i][1])+str(" ")
  a=data1[i][0]-1
  b=data1[i][1]-1
  ap=data2[a][1]
  bp=data2[b][1]
  if ap<bp:
    sum=sum+ap
  else:
    sum=sum+bp
    
ss=ss+str(data2[N-1][1])
    
print(sum)
print(ss)

Submission status: Wrong Answer

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

node_childs = [0] * N
sol = [0] * N
score = 0
for branch in ab:
    node_childs[branch[0] -1] += 1
    node_childs[branch[1] -1] += 1

c = sorted(c, reverse=True)

for i in range(N):
    index = node_childs.index(max(node_childs))
    sol[index] = c[i]
    node_childs[index] = -1

for branch in ab:
    score += min(sol[branch[0] -1], sol[branch[1]-1])

print(score)
print(' '.join(list(map(str, sol))))

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(' '.join(map(str,d)))

Submission status: Wrong Answer

Solution code:
N = int(input())

pair = []
dic = {}

for _ in range(N-1):
    a, b = list(map(int, input().split(" "))) 
    if a in dic.keys():
        dic[a] += 1
    else:
        dic[a] =1
        
    if b in dic.keys():
        dic[b] += 1
    else:
        dic[b] =1
    pair.append([a, b])

c = list(map(int, input().split(" ")))
c.sort(reverse=True)
c = c[:N]

ans = {}
i = 0
for k, v in sorted(dic.items(), key=lambda x: -x[1]):
    ans[k] = c[i]
    i += 1

total = 0
for a, b in pair:
    if ans[a] > ans[b]:
        total += ans[b]
    else:
        total += ans[a]

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

print(ans[N])

Submission status: Wrong Answer

Solution code:
import itertools

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

ans=0
M=0
sum=0
d=[0]*n

for j in itertools.permutations(c):
    for i in range(n-1):
        qa=a[i]
        qb=b[i]
        pl=min(j[qa-1],j[qb-1])
        sum=sum+pl
    ans=max(ans,sum)
    sum=0

print(ans)

Submission status: Wrong Answer

Solution code:
# 問題D
# 方針:繋がっている辺が多い頂点には大きい数字を置く.
# 計算:ループさせる.
n = int(input())
connected_edge_count = {}
edge_list = []
node_list = [0]
for i in range(n-1):
    b, c = map(int, input().split())
    b=b-1
    c=c-1
    edge_list.append((b, c))
    node_list.append(0)
    if(b in connected_edge_count):
        connected_edge_count[b] += 1
    else:
        connected_edge_count[b] = 1
    if(c in connected_edge_count):
        connected_edge_count[c] += 1
    else:
        connected_edge_count[c] = 1
connected_edge_count = sorted(connected_edge_count.items(), reverse=True)
num_list = list(map(int, input().split()))
counter = 0
for node in connected_edge_count:
    node_list[node[0]] = num_list[counter]
    counter += 1
score = 0
for edge in edge_list:
    score += min(node_list[edge[0]], node_list[edge[1]])
print(score)
print(" ".join(str(e) for e in node_list))

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)], reverse=True)
    cc = map(int, raw_input().split())
    cc.sort(reverse=True)
    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())

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

D = {}
for i in L:
    if i[0] in D:
        D[i[0]] += 1
    else:
        D[i[0]] = 1
        
    if i[1] in D:
        D[i[1]] += 1
    else:
        D[i[1]] = 1

D_sort = sorted(D.items(), key=lambda x:x[1], reverse=True)
C_sort = sorted(C)

M = sum(C_sort[0:N-1])
index = D_sort[0][0] - 1 

check = []
for c in C_sort[0:N-1]:
    check.append(c)
    
    
ans = check[0:index] + [C_sort[N-1]] + check[index:N] 
print(M)
print(*ans)

Submission status: Wrong Answer

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


def solve(N: int, a: "List[int]", b: "List[int]", C: "List[int]"):
    conn = [[] for _ in range(N + 1)]
    for i in range(N - 1):
        conn[a[i]].append(b[i])
        conn[b[i]].append(a[i])
    counts = [[] for _ in range(N)]
    for i in range(1, N + 1):
        counts[i - 1] = [len(conn[i]), conn[i], 0, i - 1]
    counts.sort(key=lambda x: x[0])

    ret = 0
    #print(counts)
    C.sort()
    for i, cnt in enumerate(counts):
        cnt[2] = C[i]
        ##ret += C[i] * cnt[0]
        #for node in cnt[1]:
        #    counts[node - 1][0] -= 1
    vals = [0] * N
    for cnt in counts:
        vals[cnt[3]] = cnt[2]
    for i in range(N - 1):
        ret += min(vals[a[i] - 1], vals[b[i] - 1])
    print(ret)
    print(' '.join([str(v) for v in vals]))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]" 
    b = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    c = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, a, b, c)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import defaultdict
N = int(input())
tree = defaultdict(list)
degree = [0 for i in range(N)]
edges = [0 for i in range(N-1)]
for i in range(N-1):
    a, b = map(int, input().split())
    edges[i] = (a, b)
    tree[a].append(b)
    tree[b].append(a)
for k, v in tree.items():
    degree[k-1] = len(v)
# print(degree)
sort_i = np.argsort(degree)
# print(sort_i)
C = list(map(int, input().split()))
C = list(sorted(zip(sorted(C), list(sort_i)),key=lambda x: x[1]))
# print(C[sort_i])
ans = 0
for e in edges:
    ans += min(C[e[0]-1][0], C[e[1]-1][0])
    # print(ans)
print(ans)
print(' '.join(list(map(lambda x: str(x[0]), C))))