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: Runtime Error

Solution code:
def add_node_2_tree_dic(tree_dic, x, y):
    if x not in tree_dic:
        tree_dic[x] = [y]
    else:
        tree_dic[x].append(y)

#   深さ優先探索で行けそう

N = int(input())
tree_dic = {}
for _ in range(N-1):
    a, b = map(int, input().split())
    add_node_2_tree_dic(tree_dic, a, b)
    add_node_2_tree_dic(tree_dic, b, a)

c_lst = list(map(int, input().split()))
c_lst.sort()
ans_lst = [0]*N

def search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst):
    tmp_lst = tree_dic[current_node][:]

    for next_node in tmp_lst:
        try:
            c = c_lst.pop()
            ans += c
            ans_lst[next_node - 1] = c

            tree_dic[current_node].remove(next_node)    #   今回通った枝を取り払う
            tree_dic[next_node].remove(current_node)
        except:
            return ans
            
        if len(tree_dic[current_node]) == 0:
            del tree_dic[current_node]#   探索し終えたノードの削除
        if len(tree_dic[next_node]) == 0:
            del tree_dic[next_node]#   探索し終えたノードの削除
            
        else:   #   次のノードにつながっている辺があるとき
            ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)


    return ans


ans = 0
current_node = 1
ans_lst[0] = c_lst.pop()
ans = search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst)


ans_str = ""
for i in range(N):
    ans_str += str(ans_lst[i])
    if i != N - 1:
        ans_str += " "


print(ans)
print(ans_str)

Submission status: Runtime Error

Solution code:
n = int(input())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i], b[i] = list(map(int, input().split()))
c = list(map(int, input().split()))
c.sort()
x = a
x.extend(b)
y = []
for i in range(n-1):
    y.append([i,x.count(i+1)])

y.sort(key=lambda x:x[1])
y.reverse()

s = 0
z = [0]*n
for i in range(n):
    z[y[i][0]] = c[i]
    
for i in range(n):
    s = s+min(c[a[i]-1],c[b[i]-1])

print(s)
for i in range(n):
  print(c[i], end=" ")

Submission status: Runtime Error

Solution code:
n = int(input())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i], b[i] = list(map(int, input().split()))
c = list(map(int, input().split()))
c.sort()
x = a
x.extend(b)
y = []
for i in range(n):
    y.append([i,x.count(i+1)])

y.sort(key=lambda x:x[1])
y.reverse()

s = 0
z = [0]*n
for i in range(n):
    z[y[i][0]] = c[i]
    
for i in range(n):
    s = s+min(c[a[i]-1],c[b[i]-1])

print(s)
for i in range(n):
  print(c[i], end=" ")

Submission status: Runtime Error

Solution code:
n = int(input())

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

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

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

c.sort(reverse=True)

w = [0] * n

w[0] = c.pop(0)

chk = [i for i in edge[0]]
# print(chk)

while chk != []:
    node = chk.pop(0)
    if w[node] == 0:
        w[node] = c.pop(0)
        chk.extend(edge[node])

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

print(' '.join(map(str, w)))

Submission status: Runtime Error

Solution code:
def add_node_2_tree_dic(tree_dic, x, y):
    if x not in tree_dic:
        tree_dic[x] = [y]
    else:
        tree_dic[x].append(y)

#   深さ優先探索で行けそう

N = int(input())
tree_dic = {}
for _ in range(N-1):
    a, b = map(int, input().split())
    add_node_2_tree_dic(tree_dic, a, b)
    add_node_2_tree_dic(tree_dic, b, a)

c_lst = list(map(int, input().split()))
c_lst.sort()
ans_lst = [0]*N

def search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst):
    tmp_lst = tree_dic[current_node][:]
    for next_node in tmp_lst:
        c = c_lst.pop()
        ans += c
        ans_lst[next_node - 1] = c

        tree_dic[current_node].remove(next_node)    #   今回通った枝を取り払う
        tree_dic[next_node].remove(current_node)
        if len(tree_dic[current_node]) == 0:
            del tree_dic[current_node]#   探索し終えたノードの削除
        if len(tree_dic[next_node]) == 0:
            del tree_dic[next_node]#   探索し終えたノードの削除
            
        else:   #   次のノードにつながっている辺があるとき
            ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)



    return ans


