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:
*D, = open(0)
n = int(D[0])

edge = [[] for _ in range(n+1)]
v_val = [0 for _ in range(n+1)]

dist = {}

for i in range(1, n):
    a, b = map(int, D[i].split())
    edge[a].append(b)
    edge[b].append(a)
c = list(map(int, D[n].split()))
c = sorted(c, reverse=True)

from collections import deque
visited = [False for _ in range(len(edge))]
start = 1
que = deque()
que.append(start)
order = []
order.append(start)
visited[start] = True

while que:
    node = que.popleft()
    for it in edge[node]:
        if not visited[it]:
            order.append(it)
            visited[it] = True
            que.append(it)
# calculate cost
v_val = [0 for _ in range(len(c)+1)]
for i in order:
    v_val[i] = c[i-1]

print(sum(c[1:]))
print(' '.join(map(str, v_val[1:])))

Submission status: Wrong Answer

Solution code:
*D, = open(0)
n = int(D[0])

edge = [[] for _ in range(n+1)]
v_val = [0 for _ in range(n+1)]

dist = {}

for i in range(1, n):
    a, b = map(int, D[i].split())
    edge[a].append(b)
    edge[b].append(a)
c = list(map(int, D[n].split()))
c = sorted(c, reverse=True)


from collections import deque
visited = [False for _ in range(len(edge))]
start = 1
que = deque()
que.append(start)
order = []

while que:
    node = que.popleft()
#     print(node)
    order.append(node)
    visited[node] = True
    for it in edge[node]:
        if not visited[it]:
            que.append(it)
# calculate cost
v_val = [0 for _ in range(len(c)+1)]
for i in order:
    v_val[i] = c[i-1]

print(sum(c[1:]))
print(' '.join(map(str, v_val[1:])))

Submission status: Wrong Answer

Solution code:
*D, = open(0)
n = int(D[0])

edge = [[] for _ in range(n+1)]
v_val = [0 for _ in range(n+1)]

dist = {}

for i in range(1, n):
    a, b = map(int, D[i].split())
    edge[a].append(b)
    edge[b].append(a)
c = list(map(int, D[n].split()))
c = sorted(c, reverse=True)


start = None
for i in range(1,len(edge)):
    if len(edge[i])==1:
        start = i
        break

def calcCost(D, v_val):
    total = 0
    
    n = int(D[0])
    for i in range(1, n):
        a, b = map(int, D[i].split())
        total += min(v_val[a], v_val[b])
    return total

import sys
sys.setrecursionlimit(10**7)


def visit(edge, start, visited, order):
    visited[start] = True
    order.append(start)
    
    for node in edge[start]:
        if not visited[node]:
            visit(edge, node, visited, order)
    
    return 

visited = [False for _ in range(len(edge))]
order = []
visit(edge, start, visited, order)

# calculate cost
v_val = [0 for _ in range(len(c)+1)]
for i in order:
    v_val[i] = c[i-1]
    
val = calcCost(D, v_val)

print(val)
print(' '.join(map(str, v_val[1:])))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

import sys
from operator import itemgetter

n= int( sys.stdin.readline().strip() )
e= []
for _ in range(n-1):
    e.append( [ int(x) for x in \
                sys.stdin.readline().strip().split() ] )
#
s= [ int(x) for x in sys.stdin.readline().strip().split() ]
s.sort()
#
# 頂点の次数
o   = { x+1:0 for x in range(n) }
for edge in e:
    ei,ef = edge
    o[ei]+= 1
    o[ef]+= 1
#
# score map
smap= [0] * n
i= 0
for k,_ in sorted( o.items(),key=itemgetter(1) ):
    smap[k-1]= s[i]
    i+= 1
# calculate
tot= 0
for edge in e:
    ei, ef = edge
    tot+= min(smap[ei-1],smap[ef-1])
#
print( tot )
print( ' '.join(map(str,smap)) )

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

import sys
from operator import itemgetter

n= int( sys.stdin.readline().strip() )
e= []
for _ in range(n-1):
    e.append( [ int(x) for x in \
                sys.stdin.readline().strip().split() ] )
