Problem:


Score : 500 points

Problem Statement

You are given a tree with N vertices 1,2,\ldots,N, and positive integers c_1,c_2,\ldots,c_N.
The i-th edge in the tree (1 \leq i \leq N-1) connects Vertex a_i and Vertex b_i.

We will write a positive integer on each vertex in T and calculate our score as follows:

On each edge, write the smaller of the integers written on the two endpoints.

Let our score be the sum of the integers written on all the edges.

Find the maximum possible score when we write each of c_1,c_2,\ldots,c_N on one vertex in T, and show one way to achieve it. If an integer occurs multiple times in c_1,c_2,\ldots,c_N, we must use it that number of times.

Constraints

1 \leq N \leq 10000

1 \leq a_i,b_i \leq N

1 \leq c_i \leq 10^5

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
:
a_{N-1} b_{N-1}
c_1 \ldots c_N

Output

Use the following format:

M
d_1 \ldots d_N

where M is the maximum possible score, and d_i is the integer to write on Vertex i.
d_1,d_2,\ldots,d_N must be a permutation of c_1,c_2,\ldots,c_N.
If there are multiple ways to achieve the maximum score, any of them will be accepted.

Sample Input 1

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

Sample Output 1

10
1 2 3 4 5

If we write 1,2,3,4,5 on Vertex 1,2,3,4,5, respectively, the integers written on the four edges will be 1,2,3,4, for the score of 10. This is the maximum possible score.

Sample Input 2

5
1 2
1 3
1 4
1 5
3141 59 26 53 59

Sample Output 2

197
59 26 3141 59 53

c_1,c_2,\ldots,c_N may not be pairwise distinct.



Sample input:
5
1 2
2 3
3 4
4 5
1 2 3 4 5


Sample output:
10
1 2 3 4 5

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  edges=[[] for _ in range(n)]
  for _ in range(n-1):
    a,b=LI()
    a-=1
    b-=1
    edges[a].append(b)
    edges[b].append(a)
  c=LI()

  c.sort(reverse=True)

  ans=[0]*n
  q=collections.deque()
  q.append(0)
  i=0
  ans[i]=c[i]
  while q:
    p=q.popleft()
    for nv in edges[p]:
      if ans[nv]!=0:
        continue
      q.append(nv)
      i+=1
      ans[i]=c[i]

  print(sum(ans[1:]))
  print(' '.join([str(x) for x in ans]))

main()
# print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  edges=[[] for _ in range(n)]
  for _ in range(n-1):
    a,b=LI()
    a-=1
    b-=1
    edges[a].append(b)
    edges[b].append(a)
  c=LI()

  c.sort(reverse=True)

  ans=[0]*n
  q=collections.deque()
  q.append(0)
  sm=0
  i=0
  ans[i]=c[i]
  while q:
    p=q.popleft()
    for nv in edges[p]:
      if ans[nv]!=0 and i!=0:
        continue
      q.append(nv)
      i+=1
      sm+=c[i]
      ans[i]=c[i]

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

main()
# print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  edges=[[] for _ in range(n)]
  for _ in range(n-1):
    a,b=LI()
    a-=1
    b-=1
    edges[a].append(b)
    edges[b].append(a)
  c=LI()

  c.sort(reverse=True)

  ans=[0]*n
  q=collections.deque()
  q.append(0)
  sm=0
  i=0
  ans[i]=c[i]
  while q:
    p=q.popleft()
    if ans[p]!=0 and i!=0:
      continue
    for nv in edges[p]:
      if ans[nv]!=0:
        continue
      q.append(nv)
      i+=1
      sm+=c[i]
      ans[i]=c[i]

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

main()
# print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  edges=[[] for _ in range(n)]
  for _ in range(n-1):
    a,b=LI()
    a-=1
    b-=1
    edges[a].append(b)
    edges[b].append(a)
  c=LI()

  c.sort(reverse=True)

  ans=[0]*n
  q=collections.deque()
  q.append(0)
  sm=0
  i=0
  ans[i]=c[i]
  while q:
    p=q.popleft()
    for nv in edges[p]:
      if ans[nv]!=0:
        continue
      q.append(nv)
      i+=1
      sm+=c[i]
      ans[i]=c[i]

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