ans = 0
current_node = 1
ans_lst[0] = c_lst.pop()
ans = search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst)


ans_str = ""
for i in range(N):
    ans_str += str(ans_lst[i])
    if i != N - 1:
        ans_str += " "


print(ans)
print(ans_str)

Submission status: Runtime Error

Solution code:
N = int(input())
ab_s = [list(map(int, input().split())) for _ in range(N-1)]
cs = list(map(int, input().split()))
cs.sort(reverse=True)

# graph = [[[connected nord, weight], [cn2, w2]], [[]], ... , [[]]]
graph = [[] for _ in range(N)]
for ab in ab_s:
  a = ab[0] - 1
  b = ab[1] - 1
  graph[a].append([b,0])
  graph[b].append([a,0])

value = [0]*N
visited = [0]*N

def dfs(cur, par):
  global cs
  global value
  global visited

  if len(graph[cur])==1 and par!=-1 and visited[cur]==0: # leaf
    value[cur] = cs.pop()
    visited[cur] = 1
  else:
    for nord in graph[cur]:
      if nord[0] == par:
        continue
      if visited[nord[0]]==0:
        dfs(nord[0], cur)
    else:
      value[cur] = cs.pop()
      visited[cur] = 1

dfs(0, -1)

value = list(map(str,value))
print(' '.join(value))

Submission status: Runtime Error

Solution code:
n = int(input())
adj = [[i,0] for i in range(n+1) ]
adj_path = []
for _ in range(n-1):
    a,b = map(int,input().split())
    adj_path.append([a,b])
    adj[a][1] += 1
    adj[b][1] += 1
c_list = sorted(list(map(int,input().split())))
out = [0 for i in range(n+1)]
if len(adj_path) == 0:
    print(0)
    print(" ")
else:
    for i,[name,rank] in enumerate(sorted(adj,key=lambda x:x[1])):
        if name != 0:
            out[name] = c_list[i]
    score = 0
    for a,b in adj_path:
        score += min(out[a],out[b])
    print(score)
    print(" ".join(str(x) for x in out[1:]))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import collections
import itertools

# 整数入力
n = int(input())

list = []
for i in range(n-1):
  k = input().strip()
  list.append([k[0],k[2]])

num = input().split()
#num.sort(reverse=True)

#print(list)
#print(num)

max = 0
j = []
for v in itertools.permutations(num, 5):
  j = []
  for i,e in enumerate(v):
    j.append(e)
  sum = 0
  for l in list:
    f = int(l[0])
    s = int(l[1])
    if int(j[f-1])<int(j[s-1]):
      sum = sum + int(j[f-1])
    else:
      sum = sum + int(j[s-1])


  if max < sum:
    max = sum
    max_num = j
    #print(str(max))
    #print(max_num)

print(str(max))
for nu in max_num:
  print(str(nu), end = " ")

print("")

Submission status: Runtime Error

Solution code:

def add_node_2_tree_dic(tree_dic, x, y):
    if x not in tree_dic:
        tree_dic[x] = [y]
    else:
        tree_dic[x].append(y)

#   深さ優先探索で行けそう

N = int(input())
tree_dic = {}
for _ in range(N-1):
    a, b = map(int, input().split())
    add_node_2_tree_dic(tree_dic, a, b)
    add_node_2_tree_dic(tree_dic, b, a)

c_lst = list(map(int, input().split()))
c_lst.sort()
ans_lst = [0]*N

def search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst):
    
    judge = True
    for key in tree_dic:
        if tree_dic[key] != 0:
            judge = False
    
    if judge:
        return ans

    if len(tree_dic) == 0:  #   これなしでいい？
        return ans

    tmp_lst = tree_dic[current_node][:]
    for next_node in tmp_lst:

        c = c_lst.pop()
        ans += c
        ans_lst[next_node - 1] = c

        tree_dic[current_node].remove(next_node)    #   今回通った枝を取り払う
        tree_dic[next_node].remove(current_node)
            
        ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)

    return ans