#
s= [ int(x) for x in sys.stdin.readline().strip().split() ]
s.sort()
#
# 頂点の次数
o   = { x+1:0 for x in range(n) }
for edge in e:
    ei,ef = edge
    o[ei]+= 1
    o[ef]+= 1
#
# score map
smap= [0] * n
i= 0
for k,_ in sorted( o.items(),key=itemgetter(1) ):
    smap[k-1]= s[i]
    i+= 1
# calculate
tot= 0
for edge in e:
    ei, ef = edge
    tot+= min(smap[ei-1],smap[ef-1])
#
print( tot )
print( ' '.join(map(str,s)) )

Submission status: Wrong Answer

Solution code:
*D, = open(0)
n = int(D[0])

edge = [[] for _ in range(n+1)]
v_val = [0 for _ in range(n+1)]

dist = {}

for i in range(1, n):
    a, b = map(int, D[i].split())
    edge[a].append(b)
    edge[b].append(a)
c = list(map(int, D[n].split()))
c = sorted(c, reverse=True)

# 木の端を求める
def findLeaf(edge, start=1):
    visited = [False for _ in range(len(edge))]
    next_v = edge[start]
    visited[start] = True
    count = 0
    
    while len(next_v) > 0:
        new_v = []
        for it in next_v:
    #         print(it)
            leaf = it
            for v in edge[it]:
                if not visited[v]:
                    new_v.append(v)
            visited[it] = True
        next_v = new_v
        count += 1

    return leaf, count

def calcCost(D, v_val):
    total = 0
    
    n = int(D[0])
    for i in range(1, n):
        a, b = map(int, D[i].split())
        total += min(v_val[a], v_val[b])
        
    return total

leaf, count = findLeaf(edge)

start = leaf
visited = [False for _ in range(len(edge))]
next_v = edge[start]
visited[start] = True
count = 0
order=[]
order.append(start)
while len(next_v) > 0:
    new_v = []
    for it in next_v:
#         print(it)
        leaf = it
        for v in edge[it]:
            if not visited[v]:
                new_v.append(v)
        visited[it] = True
        order.append(it)
    next_v = new_v
    count += 1

# calculate cost
v_val = [0 for _ in range(len(c)+1)]
for i in order:
    v_val[i] = c[i-1]

val = calcCost(D, v_val)

print(val)
print(' '.join(map(str, v_val[1:])))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
D - 756