main()
# print(main())

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

Cs = list(mapint())
Cs.sort(reverse=True)
from collections import deque
Q = deque([0])

checked = [0]*N
checked[0] = 1
cur = 1
ans = 0
while Q:
    v = Q.pop()
    for nx in graph[v]:
        if checked[nx]:
            continue
        checked[nx] = Cs[cur]
        ans += Cs[cur]
        cur += 1
        Q.append(nx)
print(ans)
print(*checked)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N = I()
Graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b = MI()
    Graph[a].append(b)
    Graph[b].append(a)
C = LI()
C.sort(reverse=True)
print(sum(C[1:]))

ANS = [-1]*(N+1)


def dfs(x,i):
    ANS[x] = C[i]
    for y in Graph[x]:
        if ANS[y] == -1:
            i += 1
            dfs(y,i)


dfs(1,0)
print(*ANS[1:])

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    ai, bi = map(lambda x: int(x) - 1, input().split())
    G[ai].append(bi)
    G[bi].append(ai)


# 大きい数字から順番に割り当てる
C = list(map(lambda x: -int(x), input().split()))
heapify(C)
score = -sum(C) + min(C)

# どこかの葉にmaxを置いて，そこから順番に置く
# => maxの値は葉のスコア計算で消えてOK
# leaf = -1
# for n in range(N):
#     if len(G[n]) == 1:
#         leaf = n
#         break

# 深さ優先で全探索
queue = [0]
ans = [-1] * N
while queue:
    node = queue.pop()
    for neighbor in G[node]:
        if ans[neighbor] == -1:
            ans[neighbor] = -heappop(C)
            queue.append(neighbor)