ans = 0
current_node = 1
ans_lst[0] = c_lst.pop()
ans = search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst)


ans_str = ""
for i in range(N):
    ans_str += str(ans_lst[i])
    if i != N - 1:
        ans_str += " "


print(ans)
print(ans_str)

Submission status: Runtime Error

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

x = a.extend(b)
y = []
for i in range(n):
    y.append([i+1,x.count(i+1)])

y.sort(key=lambda x:x[1])
y.reverse()

s = 0
z = [0]*n
for i in range(n):
    z[y[i][0]] = c[i]
    
for i in range(n):
    s = s+min(c[a[i]],c[b[i]])

print(s)
print(c)

Submission status: Runtime Error

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

edge_list = [[] for j in range(N)]

c.sort()
ans = sum(c[:-1])


ans_list = [0]*N

#あるノードを訪れたか
node_visit = [False]*N

#それぞれのノード番号が何回登場するかメモ
num_count = [0]*N
for edge in ab:
    num_count[edge[0]-1] += 1
    num_count[edge[1]-1] += 1
    # print(edge)
    # print(edge[0]-1)
    edge_list[edge[0]-1].append(edge)
    edge.reverse()
    # print(edge)
    # print(edge[0]-1)
    edge_list[edge[0]-1].append(edge)

#例外処理
f = 0


if num_count.count(1) != 2:
    max_node = num_count.index(N-1)
    f = 1

start = num_count.index(1)
num_count[start] += 1
goal = num_count.index(1)

#シミュレート
#"now_nodeはインデックス"
now_node = start
def saiki(now_node,ans_list,c):
    # print(now_node,node_visit)
    if node_visit[now_node] == True: return
    if len(c)== 0: return
    node_visit[now_node] = True
    ans_list[now_node] = c.pop()
    if now_node == goal:
        return
    for node in (edge_list[now_node]):
        if not(node_visit[node[0]-1]):
            next_node  = node[0]-1
            saiki(next_node,ans_list,c)
        if not(node_visit[node[1]-1]):
            # print("aaa")
            next_node  = node[1]-1
            saiki(next_node,ans_list,c)
    return




if f == 0:
    saiki(start,ans_list,c)

if f == 1:
    # print(c.pop(-1))
    ans_list[max_node] = c.pop()
    if max_node == len(c):
        ans_list =  c[:max_node]+ [ans_list[max_node]] 
    else:
        ans_list =  c[:max_node]+ [ans_list[max_node]] + c[max_node:]



# print(start,goal)

# print(edge_list)
# # print(num_count)

# print(ans_list)

print(ans)
for i in ans_list:
    print(i,end="")
    print(" ",end="")

Submission status: Runtime Error

Solution code:
import heapq
n=int(input())
ab = [list(map(int, input().split())) for _ in range(n-1)]
c=sorted(list(map(lambda x:-int(x), input().split())))
print(-sum(c[1:]))
heapq.heapify(c)
mat = [[] for _ in range(n+1)]
ans=[0]*n
for i in range(n-1):
    a, b = ab[i]
    mat[a].append(b)
    mat[b].append(a)
def dp(x, y):
    ans[y-1]=-heapq.heappop(c)
    if y>1 and len(mat[y])==1:
        return
    for i in mat[y]:
        if i!=x:
            dp(y, i)
