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())
par = [-1] * N  # 親だった場合は-(その集合のサイズ)

if N == 1:
    print(0)


# xがどのグループに属しているか調べる
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return find(par[x])


# 自分のいるグループの数
def size(x):
    return -par[find(x)]


# xとyの属する集合を併合
def unite(x, y):
    # 根を探す
    x, y = find(x), find(y)

    # 根が一緒
    if x == y:
        return

    # 大きい方に小さい方をくっつける
    if size(x) < size(y):
        x, y = y, x

    # xのサイズを更新
    par[x] += par[y]
    # yの親をxにする
    par[y] = x


# 同じ集合に属するか判定
def same(x, y):
    return find(x) == find(y)


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

for ab in AB:
    a, b = ab
    a, b = a - 1, b - 1
    if same(a, b):
        continue
    else:
        unite(a, b)

n = find(0)
# print(n)
ret = sum(C) - max(C)
print(ret)
m = C.index(max(C))
if n != m:
    C[n], C[m] = C[m], C[n]
C = list(map(str, C))
print(' '.join(C))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import heapq
INF = float("inf")


def argmax(a):
    m, n = -(1 << 31), -1
    for i, v in enumerate(a):
        if m < v:
            m, n = v, i
    return n


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])  # 無向グラフを仮定。逆向きにも辺を張る

        pass


def shortestPath(g: Graph, s: int):
    """ グラフgにおいて、始点sから各頂点への最短路を求める
    引数
    g: グラフ, s: 始点
    返り値
    dist: 始点からの距離が格納されたリスト
    prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    """
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    g = Graph(N)
    for _f, _t in zip(a, b):
        g.add_edge([_f-1, _t-1])
    dist, prev = shortestPath(g, 0)
    s = argmax(dist)
    dist, prev = shortestPath(g, s)
    g = argmax(dist)

    c.sort()

    # print(dist, prev)
    ans = -1
    haichi = [0]*N
    while True:
        haichi[g] = c.pop()
        if ans == -1:
            ans = 0
        else:
            ans += haichi[g]
        if prev[g] == None:
            break
        else:
            g = prev[g]
    for i in range(N):
        if haichi[i] == 0:
            haichi[i] = c.pop()
            ans += haichi[i]
            if len(c) == 0:
                break
    print(ans)
    print(*haichi)
    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:
from collections import defaultdict

n = int(input())

nodes = defaultdict(list)
edges = []
edge_count = defaultdict(int)
node = defaultdict(int)

for _ in range(n - 1):
    a, b = map(int, input().split())
    nodes[a].append(b)
    nodes[b].append(a)
    edges.append((a, b))
    edge_count[a] += 1
    edge_count[b] += 1

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

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

for i, e in enumerate(edge_count_list):
    node[e[0]] = c[i]

ans = 0
for edge in edges:
    ans += min(node[edge[0]], node[edge[1]])

print(ans)

position = []

for i in range(n):
    position.append(node[i + 1])

print(*position, sep=" ")

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = []
for i in range(N-1):
    ab.append(list(map(int,input().split())))
c = sorted(list(map(int,input().split())),reverse=True)

d = {}
dd = {}
for i in range(1,N+1):
    d[i]=0
    dd[i] = 0
for i in range(N-1):
    d[ab[i][0]] += 1
for i in range(N-1):
    d[ab[i][1]] += 1

l = []
for i in range(1,N+1):
    l.append([i,d[i]])

l = sorted(l,key=lambda x : x[1],reverse=True)

ansd={}
for i in range(len(l)):
    dd[l[i][0]] = c[i]

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

ansl = []
for i in range(1,N+1):
    ansl.append(dd[i])
print(" ".join(map(str,ansl)))

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)[::-1]
# max_di = sort_i[-1]
# print(sort_i)
C = list(map(int, input().split()))
C = sorted(C, reverse=True)
# C = list(sorted(zip(sorted(C), list(sort_i)),key=lambda x: x[1]))
# print(C[sort_i])
ans = 0
visited_e = []
# start = max_di + 1
visited = [False for i in range(N)]
p = 0
ans = [0 for i in range(N)]
M = 0
for i in sort_i:
    if visited[i]:
        pass
    else:
        visited[i] = True
        ans[i] = C[p]
        p += 1
    for node in tree[i+1]:
        # set_e = set(node, start)
        if visited[node-1]:
            continue
        visited[node-1] = True
        # M += min(ans[i], C[p])
        ans[node-1] = C[p]
        p += 1