print(score)
print(*ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    ab = [0] * (N-1)
    cnt = [[0, n] for n in range(N)]
    num = [0] * N
    for n in range(N-1):
        a, b = [int(x)-1 for x in input().strip().split()]
        cnt[a][0] += 1
        cnt[b][0] += 1
        ab[n] = (a, b)
    cnt.sort(key=lambda x: x[0])
    C = sorted([int(x) for x in input().strip().split()])
    for n in range(N):
        num[cnt[n][1]] = C[n]
    ans = 0
    for n in range(N-1):
        ans += min(num[ab[n][0]], num[ab[n][1]])
    print(ans)
    print(*num)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ans = [0 for _ in range(n)]
    tree = [[[], i] for i in range(n)]
    graph = [[] for _ in range(n - 1)]
    for i in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        tree[a][0].append(b)
        tree[b][0].append(a)
        graph[i] = [a, b]
    c = list(map(int, input().split()))
    c.sort(reverse=True)
    tree.sort(key=lambda x: len(x[0]), reverse=True)
    for i in range(n):
        ans[tree[i][1]] = c[i]
    ans_sum = 0
    for a, b in graph:
        ans_sum += min(ans[a], ans[b])
    print(ans_sum)
    print(" ".join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ans = [0 for _ in range(n)]
    tree = [[-1, i] for i in range(n)]
    graph = [[] for _ in range(n - 1)]
    for i in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        tree[a][0] = b
        tree[b][0] = a
        graph[i] = [a, b]
    c = list(map(int, input().split()))
    c.sort(reverse=True)
    tree.sort(key=lambda x: x[0], reverse=True)
    for i in range(n):
        ans[tree[i][1]] = c[i]
    ans_sum = 0
    for a, b in graph:
        ans_sum += min(ans[a], ans[b])
    print(ans_sum)
    print(" ".join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
e=[[i] for i in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
c=sorted(list(map(int,input().split())))
q=[1]
vis=[0]*(n+1)
ans=0
while q:
  now=q.pop()
  vis[now]=c.pop()
  for to in e[now]:
    if vis[to]:continue
    q+=[to]
print(sum(c[:n-1]))
print(*vis[1:])

Submission status: Wrong Answer

Solution code:
n=int(input())
e=[[i] for i in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  e[a]+=[b]
  e[b]+=[a]
c=sorted(list(map(int,input().split())))[::-1]
d=sorted(e,key=len)
p=[0]*(n+1)
for i in d[1:]:
  p[i[0]]=c.pop()
q=[1]
vis=[0]*(n+1)
ans=0
while q:
  now=q.pop()
  vis[now]=1
  for to in e[now]:
    if vis[to]:continue
    q+=[to]
    ans+=min(p[now],p[to])
print(ans)
print(*p[1:])

Submission status: Wrong Answer

Solution code:
n = int(input())
graph = [[] for _ in range(n)]
cnt = [0] * (n)
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    cnt[a] += 1
    cnt[b] += 1
sort_idx = []
for i, e in enumerate(cnt):
    sort_idx.append((e, i))
sort_idx.sort(reverse=True)

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

ans = [-1] * n
for i in range(n):
    idx = sort_idx[i][1]
    val = C[i]
    ans[idx] = val


num = 0
start = 0
par = [-1] * n
stack = [start]
while stack:
    v = stack.pop()
    num1 = ans[v]
    for u in graph[v]:
        if u == par[v]:
            continue
        par[u] = v
        num2 = ans[u]
        num += min(num1, num2)
        stack.append(u)
    # print(stack)

print(num)
print(*ans, sep=" ")

Submission status: Wrong Answer

Solution code:
n = int(input())
V = [[] for i in range(n+1)]

a = [0]*(n-1)
for i in range(n-1):
    A,B = map(int,input().split())
    V[A].append(B)
    V[B].append(A)
    
    a[i] = [A, B]
    
c = list(map(int,input().split()))
c = sorted(c, reverse=True)

L = [0]*n
for i in range(1,n+1):
    L[i-1] = [i, len(V[i])]
    
L.sort(key= lambda val : val[1], reverse=True)

d = [-1] + [0]*n

for i in range(n):
    x = L[i][0]
    d[x] = str(c[i])
    
ans = 0
for A,B in a:
    ans += min(int(d[A]), int(d[B]))

print(ans)
print(" ".join(d[1:]))

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/m-solutions2019/tasks/m_solutions2019_d

N=int(input())
a=[0]*N
b=[0]*N
d=[[] for _ in range(N)]
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].append(b[i]-1)
    d[b[i]-1].append(a[i]-1)
#print(d)
c=list(map(int,input().split()))
c.sort()
e=[[len(d[i]),i] for i in range(N)]
e.sort()
#print(e)

ans_list=[0]*N
for i in range(N):
    p = e[i][1]
    ans_list[p] = c[i]

score=0
for i in range(N-1):
    q = ans_list[a[i]-1]
    r = ans_list[b[i]-1]
    #print(a[i]-1, b[i]-1)
    score += min(q,r)
print(score)
print(*ans_list)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/m-solutions2019/tasks/m_solutions2019_d

N=int(input())
a=[0]*N
b=[0]*N
d=[[] for _ in range(N)]
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].append(b[i]-1)
    d[b[i]-1].append(a[i]-1)
#print(d)
c=list(map(int,input().split()))
c.sort()
e=[[len(d[i]),i] for i in range(N)]
e.sort()
#print(e)

ans_list=[0]*N
for i in range(N):
    p = e[i][1]
    ans_list[p] = c[i]

score=0
for i in range(N-1):
    q = ans_list[a[i]-1]
    r = ans_list[b[i]-1]
    #print(a[i]-1, b[i]-1)
    score += min(q,r)
print(score)
print(ans_list)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    C = list(map(int, input().split()))
    C.sort(reverse=True)

    M = sum(C[1:])
    d = [0] * N
    i = 0
    queue = deque([(i, -1)])
    while queue:
        u, p = queue.popleft()
        d[i] = C[i]
        i += 1
        for v in G[u]:
            if v == p: continue
            queue.append((v, u))

    print(M)
    print(" ".join(map(str, d)))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

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

sort_len = {}

for key,value in enumerate(root):
    sort_len[key] = len(value)

sort_len = sorted(sort_len.items(), key=lambda x: x[1])
#print(sort_len)

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

cost = [0]*N
for i in range(N):
    cost[sort_len[i][0]] = c[i]

stack=deque([0])
check = [True]*N
check[0] = False
ans = 0

while len(stack)>0:
    v = stack.popleft()
    for i in root[v]:
        if check[i]:
            ans += min(cost[i], cost[v])
            check[i]=False
            stack.append(i)

print(ans)
print(*cost)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(1000000)

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



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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
N = int(input())
edge = [[] for _ in range(N)]
cnt = [[0,i] for i in range(N)]

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

cnt.sort()
C = list(map(int, input().split()))
C.sort()
nodes = [0] * N
for idx, (c, i) in enumerate(cnt):
    nodes[i] = C[idx]

#print(nodes)

ans = []

def dfs(v, pv, w):
    ans.append(min(w, nodes[v]))
    for nv in edge[v]:
        if pv == nv: continue
        dfs(nv, v, nodes[v])

dfs(0, 0, 0)
print(sum(ans))
print(*nodes, sep=" ")

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=[]
  for i in range(n):
    l.append([i,0,-1])

  edges=[]
  for _ in range(n-1):
    a,b=LI()
    a-=1
    b-=1
    edges.append((a,b))
    l[a][1]+=1

  l=sorted(l,key=lambda x:x[1],reverse=True)
  a=LI()
  a.sort(reverse=True)
  for i,x in enumerate(a):
    l[i][2]=x

  l=sorted(l,key=lambda x:x[0])
  sm=0
  for a,b in edges:
    sm+=min(l[a][2],l[b][2])
  print(sm)
  print(' '.join(str(x) for _,__,x in l))

main()
# print(main())

Submission status: Wrong Answer

Solution code:
from collections import deque


def nearlist(N, LIST):  # 隣接リスト
    NEAR = [set() for _ in range(N)]
    for a, b in LIST:
        NEAR[a - 1].add(b - 1)
        NEAR[b - 1].add(a - 1)
    return NEAR


def bfs(NEAR, S):  # 幅優先探索  # キュー
    ans[S] = c.pop()
    que, frag = deque([S]), set([S])

    while len(que) > 0:
        q = que.popleft()
        for i in NEAR[q]:  # 移動先の候補
            if i in frag:  # 処理済みか否か
                continue
            ans[i] = c.pop()
            que.append(i), frag.add(i)
    return ans


n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
c = sorted(map(int, input().split()))

ans = [0] * n
near = nearlist(n, ab)
print(*bfs(near, 0))

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    node = [[0, i] for i in range(n)]
    e = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = ns()
        a, b = a - 1, b - 1
        node[a][0] += 1
        node[b][0] += 1
        e[a].append(b)
    node.sort()
    c = na()
    c.sort()

    for tnode, ci in zip(node, c):
        tnode[0] = ci
    node.sort(key=lambda x: x[1])

    ans = 0
    for i, ei in enumerate(e):
        for te in ei:
            ans += min(node[i][0], node[te][0])

    print(ans)
    output = [cost for cost, i in node]
    print(*output, sep=" ")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

n=int(input())

g=[[] for _ in range(n+1)]

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

c=sorted(list(map(int,input().split())))
print(sum(c[:-1]))

q=deque([1])
visit=[0]*(n+1)
ans=['']*(n+1)

while len(q)>0:
    u=q.popleft()

    visit[u]=1

    ans[u]=str(c.pop())

    for v in g[u]:
        if visit[v]:
            continue

        q.append(v)

print(' '.join(ans[1:]))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    edges[a].append(b)
    edges[b].append(a)


cost = sorted(map(int, input().split()))

priority = [(len(edge), v) for v, edge in enumerate(edges)]
priority.sort()
ans = [None]*n
while priority:
    d, v = priority.pop()
    c = cost.pop()
    ans[v] = c

m = 0


def dfs(v, parent):
    if parent != -1:
        global m
        m += min(ans[v], ans[parent])

    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v)


dfs(0, -1)
print(m)
print(*ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# 双方向グラフで幅優先探索

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)
mx = 0
st = -1
for i, g in enumerate(graph):
    if len(g)>mx:
        st = i
        mx = len(g)
#    print(graph)
c = list(map(int,input().split()))
c.sort(reverse = True)

#幅優先探索
q = deque()
seen = [False]*N
q.append(st)
seen[0] = c[0]
idx = 1
while len(q)>0:
    cur = q.popleft()
    for i in graph[cur]:
        if seen[i]==False:
            seen[i] = c[idx]
            idx += 1
            q.append(i)
print(sum(c[1:]))
print(' '.join(map(str,seen)))

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

n = int(input())
graph = [[] for _ in range(n)]
cnt = {}
#隣接リストの作成
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    cnt[a]=cnt.get(a,0)+1
    cnt[b]=cnt.get(b,0)+1

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

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

pair = {}
for i in range(n):
    k = c[i]
    i, v = cnt[i]
    pair[i] = k

ret = 0
for i, _ in enumerate(graph):
    x = pair[i]
    for y in _:
        ret += min(x, pair[y])
ret //=2
print(ret)
ret = [pair[i] for i in range(n)]
print(' '.join(map(str,ret)))

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

n = int(input())
graph = [[] for _ in range(n)]
cnt = {}
#隣接リストの作成
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    cnt[a]=cnt.get(a,0)+1
    cnt[b]=cnt.get(b,0)+1

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

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

pair = {}
for i in range(n):
    k = c[i]
    i, v = cnt[i]
    pair[i] = k

ret = 0
for i, _ in enumerate(graph):
    x = pair[i]
    for y in _:
        ret += min(x, pair[y])
ret //=2
print(ret)
ret = [pair[i] for i in range(n)]
print(' '.join(map(str,ret)))

Submission status: Wrong Answer

Solution code:
class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    # k: index , x: value
    def update(self, k: int, x):
        k += self.N0 - 1
        ############################
        self.data[k] = x
        ###########################
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    # rightは開区間  l<=x<r
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ##########################
        a, b = [], []
        while L < R:
            if L & 1:
                a.append(L - 1)
                L += 1
            if R & 1:
                R -= 1
                b.append(R - 1)
            L >>= 1
            R >>= 1
        for i in a + b[::-1]:
            res = self.segfunc(res, self.data[i])
        ##########################
        return res

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()))
C=sorted(C,reverse=True)