dp(0, 1)
print(' '.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
n=int(input())
abs=[0]*n

for i in range(n-1):
    abs[i]=[list(map(int,input().split()))]
cs=[c in list(map(int,input(split())))]

cnt=[0]*n
for i in range(n-1):
    ma=max(cnt[abs[i][0]], cnt[abs[i][1]])
    ma+=1
    cnt[abs[i][0]]=ma
    cnt[abs[i][1]]=ma

for i in range(n-1):
    ma=max(cnt[abs[i][0]], cnt[abs[i][1]])
    cnt[abs[i][0]]=ma
    cnt[abs[i][1]]=ma

ans=[0]*n
for i in range(n):
    ans[cnt.index(max(cnt))]=max(cs)
    cnt[cnt.index(max(cnt))]=0
    cs[cs.index(max(cs))]=0

print(ans)

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python3
# -*- coding: utf-8 -*-
N = int(input())
abls =[]
for i in range (N-1):
    ab= [int(x) for x in (input().split())]
    abls.append(ab)
clist = [int(x) for x in input().split()]
clist.sort(reverse = True)
sum = 0
count = 0
for i in range (N-1):
    a = abls[i][0]
    b = abls[i][1]

    aa = clist[a-1]
    bb = clist[b-1]
    if clist[count] >= clist[a-1]:
        clist[a-1] = clist[count]
        clist[count] = aa
        count+= 1

  
    if clist[count] >= clist[b-1]:
        clist[b-1] = clist[count]
        clist[count] == bb
        count+= 1
    sum += min(clist[a-1], clist[b-1])

print(sum)
print(clist)

Submission status: Runtime Error

Solution code:
class Tree:
    def __init__(self, N):
        self.par = [i for i in range(n+1)]
        self.child = [[] for i in range(n+1)]
        self.val = [0 for i in range(n+1)]
        self.q = [1]
        self.check = []

    def fix(a, b):
        if a < b:
            self.par[b] = a
        else:
            self.par[a] = b

    def find():
        for i in range(len(self.par)):
            self.child[self.par].append(i)

    def ins(c):
        for i in self.q:
            self.check.append(i)
            clear(self.q)

        for i in self.child[c]:
            self.q.append(i)

        if not len(self.child[c]) == 0:
            ins(c+1)

N = int(input())

tree = Tree(N)

for i in range(n):
    a, b = map(int, input().split())
    tree.fix(a, b)

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

tree.find()

ins(1)

c.sort(reverse = True)

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

for i in range(n):
    ans[tree.check[i+1]] = c[i]

for i in range(n):
    print(ans[i])

Submission status: Runtime Error

Solution code:
N=int(input())
nodes=[0]*(N+1)
edge_list=[]
point_dic={}
for i in range(N-1):
    a,b=map(int,input().split())
    nodes[a]+=1
    nodes[b]+=1
    edge_list.append((a,b))
    point_dic.setdefault(a,[]).append(b)
    point_dic.setdefault(b,[]).append(a)
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)

def around(posi):
    new_dic={}
    for around_posi in point_dic[posi+1]:
        new_dic.append(nodes[around_posi],[]).append(around_posi)
    new_dic_sorted=sorted(new_dic.items(), key=lambda x:x[0], reverse=True)    
    
    for i in range(len(new_dic_sorted)): 
        for posi in node_dic[new_dic_sorted[i][0]]:
        if len(c)==0:
            break
        if ans[around_posi-1]==0:
            ans[around_posi-1]=c.pop(0)
            #print(ans)
ans=[0]*N
for i in range(len(node_dic_sorted)):
    for posi in node_dic[node_dic_sorted[i][0]]:
        if ans[posi]==0:
            #print(posi)
            ans[posi]=c.pop(0)
            around(posi)
        if len(c)==0:
            break
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: Runtime Error

Solution code:
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
using namespace std;