"""
import sys


from collections import Counter

def prime_factor(N):
    factors = Counter()
    for i in range(2, int(N**0.5)+1):
        while N % i == 0:
            factors[i] += 1
            N //= i
    if N != 1:
        factors[N] = 1
    return factors


def solve(n):
    d = Counter()
    for i in range(2, n+1):
        x = prime_factor(i)
        d += x
    t3 = [v for k, v in d.items() if v >= 2]
    t5 = [v for k, v in d.items() if v >= 4]
    t15 = [v for k, v in d.items() if v >= 14]
    t25 = [v for k, v in d.items() if v >= 24]
    t75 = [v for k, v in d.items() if v >= 74]
    ans = len(t75) + len(t25)*(len(t3)-1) + len(t15)*(len(t5)-1)+len(t5)*(len(t5)-1)*(len(t3)-2) // 2
    return ans


def main(args):
    n = int(input())
    ans = solve(n)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(20000000)
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))

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

ans = [0] * (n+1)
def dfs(num):
    ans[num] = c.pop()
    for next_num in connection[num]:
        if ans[next_num] != 0 :
            dfs(next_num)

dfs(1)

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

print(score)
print(" ".join(map(str, ans[1:])))

Submission status: Wrong Answer

Solution code:
def input_from_console():
    n = int(input())
    a_list, b_list = [], []
    for i in range(n - 1):
        data = input()
        a, b = map(int, data.split())
        if b > a:
            a, b = b, a  # swap smaller one.
        a_list.append(a)
        b_list.append(b)
    c_list = []
    c_list = list(map(int, input().split()))
    return n, a_list, b_list, c_list


def solve(n, a_list, b_list, c_list):
    edge = [[] for i in range(n)]
    for i in range(len(a_list)):
        a, b = a_list[i] - 1, b_list[i] - 1  # convert to 0 based index.
        edge[a].append(b)
        edge[b].append(a)
    c_list_new = sorted(c_list, reverse=True)

    value = sum(c_list_new[1:])

    vertices = [None] * n
    vertices[0] = c_list_new.pop(0)

    search_path = []
    search_path.extend(edge[0])

    while search_path:
        node = search_path.pop(0)
        if vertices is None:
            vertices[node] = c_list_new.pop(0)
            search_path.extend(edge[node])
    return str(value) + '\n' + ' '.join(map(str, vertices))


def main():
    n, a_list, b_list, c_list = input_from_console()
    print(solve(n, a_list, b_list, c_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = []
for _ in range(N-1):
    ab.append([int(i) for i in input().split()])
ab = sorted(ab)
c = [int(i) for i in input().split()]
c = sorted(c,reverse=True)
ans = 0
for abi in ab:
    a_temp = c[abi[0]-1]
    b_temp = c[abi[1]-1]
    ans += min(a_temp,b_temp)
print(ans)
print(str(c).replace("[","").replace("]","").replace(",",""))

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int( input())
E = [[] for _ in range(N)]
V = [0]*N
for _ in range(N-1):
    a, b = map( int, input().split())
    a, b = a-1, b-1
    E[a].append(b)
    E[b].append(a)
    V[a] += 1
    V[b] += 1
C = list(map( int, input().split()))
C.sort(reverse=True)
for i in range(N):
    if V[i] == 1:
        s = i
        break
q = deque([s])
V = [0]*N
l = 0
for l in range(N):
    t = q.popleft()
    V[t] = C[l]
    for v in E[t]:
        if V[v] == 0:
            q.append(v)
print( sum(C) - C[0])
print( " ".join( map( str, C)))

Submission status: Wrong Answer

Solution code:
# n=int(input())
# a,b=map(int, input().split())
# c=list(map(int, input().split()))
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import numpy as np
import math
import copy

class node_info:
    def __init__(self, id):
        self.id = id
        self.childs = []
        self.parent = -1
        self.assigned_value = -1

def dfs(num_list, num_idx, node_id, node_list, total):
    target_node = node_list[node_id]

    if target_node.assigned_value == -1:
        target_node.assigned_value = num_list[num_idx]
        num_idx += 1

    if len(target_node.childs) == 0:
        pass
    else:
        for ch in target_node.childs:
            num_idx, total = dfs(num_list, num_idx, ch, node_list, total)
    if target_node.parent != -1:
        total += target_node.assigned_value
    return num_idx, total

def get_root(num_list):
    root_idx = 0
    while True:
        if num_list[root_idx] != None:
            if num_list[root_idx].parent == -1:
                return root_idx
            else:
                root_idx = num_list[root_idx].parent

if __name__ == "__main__":
    N = int(input())
    node_list = [None for _ in range(N)]
    for _ in range(N - 1):
        node, ch = map(int, input().split())
        # align index
        node -= 1
        ch -= 1
        if node_list[node] == None:
            node_list[node] = node_info(node)
        node_list[node].childs.append(ch)
        if node_list[ch] == None:
            node_list[ch] = node_info(ch)
        node_list[ch].parent = node

    num_list = list(map(int, input().split()))
    num_list = sorted(num_list, reverse=True)
    root_idx = get_root(node_list)

    _, total = dfs(num_list, 0, root_idx, node_list, 0)

    ans = []
    for node in node_list:
        if node != None:
            ans.append(node.assigned_value)

    print(total)
    print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int( input())
E = [[] for _ in range(N)]
V = [0]*N
for _ in range(N-1):
    a, b = map( int, input().split())
    a, b = a-1, b-1
    E[a].append(b)
    E[b].append(a)
    V[a] += 1
    V[b] += 1
C = list(map( int, input().split()))
C.sort(reverse=True)
s = 0
for i in range(N):
    if V[i] == 1:
        s = i
        break
q = deque([s])
V = [0]*N
l = 0
while q and l < N:
    t = q.popleft()
    if V[t] != 0:
        continue
    V[t] = C[l]
    l += 1
    for v in E[t]:
        if V[v] == 0:
            q.append(v)
print( sum(C) - C[0])
print( " ".join( map( str, C)))

Submission status: Wrong Answer

Solution code:
N = int(input())
A, B, S= [], [], []
T = [0] * N

for i in range(N-1):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)

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

for i in range(N):
  S.append((A.count(i+1)+B.count(i+1), i))
S.sort()
for i in range(N):
  T[S[i][1]] = C[i]

s = sum(C)-C[0]

print(s)
print(*T)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
 
n = int(input())
g = [[]for i 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()))
kyo = [float("inf")] * n
def dfs(x,y,z):
  kyo[x] = y
  for i in g[x]:
    if i == z:
            continue
    dfs(i,y+1,x)
dfs(0,0,-1)
kyo2 = []
for i in range(n):
        kyo2.append([kyo[i],i])
ans = [0]*n
kyo2.sort()
c.sort()
for i in range(n):
        ans[kyo2[i][1]] = c[i]
print(sum(c)-c[-1])
print(*ans)

Submission status: Wrong Answer

Solution code:
import itertools
N = input()
N = int(N)
querys = []
graph = {}
for i in range(N-1):
    l = list(map(int,input().split(" ")))
    querys.append(l)
    a = l[0]
    b = l[1]
    if a not in graph:
        graph[a] = []
    graph[a].append(b)
    if b not in graph:
        graph[b] = []
    graph[b].append(a)

# print(graph)
graph = sorted(graph.items(), key=lambda x:len(x[1]))
nums = list(map(int,input().split(" ")))
nums.sort()
ans_graph = {}

for num,temp in zip(nums,graph):
    ans_graph[temp[0]] = num
ans = 0
for temp in querys:
    a,b = temp
    ans += min(ans_graph[a],ans_graph[b])

print(ans)
ans_graph= sorted(ans_graph.items(), key=lambda x:x[0])
ans = list(map(lambda x:str(x[1]),ans_graph))
print(" ".join(ans))

Submission status: Wrong Answer

Solution code:
class Node:
  def __init__(self,data):
    self.data = data
    self.childs = []
    self.depth = 0
    self.number = 0

N = int(input())
Nodes = []
for i in range(N+1):
  Nodes.append(Node(i))

for i in range(N-1):
  A,B = (int(i) for i in input().split())
  Nodes[A].childs.append(B)

c = [int(i) for i in input().split()]
c.sort(reverse=True)
tmp_ans = sum(c[1:])

for Node in Nodes:
  for child in Node.childs:
    Nodes[child].depth = Node.depth + 1

Nodes.pop(0)
Nodes = sorted(Nodes, key=lambda x: x.depth)

for Node in Nodes:
  Node.number = c[0]
  c.pop(0)

Nodes = sorted(Nodes, key=lambda x: x.data)

ans = 0
ans_list = []

for Node in Nodes:
  ans_list.append(Node.number)
  for child in Node.childs:
    ans += min(Nodes[child-1].number,Node.number)

print(tmp_ans)
print(" ".join(map(str, ans_list)))

Submission status: Wrong Answer

Solution code:
class Node:
  def __init__(self,data):
    self.data = data
    self.childs = []
    self.depth = 0
    self.number = 0

N = int(input())
Nodes = []
for i in range(N+1):
  Nodes.append(Node(i))

for i in range(N-1):
  A,B = (int(i) for i in input().split())
  Nodes[A].childs.append(B)

c = [int(i) for i in input().split()]
c.sort(reverse=True)
tmp_ans = sum(c[1:])

for Node in Nodes:
  for child in Node.childs:
    Nodes[child].depth = Node.depth + 1

Nodes.pop(0)
Nodes = sorted(Nodes, key=lambda x: (x.depth,len(x.childs)))

for Node in Nodes:
  Node.number = c[0]
  c.pop(0)

Nodes = sorted(Nodes, key=lambda x: x.data)

ans = 0
ans_list = []

for Node in Nodes:
  ans_list.append(Node.number)
  for child in Node.childs:
    ans += min(Nodes[child-1].number,Node.number)

print(tmp_ans)
print(" ".join(map(str, ans_list)))

Submission status: Wrong Answer

Solution code:
class Node:
  def __init__(self,data):
    self.data = data
    self.childs = []
    self.depth = 0
    self.number = 0

N = int(input())
Nodes = []
for i in range(N+1):
  Nodes.append(Node(i))

for i in range(N-1):
  A,B = (int(i) for i in input().split())
  Nodes[A].childs.append(B)

c = [int(i) for i in input().split()]
c.sort(reverse=True)
tmp_ans = sum(c[1:])

for Node in Nodes:
  for child in Node.childs:
    Nodes[child].depth = Node.depth + 1

Nodes.pop(0)
Nodes = sorted(Nodes, key=lambda x: (x.depth,len(x.childs)), reverse = True)

c.sort(reverse=True)
for Node in Nodes:
  Node.number = c[0]
  c.pop(0)

Nodes = sorted(Nodes, key=lambda x: x.data)

ans = 0
ans_list = []

for Node in Nodes:
  ans_list.append(Node.number)
  for child in Node.childs:
    ans += min(Nodes[child-1].number,Node.number)

print(tmp_ans)
print(" ".join(map(str, ans_list)))

Submission status: Wrong Answer

Solution code:
class Node:
  def __init__(self,data):
    self.data = data
    self.childs = []
    self.depth = 0
    self.number = 0

N = int(input())
Nodes = []
for i in range(N+1):
  Nodes.append(Node(i))

for i in range(N-1):
  A,B = (int(i) for i in input().split())
  Nodes[A].childs.append(B)

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

for Node in Nodes:
  for child in Node.childs:
    Nodes[child].depth = Node.depth + 1

Nodes.pop(0)
Nodes = sorted(Nodes, key=lambda x: (x.depth,len(x.childs)), reverse = True)

c.sort()
ans = sum(c[:-1])
for Node in Nodes:
  Node.number = c[0]
  c.pop(0)

Nodes = sorted(Nodes, key=lambda x: x.data)

ans_list = []

for Node in Nodes:
  ans_list.append(Node.number)
#  for child in Node.childs:
#    ans += min(Nodes[child-1].number,Node.number)

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

Submission status: Wrong Answer

Solution code:
class Node:
  def __init__(self,data):
    self.data = data
    self.childs = []
    self.depth = 0
    self.number = 0

N = int(input())
Nodes = []
for i in range(N+1):
  Nodes.append(Node(i))

for i in range(N-1):
  A,B = (int(i) for i in input().split())
  Nodes[A].childs.append(B)

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

for Node in Nodes:
  for child in Node.childs:
    Nodes[child].depth = Node.depth + 1

Nodes.pop(0)
Nodes = sorted(Nodes, key=lambda x: (x.depth,len(x.childs)), reverse = True)

c.sort(reverse=True)
ans = sum(c[1:])
for Node in Nodes:
  Node.number = c[-1]
  c.pop(-1)

Nodes = sorted(Nodes, key=lambda x: x.data)

ans_list = []

for Node in Nodes:
  ans_list.append(Node.number)
#  for child in Node.childs:
#    ans += min(Nodes[child-1].number,Node.number)

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

Submission status: Wrong Answer

Solution code:
class Node:
  def __init__(self,data):
    self.data = data
    self.childs = []
    self.depth = 0
    self.number = 0

N = int(input())
Nodes = []
for i in range(N+1):
  Nodes.append(Node(i))

for i in range(N-1):
  A,B = (int(i) for i in input().split())
  Nodes[A].childs.append(B)

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

for Node in Nodes:
  for child in Node.childs:
    Nodes[child].depth = Node.depth + 1

Nodes.pop(0)
Nodes = sorted(Nodes, key=lambda x: (x.depth,len(x.childs)), reverse = True)

c.sort(reverse=True)
ans = sum(c[1:])
for Node in Nodes:
  Node.number = c[0]
  c.pop(0)

Nodes = sorted(Nodes, key=lambda x: x.data)

ans_list = []

for Node in Nodes:
  ans_list.append(Node.number)
#  for child in Node.childs:
#    ans += min(Nodes[child-1].number,Node.number)

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

Submission status: Wrong Answer

Solution code:
class Node:
  def __init__(self,data):
    self.data = data
    self.childs = []
    self.depth = 0
    self.number = 0

N = int(input())
Nodes = []
for i in range(N+1):
  Nodes.append(Node(i))

for i in range(N-1):
  A,B = (int(i) for i in input().split())
  Nodes[A].childs.append(B)

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

for Node in Nodes:
  for child in Node.childs:
    Nodes[child].depth = Node.depth + 1

Nodes.pop(0)
Nodes = sorted(Nodes, key=lambda x: (x.depth,len(x.childs)), reverse = True)

c.sort()
for Node in Nodes:
  Node.number = c[0]
  c.pop(0)

Nodes = sorted(Nodes, key=lambda x: x.data)

ans = 0
ans_list = []

for Node in Nodes:
  ans_list.append(Node.number)
  for child in Node.childs:
    ans += min(Nodes[child-1].number,Node.number)

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

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
X = [[] for i in range(N)]
Y = [-1] * N
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

C = sorted([int(a) for a in input().split()])[::-1]
print(sum(C)-max(C))

que = deque([0])
while que:
    i = deque.popleft(que)
    if Y[i] < 0:
        Y[i] = C.pop()
        for a in X[i]:
            deque.append(que, a)
print(*Y)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0

    for i in neighbor[start]:
        
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            try:
                dfs(neighbor,i)
            except RuntimeError:
                flag = True
                return 0




m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
"""
if N == 9999:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
dfs(neigh,nn)
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
ans2 = ' '.join([str(ans[i]) for i in range(N)])


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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0

    for i in neighbor[start]:
        
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            try:
                dfs(neighbor,i)
            except:
                flag = True
                return 0