edges=[0]*N
for i in range(N):
    edges[i]=[len(G[i]),i]
#print(G)

seg=SegmentTree(edges, max, [0,-1])
ans=[-1]*N

count=0
score=0

while count<N:
    
    #print(A)
    now=seg.query(0,N)
    #print(now)
    nowlen, nowi=now
    #print(nowlen, nowi)
    if nowlen<1:
        break
    ans[nowi]=C[count]
    score+=(len(G[nowi])-nowlen)*C[count]
    count+=1
    seg.update(nowi, [-1,nowi])
    for i in G[nowi]:
        seg.update(i,[-1,i])
        if ans[i]==-1:
            #print(ans, count)
            ans[i]=C[count]
            score+=C[count]
            count+=1
            for j in G[i]:
                new=edges[j][0]-1
                edges[j][0]=-1
                seg.update(j,[new,j])
            

print(score)
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
d = [0]*n
uvs = [None]*(n-1)
for i in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    d[u] += 1
    d[v] += 1
    uvs[i] = (u,v)
c = list(map(int, input().split()))
c.sort()
dd = [(item,i) for i,item in enumerate(d)]
dd.sort()
ans = [None]*n
val = 0
for i in range(n):
    ans[dd[i][1]] = c[i]
for u,v in uvs:
    val += min(ans[u], ans[v])