long long c[10000];
int a[10000];
int b[10000];
int degrees[10000];
bool used[10000];
long long v_weights[10000];
pair <int, int> degree_v[10000];
vector <int> edges[10000];
int main(){
    int N;
    cin >> N;
    for(int i = 0; i < N - 1; i++){
        cin >> a[i] >> b[i];
        
        a[i] --;
        b[i] --;
        edges[a[i]].push_back(b[i]);
        edges[b[i]].push_back(a[i]);
        degrees[a[i]] ++;
        degrees[b[i]] ++;
    }

    priority_queue <int, int> alt_degree_v;
    for(int i = 0; i < N; i++){
        degree_v[i] = make_pair(degrees[i], i);
        alt_degree_v.push(make_pair(-degree[i], i));
    }
    //sort(degree_v, degree_v + N);

    for(int i = 0; i < N; i++){
        cin >> c[i];
    }
    sort(c, c + N);
    
    for(int i = 0; i < N; i++){
        auto cur = alt_degree_v.top();
        v_weights[cur.second] = c[i];
        used[cur.second] = true;
        for(int j = 0; j < edges[cur.second].size(); j++){
            
            int tmp_v = edges[cur.second][j];
            if(!used[tmp_v]){
                alt_degree_v.push(make_pair(- degree[tmp_v] + 1, tmpv));
            }

        }
    }

    long long ans = 0;
    for(int i = 0; i < N - 1; i++){
        ans += min(v_weights[a[i]], v_weights[b[i]]);
    }
    cout << ans << endl;
    for(int i = 0; i < N; i++){
        if(i < N - 1){
            cout << v_weights[i] << " ";
        } else {
            cout << v_weights[i] << endl;
        }
    }
    return 0;
}

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
degree = np.zeros(N)
for i in range(N-1):
    A, B = map(int, input().split())
    degree[A-1] += 1
    degree[B - 1] += 1
dic = {}
for k in range(N):
    dic[k] = degree[k]
score = list(map(int, input().split()))
sum = 0
sort_score = sorted(score, reverse=True)
sort_degree = sorted(dic.items(), key=lambda x: x[1], reverse=True)
print("{}".format(sort_degree))
for j in range(1, N):
    sum += sort_score[j]
new_degree = np.zeros(N)
Z = dic.keys()
print("{}".format(Z))
for m in range(N):
    X = Z(m)
    new_degree[Z] = sort_score[m]
print("{}".format(sum))
print("{}".format(new_degree))

Submission status: Runtime Error

Solution code:
import itertools

N = int(input())
A = list()
B = list()
for i in range(N - 1) :
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
C = list(map(int, input().split()))
O = list(itertools.permutations(C))  #C の全要素の順列を生成しlistに格納

n = 1
for i in range(N) :
  n *= i

x = list()
S = 10000000000

for i in range(n) :
  s = 0
  for j in range(N - 1, 1, -1) :
    x = c[i]
    if(x[j] < x[j - 1]) :
      s += x[j]
    else :
      s += x[j - 1]
  if(s < M) :
    M = s
    d = x
  else :
    pass
  return M
  return d
  
print(M)
for i in range(N) :
  print(d[i], "", end = "")

Submission status: Runtime Error

Solution code:
n=int(input())
abs=[]*n

for i in range(n-1):
    abs[i]=[list(map(int,input().split()))]
cs=[c in list(map(int,input(split())))]

cnt=[0]*n
for i in range(n-1):
    ma=max(cnt[abs[i][0]], cnt[abs[i][1]])
    ma+=1
    cnt[abs[i][0]]=ma
    cnt[abs[i][1]]=ma

for i in range(n-1):
    ma=max(cnt[abs[i][0]], cnt[abs[i][1]])
    cnt[abs[i][0]]=ma
    cnt[abs[i][1]]=ma

ans=[0]*n
for i in range(n):
    ans[cnt.index(max(cnt))]=max(cs)
    cnt[cnt.index(max(cnt))]=0
    cs[cs.index(max(cs))]=0

print(ans)

Submission status: Runtime Error

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

edge_list = [[] for j in range(N)]

c.sort()
ans = sum(c[:-1])


ans_list = [0]*N

#あるノードを訪れたか
node_visit = [False]*N

#それぞれのノード番号が何回登場するかメモ
num_count = [0]*N
for edge in ab:
    num_count[edge[0]-1] += 1
    num_count[edge[1]-1] += 1
    # print(edge)
    # print(edge[0]-1)
    edge_list[edge[0]-1].append(edge)
    edge.reverse()
    # print(edge)
    # print(edge[0]-1)
    edge_list[edge[0]-1].append(edge)

#例外処理
f = 0


if num_count.count(1) != 2:
    max_node = num_count.index(N-1)
    f = 1

start = num_count.index(1)
num_count[start] += 1
goal = num_count.index(1)