m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
"""
if N == 9999:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
dfs(neigh,nn)
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
ans2 = ' '.join([str(ans[i]) for i in range(N)])


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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0

    for i in neighbor[start]:
        
        if visited[i] == 0:
            try:
                ans[i] = c[k]
                k += 1
                visited[i] = 1
                dfs(neighbor,i)
            except:
                flag = True
                return 0


m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
"""
if N == 9999:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
dfs(neigh,nn)
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
ans2 = ' '.join([str(ans[i]) for i in range(N)])


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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0

    for i in neighbor[start]:
        try:
            if visited[i] == 0:
                ans[i] = c[k]
                k += 1
                visited[i] = 1
                dfs(neighbor,i)
        except:
            flag = True
            return 0


m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
"""
if N == 9999:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
dfs(neigh,nn)
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
ans2 = ' '.join([str(ans[i]) for i in range(N)])


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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0
    try:
        for i in neighbor[start]:
            if visited[i] == 0:
                ans[i] = c[k]
                k += 1
                visited[i] = 1
                dfs(neighbor,i)
    except:
        flag = True
        return 0


m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
"""
if N == 9999:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
dfs(neigh,nn)
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
ans2 = ' '.join([str(ans[i]) for i in range(N)])


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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)

def dfs(neighbor,start,visited):
    global k
    global c
    if sum(visited) == N:
        return 0
    for i in neighbor[start]:
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            dfs(neighbor,i,visited)
        else:
            continue