print(val)
write(" ".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush, heapify
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()))
C=sorted(C,reverse=True)


edges=[]
for i in range(N):
    edges.append([-len(G[i]), i])
#print(G)

done=[0]*N
ans=[-1]*N

count=0
score=0
while count<N:
    A=edges.copy()
    
    heapify(A)
    #print(A)
    now=heappop(A)
    nowlen, nowi=now
    #print(nowlen, nowi)
    if nowlen>-1:
        break
    ans[nowi]=C[count]
    score+=(len(G[nowi])+nowlen)*C[count]
    count+=1
    edges[nowi][0]+=10**5
    for i in G[nowi]:
        edges[i][0]+=10**5
        if ans[i]==-1:
            ans[i]=C[count]
            score+=C[count]
            count+=1
            for j in G[i]:
                edges[j][0]+=1
            

print(score)
print(*ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush, heapify
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()))
C=sorted(C,reverse=True)


edges=[]
for i in range(N):
    edges.append([-len(G[i]), i])
#print(G)

done=[0]*N
ans=[-1]*N

count=0
score=0
while count<N:
    A=edges.copy()
    
    heapify(A)
    #print(A)
    now=heappop(A)
    nowlen, nowi=now
    #print(nowlen, nowi)
    if nowlen>-1:
        break
    ans[nowi]=C[count]
    score+=(len(G[nowi])+nowlen)*C[count]
    count+=1
    edges[nowi][0]+=10**5
    for i in G[nowi]:
        edges[i][0]+=10**5
        if ans[i]==-1:
            ans[i]=C[count]
            score+=C[count]
            count+=1
        for j in G[i]:
            edges[j][0]+=1
            