#シミュレート
#"now_nodeはインデックス"
now_node = start
def saiki(now_node,ans_list,c):
    # print(now_node,node_visit)
    if node_visit[now_node] == True: return
    if len(c)== 0: return
    node_visit[now_node] = True
    ans_list[now_node] = c.pop()
    if now_node == goal:
        return
    for node in (edge_list[now_node]):
        if not(node_visit[node[0]-1]):
            next_node  = node[0]-1
            saiki(next_node,ans_list,c)
        if not(node_visit[node[1]-1]):
            # print("aaa")
            next_node  = node[1]-1
            saiki(next_node,ans_list,c)
    return




if f == 0:
    saiki(start,ans_list,c)

if f == 1:
    # print(c.pop(-1))
    ans_list[max_node] = c.pop()
    ans_list =  c[:max_node]+ [ans_list[max_node]] + c[max_node:]



# print(start,goal)

# print(edge_list)
# # print(num_count)

# print(ans_list)

print(ans)
for i in ans_list:
    print(i,end="")
    print(" ",end="")

Submission status: Runtime Error

Solution code:
class Queue(object): 

def __init__(self): 
self.queue_list = [] 

def enqueue(self, value): 
self.queue_list.append(value) 

def dequeue(self): 
try: 
value = self.queue_list.pop(0) 
except IndexError: 
value = None 

return value 
N = int(input()) 

pair = [] 
tree = {} 

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

if b in tree.keys(): 
tree[b].append(a) 
else: 
tree[b] = [a] 
pair.append([a,b]) 

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


queue = Queue() 
tree_l = {} 
for key in tree.keys(): 
tree_l[key] = len(tree[key]) 

ans = {} 
max_node = max((v, k) for k, v in tree_l.items())[1] 
ans[max_node] = c[0] 
used = [max_node] 
cnt = 0 

candi = {} 
for i in tree[max_node]: 
candi[i] = tree_l[i] 

for k, v in sorted(candi.items(), key=lambda x: -x[1]): 
queue.enqueue(k) 
used.append(k) 

while True: 
node = queue.dequeue() 
cnt += 1 
ans[node] = c[cnt] 

if cnt == N-1: 
break 

candi = {} 
for i in tree[node]: 
candi[i] = tree_l[i] 
for k, v in sorted(candi.items(), key=lambda x: -x[1]): 
if k not in used: 
queue.enqueue(k) 
used.append(k) 
total = 0 
for a, b in pair: 
if ans[a] > ans[b]: 
total += ans[b] 
else: 
total += ans[a] 

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

print(ans[N])

Submission status: Runtime Error

Solution code:
score = 0

def m():
    N = int(input())
    g = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)
    C = list(map(int, input().split()))
    C.sort(reverse=True)
    nodes = {}

    for i in range(1, N+1):
        nodes[i] = len(g[i])
    l = list(nodes.items())
    l.sort(reverse=True, key=lambda x:x[1])
    ans = [0] * N
    for k,v in l:
        ans[k-1] = C[k-1]

    visited = [False] * (N+1)
    def dfs(v, g):
        if visited[v] == True:
            return
        visited[v] = True
        for i in g[v]:
            global score
            score += min(ans[i-1], ans[v-1])
            dfs(i, g)
    dfs(1,g)
    print(score//2)
    return ans

print(*m())

Submission status: Runtime Error

Solution code:

def add_node_2_tree_dic(tree_dic, x, y):
    if x not in tree_dic:
        tree_dic[x] = [y]
    else:
        tree_dic[x].append(y)

#   深さ優先探索で行けそう

N = int(input())
tree_dic = {}
for _ in range(N-1):
    a, b = map(int, input().split())
    add_node_2_tree_dic(tree_dic, a, b)
    add_node_2_tree_dic(tree_dic, b, a)

c_lst = list(map(int, input().split()))
c_lst.sort()
ans_lst = [0]*N

def search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst):
    
    if len(tree_dic) == 0:  #   これなしでいい？
        return ans
    if len(tree_dic[current_node]) == 0:
        del tree_dic[current_node]#   探索し終えたノードの削除
        return ans
    tmp_lst = tree_dic[current_node][:]
    for next_node in tmp_lst:

        c = c_lst.pop()
        ans += c
        ans_lst[next_node - 1] = c

        tree_dic[current_node].remove(next_node)    #   今回通った枝を取り払う
        tree_dic[next_node].remove(current_node)
        if len(tree_dic[current_node]) == 0:
            del tree_dic[current_node]#   探索し終えたノードの削除
        if len(tree_dic[next_node]) == 0:
            del tree_dic[next_node]#   探索し終えたノードの削除