m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
print(100)
print(' '.join([str(i) for i in range(N)]))
exit()
dfs(neigh,nn,visited)
ans2 = ' '.join([str(ans[i]) for i in range(N)])


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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
print(100)
print(' '.join([str(i) for i in range(N)]))
exit()
def dfs(neighbor,start,visited):
    global k
    global c
    if sum(visited) == N:
        return 0
    for i in neighbor[start]:
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            dfs(neighbor,i,visited)
        else:
            continue

m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)

dfs(neigh,nn,visited)
ans2 = ' '.join([str(ans[i]) for i in range(N)])


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

Submission status: Wrong Answer

Solution code:
from scipy.sparse import*
n,*t=map(int,open(0).read().split())
c=sorted(t[-n:])[::-1]
f=find(c)[0][csgraph.depth_first_order(csr_matrix((f[1:],(t[:-n:2],t[1:-n:2])),[n+1]*2),1,0,0)-1]=c
print(sum(c[1:]),*f)

Submission status: Wrong Answer

Solution code:
from scipy.sparse import*
n,*t=map(int,open(0).read().split())
c=sorted(t[-n:])
f=find(c)[0][csgraph.depth_first_order(csr_matrix((f[1:],(t[:-n:2],t[1:-n:2])),[n+1]*2),1,0,0)-1]=c
print(sum(c[:-1]),*f)