for e in edges:
    M += min(ans[e[0]-1], ans[e[1]-1])
    # print(ans)
print(M)
print(' '.join(list(map(lambda x: str(x), ans))))

Submission status: Wrong Answer

Solution code:
import copy
N = int(input())
node =  [0]*N
ans = [0]*N
for i in range(N-1):
    a, b = map(int,input().split())
    node[a-1] += 1
    node[b-1] += 1

c = list(map(int, input().split()))
d = copy.deepcopy(c)

for j in range(N):
    ans[node.index(min(node))] = min(c)
    node[node.index(min(node))] = N
    c.remove(min(c))
print(sum(d)-max(d))
for k in range(N):
    print(ans[k], end=' ')
print()

Submission status: Wrong Answer

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

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

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


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

Submission status: Wrong Answer

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

n = int(input())
ch = [[0,i] for i in range(n)]
graph = [[] for i in range(n)]

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

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

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

ans = [0 for i in range(n)]
def solve(i,count):
    use[i] = 1
    ans[i] = c[count]
    count += 1
    for j in graph[i]:
        if use[j] == 0:
            solve(j,count)
            count += 1

    return count

count = solve(ch[0][1],0)

print(sum(c)-c[0])
for i in ans:
    print(i,end=' ')

print()

Submission status: Wrong Answer

Solution code:
n = int(input())
for i in range(n-1):
    a,b = map(int,input().split())
c = list(map(int,input().split()))
ans = sum(sorted(c,reverse=True)[1:])
ans2 = sorted(c,reverse=True)
print(ans)
for i in ans2:
    print(i,end=' ')

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = []
for i in range(N-1):
    ab.append(list(map(int,input().split())))
c = sorted(list(map(int,input().split())),reverse=True)

d = {}
dd = {}
for i in range(1,N+1):
    d[i]=0
    dd[i] = 0
for i in range(N-1):
    d[ab[i][0]] += 1
for i in range(N-1):
    d[ab[i][1]] += 1

l = []
for i in range(1,N+1):
    l.append([i,d[i]])

l = sorted(l,key=lambda x : x[1],reverse=True)

ansd={}
for i in range(len(l)):
    dd[l[i][0]] = c[i]

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

ansl = []
for i in range(1,N+1):
    ansl.append(dd[i])
print(" ".join(map(str,ansl)))

Submission status: Wrong Answer

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

M = sum(C[:-1])

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

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

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

Submission status: Wrong Answer

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

n = int(input())

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

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

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

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

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

score = 0

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = []
for i in range(n-1):
    a, b = map(int, input().split())
    shou = min(a, b)
    dai = max(a, b)
    temp = [shou, dai]
    lst.append(temp)

lst.sort(key=lambda x:(x[0]))

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

ans_lst = [0] * n
ans = sum(d[1:])

ans_lst[0] = d[0]
for i in range(n-1):
    ans_lst[lst[i][1]-1] = d[i+1]

ans_lst = map(str, ans_lst)
mojiretu = ' '.join(ans_lst)
print(ans)
print(mojiretu)

Submission status: Wrong Answer

Solution code:
N = int(input())
tree = {i:[] for i in range(N)}
t_n = [None for i in range(N)]
t = [[0, i] for i in range(N)]

for i in range(N-1):
    a, b = list(map(int, input().split()))
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    t[a-1][0] += 1
    t[b-1][0] += 1

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

for _, idx in t:
    t_n[idx] = c.pop(-1)
ans = 0
for key, value in tree.items():
    for idx in value:
        ans += min(t_n[key], t_n[idx])

print(ans//2)
[print(n, ' ', end='') for n in t_n]

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())

tree = []
trees = np.zeros(N)

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

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

print(sum(c[:N-1]))
str_c = ''
for i in range(len(c)):
    str_c+=str(c[i])+' '