#                print()
            
        else:   #   次のノードにつながっている辺があるとき
            ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)



    return ans


ans = 0
current_node = 1
ans_lst[0] = c_lst.pop()
ans = search_next_node_and_add_side_wate(tree_dic, ans, current_node, c_lst, ans_lst)


ans_str = ""
for i in range(N):
    ans_str += str(ans_lst[i])
    if i != N - 1:
        ans_str += " "


print(ans)
print(ans_str)

Submission status: Runtime Error

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

edge_list = [[] for j in range(N)]

c.sort()
ans = sum(c[:-1])


ans_list = [0]*N

#あるノードを訪れたか
node_visit = [False]*N

#それぞれのノード番号が何回登場するかメモ
num_count = [0]*N
for edge in ab:
    num_count[edge[0]-1] += 1
    num_count[edge[1]-1] += 1
    # print(edge)
    # print(edge[0]-1)
    edge_list[edge[0]-1].append(edge)
    edge.reverse()
    # print(edge)
    # print(edge[0]-1)
    edge_list[edge[0]-1].append(edge)

#例外処理
f = 0


if num_count.count(1) != 2:
    max_node = num_count.index(N-1)
    f = 1

start = num_count.index(1)
num_count[start] += 1
goal = num_count.index(1)

#シミュレート
#"now_nodeはインデックス"
now_node = start
def saiki(now_node,ans_list,c):
    # print(now_node,node_visit)
    if node_visit[now_node] == True: return
    node_visit[now_node] = True
    ans_list[now_node] = c.pop()
    if now_node == goal:
        return
    for node in (edge_list[now_node]):
        if not(node_visit[node[0]-1]):
            next_node  = node[0]-1
            saiki(next_node,ans_list,c)
        if not(node_visit[node[1]-1]):
            # print("aaa")
            next_node  = node[1]-1
            saiki(next_node,ans_list,c)
    return




if f == 0:
    saiki(start,ans_list,c)

if f == 1:
    # print(c.pop(-1))
    ans_list[max_node] = c.pop()
    ans_list =  c[:max_node]+ [ans_list[max_node]] + c[max_node:]



# print(start,goal)

# print(edge_list)
# # print(num_count)

# print(ans_list)

print(ans)
for i in ans_list:
    print(i,end="")
    print(" ",end="")

Submission status: Runtime Error

Solution code:
import numpy as np
from sys import stdin

N = int(stdin.readline().rstrip())

vs = np.array([list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)])
cs = np.sort(np.array(list(map(int, stdin.readline().rstrip().split()))))[::-1]

max_score = np.sum(cs[1:])

def make_tree(i):
    global vs
    children = vs[np.any(vs == i, axis=1)].flatten()
    children = children[children != i]
    vs =vs[np.all(vs != i, axis=1)]
    return np.array([i, np.array(map(make_tree ,children))])

    # return np.array([i, np.array(list(map(make_tree ,children)))])

tree = make_tree(1)
c_pos = np.empty_like(cs)

def show_tree(tree):
    global cs
    c_pos[tree[0]-1] = cs[0]
    cs = np.delete(cs, 0)
    [show_tree(t) for t in tree[1]]

show_tree(tree)

print(max_score)
print(' '.join([str(c) for c in c_pos]))

Submission status: Runtime Error

Solution code:
import numpy as np
from sys import stdin

N = int(stdin.readline().rstrip())

vs = np.array([list(map(int, stdin.readline().rstrip().split())) for _ in range(N-1)])
cs = np.sort(np.array(list(map(int, stdin.readline().rstrip().split()))))[::-1]