print(score)
print(*ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush, heapify
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()))
C=sorted(C,reverse=True)


edges=[]
for i in range(N):
    edges.append([-len(G[i]), i])
#print(G)

done=[0]*N
ans=[-1]*N

count=0
score=0
while True:
    A=edges.copy()
    
    heapify(A)
    #print(A)
    now=heappop(A)
    nowlen, nowi=now
    #print(nowlen, nowi)
    if nowlen>-1:
        break
    ans[nowi]=C[count]
    score+=(len(G[nowi])+nowlen)*C[count]
    count+=1
    edges[nowi][0]+=10**5
    for i in G[nowi]:
        edges[i][0]+=10**5
        if ans[i]==-1:
            ans[i]=C[count]
            score+=C[count]
            count+=1
        for j in G[i]:
            edges[j][0]+=1
            

print(score)
print(*ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush, heapify
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()))
C=sorted(C,reverse=True)


edges=[]
for i in range(N):
    edges.append([-len(G[i]), i])
print(G)

done=[0]*N
ans=[-1]*N

count=0
score=0
while True:
    A=edges.copy()
    
    heapify(A)
    #print(A)
    now=heappop(A)
    nowlen, nowi=now
    #print(nowlen, nowi)
    if nowlen>-1:
        break
    ans[nowi]=C[count]
    score+=(len(G[nowi])+nowlen)*C[count]
    count+=1
    edges[nowi][0]+=10**5
    for i in G[nowi]:
        edges[i][0]+=10**5
        if ans[i]==-1:
            ans[i]=C[count]
            score+=C[count]
            count+=1
        for j in G[i]:
            edges[j][0]+=1
            

print(score)
print(*ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7
res = 0


def resolve():
    def dfs(v, p):
        global res
        for u in edge[v]:
            if u == p:
                continue
            else:
                res += min(T[v], T[u])
                dfs(u, v)

    n = int(input())
    edge = [[] for _ in range(n)]
    cnt_edge = [0] * n
    for _ in range(n - 1):
        a, b = map(int, input().split())
        edge[a - 1].append(b - 1)
        edge[b - 1].append(a - 1)
        cnt_edge[a - 1] += 1
        cnt_edge[b - 1] += 1
    C = list(map(int, input().split()))
    C.sort()

    cnt = []
    for i in range(n):
        cnt.append([cnt_edge[i], i])
    cnt.sort(key=lambda x: [x[0], x[1]])

    T = [0] * n
    for i in range(n):
        _, idx = cnt[i]
        T[idx] = C[i]

    dfs(0, -1)
    print(res)
    print(*T)


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N = NI()
    edges = [[i]+NLI() for i in range(N-1)]
    C = NLI()
    tree = [[] for _ in range(N+1)]
    for edge in edges:
        tree[edge[1]].append(edge[2])
        tree[edge[2]].append(edge[1])
    option_nums = []
    for i, node in enumerate(tree):
        option = len(node)
        option_nums.append([option, i])
    option_nums = sorted(option_nums)
    C = sorted(C)
    ans = {}
    for op, c in zip(option_nums[1:], C):
        ans[op[1]] = c
    A = 0
    for edge in edges:
        x, y = edge[1], edge[2]
        A += min(ans[x], ans[y])
    print(A)
    for i in range(1, N+1):
        if i == N:
            print(str(ans[i]))
            continue
        print(str(ans[i]), end=" ")

if __name__ == "__main__":
    main()