print(str_c[:-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
for i in range(n-1):
    a,b = map(int,input().split())
c = list(map(int,input().split()))
ans = sum(sorted(c,reverse=True)[1:])
ans2 = sorted(c)
print(ans)
for i in ans2:
    print(i,end=' ')

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
a, b = [], []
ab = []
for i in range(n-1):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
    ab.append(ai)
    ab.append(bi)
c = sorted(list(map(int, input().split())))
cnt = collections.Counter(ab)
cnt = sorted(cnt.items(), key=lambda x: x[1])

cc = [0] * n
for i in range(n):
    k, v = cnt[i]
    cc[k-1] = c[i]
ans = 0
for i in range(n-1):
    ans += min(cc[a[i]-1], cc[b[i]-1])
print(ans)
print(*cc)

Submission status: Wrong Answer

Solution code:
n = int(input())
tree = []
leaf = []
node = [0] * (n-1)

for i in range(n-1):
    tmp = input().split(" ")
    tree.append([int(tmp[0]), int(tmp[1])])

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

for i in range(n-1):
    if leaf[tree[i][0] - 1] > leaf[tree[i][1] - 1] :
        node[i] = leaf[tree[i][1] - 1]
    else:
        node[i] = leaf[tree[i][0] - 1] 
    
r = 0
for i in node:
    r += i

res = str(r) + "\n"
for i in node:
    res += str(i) + " "

print(res)

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

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

res = [-1] * (n + 1)
for i in range(n):
    res[lines[i][0]] = dat_c[i]

lines.remove((0, 0))
#print(lines)
cost = 0
for i in range(len(line_dat)):
    #print("line_dat:")
    #print(line_dat[i])
    #print("cost:" + str(min( res[line_dat[i][0]], res[line_dat[i][1]])))
    cost += min( res[line_dat[i][0]], res[line_dat[i][1]])

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

Submission status: Wrong Answer

Solution code:
import copy
N=int(input())
graph=list([0]*N for _ in range(N))
ab=list(list(map(int,input().split())) for _ in range(N-1))
c=list(map(int,input().split()))
for a,b in ab:
    graph[a - 1][b - 1] = 1
    graph[b - 1][a - 1] = 1
for i in range(N):
    graph[i].append(sum(graph[i]))
    graph[i].append(i)

graph.sort(key=lambda x :x[N],reverse=True)
c.sort(reverse=True)
L=[[] for p in range(N)]
for i in graph:
    L[i[N+1]].append(c[i[N+1]])
ans=-max(c)
for q in L:
    ans+=q[0]
print(ans)
for j in range(N):
    print(L[j][0],end=' ')

Submission status: Wrong Answer

Solution code:
N = int(input())
E = [[]]*N
D = [0] * N
for i in range(N-1):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
c = list(map(int,input().split()))
x = max(c)
print(sum(c)-max(c))
start = 0
for i in range(N-1):
    if (len(E[i]) >= 2):
        start = i
        break
already = [0]*N
already[start] = 1
path = [start]
while(path):
    start = path[0]
    try:
        next = E[start][0]
    except:
        d = min(c)
        D[start] = d
        c.remove(d)
        path.remove(start)
        continue
    if already[next] == 1:
        E[start].remove(next)
        continue
    path.insert(0,next)
    already[next] = 1
    start = next
for d in D:
    print(d,end = " ")

Submission status: Wrong Answer

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

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

print(goukei - num)
print(*c)

Submission status: Wrong Answer

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

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
nodes.sort(key=lambda x: -x[0])
# 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)))

Submission status: Wrong Answer

Solution code:
N=int(input())
edge=[list(map(int,input().split())) for i in range(N-1)]
C=list(map(int, input().split()))
from heapq import heapify,heappop
MAX=max(C)
heapify(C)
c=[[] for i in range(N)]
for i,j in edge:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
d=[-1]*N
d[0]=heappop(C)
v=[0]*N
v[0]=1
SUM=d[0]
import sys
sys.setrecursionlimit(10**5)
def dfs(p,v,d):
    global SUM
    for n in c[p]:
        if v[n]==0:
            d[n]=heappop(C)
            SUM+=d[n]
            v[n]=1
            dfs(n,v,d)
dfs(0,v,d)
print(SUM-MAX)
for i in range(N-1):
    print(d[i],end=' ')
print(d[N-1])

Submission status: Wrong Answer

Solution code:
N = int(input())
nodes_cnt = [[i+1, 0] for i in range(N)]
sides = []
for i in range(N-1):
    side = list(map(int, input().split()))
    nodes_cnt[side[0]-1][1] += 1
    nodes_cnt[side[1]-1][1] += 1
    sides.append(side)
costs = list(map(int, input().split()))

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

total_res = 0
nodes_res = [0 for i in range(N)]

for i in range(N):
    n = nodes_cnt[i][0]
    cost = costs[i]
    nodes_res[n-1] = cost

    prev_len = len(sides)
    sides = [side for side in sides if not n in side]
    curr_len = len(sides)
    total_res += cost * (prev_len - curr_len)

print(total_res)
for node in nodes_res:
    print(node, end=' ')
print()

Submission status: Wrong Answer

Solution code:
N=int(input())
nodes=[0]*(N+1)
edge_list=[]
for i in range(N-1):
    a,b=map(int,input().split())
    nodes[a]+=1
    nodes[b]+=1
    edge_list.append((a,b))
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)
ans=[0]*N
for i in range(len(node_dic_sorted)):
    for posi in node_dic[node_dic_sorted[i][0]]:
        ans[posi]=c.pop(0)
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())
#tree = [[0 for i in range(n)] for i in range(n)]
count = []
tmp = []
#dic = {}
ans = 0
#count = [接続数、cの値、何番目の点]
for i in range(n):
    count.append([0, 0, i])

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

    #tree[a-1][b-1], tree[b-1][a-1] = 1, 1
    count[a-1][0] += 1
    count[b-1][0] += 1