max_score = np.sum(cs[1:])

def make_tree(i):
    global vs
    children = vs[np.any(vs == i, axis=1)].flatten()
    children = children[children != i]
    vs =vs[np.all(vs != i, axis=1)]
    return np.array([i, list(map(make_tree ,children))])

    # return np.array([i, np.array(list(map(make_tree ,children)))])

tree = make_tree(1)
c_pos = np.empty_like(cs)

def show_tree(tree):
    global cs
    c_pos[tree[0]-1] = cs[0]
    cs = np.delete(cs, 0)
    [show_tree(t) for t in tree[1]]

show_tree(tree)

print(max_score)
print(' '.join([str(c) for c in c_pos]))

Submission status: Runtime Error

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

edge_list = [[] for j in range(N)]

c.sort()
ans = sum(c[:-1])


ans_list = [0]*N

#あるノードを訪れたか
node_visit = [False]*N

#それぞれのノード番号が何回登場するかメモ
num_count = [0]*N
for edge in ab:
    num_count[edge[0]-1] += 1
    num_count[edge[1]-1] += 1
    # print(edge)
    # print(edge[0]-1)
    edge_list[edge[0]-1].append(edge)
    edge.reverse()
    # print(edge)
    # print(edge[0]-1)
    edge_list[edge[0]-1].append(edge)

#例外処理
f = 0

if num_count.count(1) != 2:
    max_node = num_count.count(N-1)-1
    f = 1

start = num_count.index(1)
num_count[start] += 1
goal = num_count.index(1)

#シミュレート
#"now_nodeはインデックス"
now_node = start
def saiki(now_node,ans_list,c):
    # print(now_node,node_visit)
    if node_visit[now_node] == True: return
    node_visit[now_node] = True
    ans_list[now_node] = c.pop()
    if now_node == goal:
        return
    for node in (edge_list[now_node]):
        if not(node_visit[node[0]-1]):
            next_node  = node[0]-1
            saiki(next_node,ans_list,c)
        if not(node_visit[node[1]-1]):
            # print("aaa")
            next_node  = node[1]-1
            saiki(next_node,ans_list,c)
    return




if f == 0:
    saiki(start,ans_list,c)

if f == 1:
    # print(c.pop(-1))
    ans_list[max_node] = c.pop()
    ans_list =  c[:max_node]+ [ans_list[max_node]] + c[max_node:]

# print(start,goal)

# print(edge_list)
# # print(num_count)

# print(ans_list)

print(ans)
for i in ans_list:
    print(i,end="")
    print(" ",end="")

Submission status: Runtime Error

Solution code:
a = "5" 
print "10"

Submission status: Runtime Error

Solution code:
import itertools,math
N = int(input())
list=[]
for i in range(N-1):
    a,b = input().split()
    list.append([int(a),int(b)])
c=[]
c_input = input().split()
for data in c_input:
    c.append(int(data))

ans=()
sum_ans=0
for index,v in enumerate(itertools.permutations(c)):
    sum=0
    for d in list:
        if v[d[0]-1] > v[d[1]-1]:
            sum+=v[d[1]-1]
        else:
            sum+=v[d[0]-1]
    if sum>sum_ans:
        ans=v
        sum_ans=sum
    if math.factorial(len(c))/1.5 < index:
        break

maped_list = map(str, ans)
print(sum_ans)
print(' '.join(maped_list))

Submission status: Runtime Error

Solution code:
visit_list = []


def topological_sort():
    for s in range(n):
        if color[s] == 0:
            dfs(s)

def dfs(u):
    color[u] = 1
    for v in graph[u]:
        if color[v] == 0:
            dfs(v)
    visit_list.append(u)        
 
 
n = int(input())
color = [0] * n
graph = [[] * n for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    graph[a].append(b)
    graph[b].append(a)    

topological_sort()
c = [int(i) for i in input().split()]
c.sort()
t_list = [[visit_list[i], str(c[i])] for i in range(n)]
t_list.sort()
print(sum(c) - c[-1])
print(" ".join(list(map(lambda x: x[1], t_list))))