c = list(map(int, input().split()))
c.sort(reverse = True)
count.sort()
count.reverse()
#print(count)
for i in range(n):
    count[i][1] = c[i]

count = sorted(count, key = lambda x: x[2])
"""
for i in range(n):
    dic[i] = count[i][1]
"""
print(sum(c) - max(c))
for i in range(n):
    if i == n - 1:
        print(count[i][1])
    else:
        print("{} ".format(count[i][1]), end = "")

Submission status: Wrong Answer

Solution code:
# Take 2
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()

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

# 接続数の少ない順に値を格納
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:
#

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

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

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

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

    for i in range(len(d)):
        d[i] = (d[i], i)
    d.sort(key=lambda v: v[0], reverse=True)

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

            count += 1
            if count == N:
                break

        # print(edges[i])
        neighbors = []
        for nei in edges[i]:
            neighbors.append((nei, multi[nei]))

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# 2019/06/01
# M-SOLUTIONS プロコンオープン - D

from operator import itemgetter

# Input
n = int(input())
abl = list()

# Init Fushi no Kazu
fcnt = list()
for i in range(n+1):
    wfcnt = 0
    fcnt.append([wfcnt, i])

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

    # Count up Fushi no Kazu
    fcnt[ab[0]][0] += 1
    fcnt[ab[1]][0] += 1

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

fcnt.sort(key=itemgetter(0), reverse=True)

scoresum = 0
for i in range(n):
    fcnt[i].append(c[i])
    scoresum += c[i]

scoresum -= max(c)
fcnt.sort(key=itemgetter(1))

ansstr = ""

for i in range(1, n+1):
    ansstr +=  str(fcnt[i][2]) + " "

# Output
print(scoresum)
print(ansstr)

Submission status: Wrong Answer

Solution code:
import copy
import queue
q = queue.Queue()
n = int(input())

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

def bfs():
    start = 0
    valid = [1]*100001
    q.put((start,0)) 
    valid[start] = 0
    level[start][1] = 0
    while not q.empty():
        p,d = q.get()
        for nei in neib[p]:
            if valid[nei]:
                valid[nei]=0
                level[nei][1] = d+1
                q.put((nei,d+1))
bfs()

level.sort(key = lambda x:x[1])
c = list(map(int,input().split()))
c.sort()
res = 0
for i in range(n):
    level[i].append(c[i])
    res += c[i]
res -= c[-1]
print(res)
level.sort(key = lambda x:x[0])
for i in range(n):
    print(level[i][2],end=" ")
print("")

Submission status: Wrong Answer

Solution code:
N = int(input())
branch = []

# 各頂点の数値
numDict = []

# 各頂点が使われている数
topCount = {}
for i in range(N + 1):
    topCount.setdefault(i, 0)
    numDict.append(0)

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

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

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

count = 0
for item in sortcount:
    if item[0] > 0:
        numDict[item[0]] = leaf[count]
        count += 1

ans = 0

for pair in branch:
    ans += min(leaf[pair[0] - 1],leaf[pair[1] - 1])

print(ans)
for i in range(1,N+1):
    print(numDict[i])

Submission status: Wrong Answer

Solution code:

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

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

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

c.sort()

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

Submission status: Wrong Answer

Solution code:
N = int(input())
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 = []
for i in range(N-1):
    _list.append(min(C[A[i]-1],C[B[i]-1]))

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
from collections import deque

def main():
    N = int(input())
    adjacency_lists = {}
    nodes = {}
    for i in range(1, N + 1):   
        adjacency_lists[i] = []
    for i in range(N - 1):
        a, b = map(int, input().split())
        adjacency_lists[a].append(b)
        adjacency_lists[b].append(a)
    C = [int(c) for c in input().split()]
    C.sort()
    root = None
    for i in range(1, N):
        if len(adjacency_lists[i]) > 1:
            root = adjacency_lists[i]
            break
    c = np.zeros((N + 1, ))
    c[root] = 1
    leaves = []
    for node in range(1, N + 1):
        if len(adjacency_lists[node]) == 1:
            # 一つしか繋がっていないのは葉
            leaves.append(node)
    queue = deque()
    colors = np.zeros((N + 1, ))
    for node in leaves:
        queue.append(node)
        colors[node] = 1
    num = 0
    while(queue):
        now = queue.popleft()
        nodes[now] = C[num]
        num += 1
        for next_node in adjacency_lists[now]:
            if (colors[next_node] != 1):
                queue.append(next_node)
                colors[next_node] = 1
    nodes = sorted(nodes.items())
    print(sum(C[:N - 1]))
    for key_, value_ in nodes:
        print(value_, end=" ")
    print()


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

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

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

c_list.sort()

d_list = [(len(table[i]), i) for i in range(N)]
d_list.sort()
i_list = [d_list[i][1] for i in range(N)]

scores = [None] * N
for i, s in zip(i_list, c_list):
	scores[i] = s

score = 0
stack = [0]
visited = set()
visited.add(0)
while stack:
	cur = stack.pop()
	s1 = scores[cur]
	for n in table[cur]:
		if not n in visited:
			s2 = scores[n]
			if s1 < s2:
				score += s1
			else:
				score += s2
			stack.append(n)
			visited.add(n)

print(score)
print(" ".join([str(s) for s in scores]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, OrderedDict


N = int(input())
As, Bs = list(), list()

node_dict = defaultdict(list)

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

    node_dict[a].append(b)
    node_dict[b].append(a)

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

node_list = sorted(node_dict.items(), key=lambda kv: len(kv[1]))

Ds = [0 for i in range(len(Cs))]
for i, (node, _) in enumerate(node_list):
    Ds[node] = Cs[i]

score = 0
for a, b in zip(As, Bs):
    score += min(Ds[a], Ds[b])

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

Submission status: Wrong Answer

Solution code:
N = int(input())
E = [[]]*N
D = [0] * N
for i in range(N-1):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
c = list(map(int,input().split()))
x = max(c)
print(sum(c)-max(c))
start = 0
for i in range(N-1):
    if (len(E[i]) >= 2):
        start = i
        break
D[start] = x
c.remove(x)
already = [0]*N
already[start] = 1
path = [start]
while(path):
    start = path[0]
    try:
        next = E[start][0]
    except:
        path.remove(start)
        continue
    if already[next] == 1:
        E[start].remove(next)
        continue
    path.insert(0,next)
    already[next] = 1
    x = max(c)
    c.remove(x)
    D[next] = x
    start = next
for d in D:
    print(d,end = " ")