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: Time Limit Exceeded

Solution code:
n=int(input())
list=[]
kazulist=[]
koho=[]

for i in range(n):
    list.append([])
    kazulist.append(0)
    koho.append(i)

for i in range(n-1):
    eda=input().split(" ")
    a=int(eda[0])
    b=int(eda[1])
    list[a-1].append(b)
    list[b-1].append(a)

count=1

nagasa=len(list)

while count<=n:
    newkoho=[]
    for e in koho:
        if len(list[e])==1:
            list[list[e][0]-1].remove(e+1)
            list[e]=[]
            kazulist[e]=count
            count+=1
        elif list[e]==[] and kazulist[e]==0:
            kazulist[e]=count
            count+=1
        else:
            koho.append(e)
    koho=newkoho


kouho = [int(i) for i in input().split()] 
kouho=sorted(kouho)
gokei=sum(kouho[:n-1])
print(gokei)
text=""
for i in range(n-1):
    text+=(str(kouho[kazulist[i]-1])+" ")
text+=str(kouho[kazulist[n-1]-1])
print(text)

Submission status: Time Limit Exceeded

Solution code:
a = 1
for i in range(10000**2 * 10):
  a = a + 1

Submission status: Time Limit Exceeded

Solution code:
a = 1
for i in range(100000**2):
  a = a + 1

Submission status: Time Limit Exceeded

Solution code:
import copy

n = int(input())

edge_list = []
val_list = []
val_dict = dict()

for i in range(n-1):
    line = input()
    splitted = line.split(' ')
    edge_list.append([int(splitted[0]), int(splitted[1])])

line = input()
line_list = line.split(' ')
for item in line_list:
    val_list.append(int(item))

val_list.sort()
edge_list_ret = copy.copy(edge_list)

for i in range(n-1):

    count_list = [0] * n
    for k in val_dict.keys():
        count_list[k] = 10000000

    for item in edge_list:
        count_list[item[0]-1] += 1
        count_list[item[1]-1] += 1

    index = count_list.index(min(count_list))

    for j in range(len(edge_list)):
        if edge_list[j][0] == (index+1) or edge_list[j][1] == (index+1):
            edge_list.pop(j)
            val_dict[index] = val_list.pop(0)
            break

for i in range(n):
    if not (i in val_dict):
        val_dict[i] = val_list.pop(0)


ret_list = []
ret_value = 0

for item in edge_list_ret:
    ret_value += min(val_dict[item[0]-1], val_dict[item[1]-1])

for i in range(n):
    ret_list.append(val_dict[i])


ret_list_str = map(lambda x: str(x), ret_list)
print(ret_value)
print(" ".join(ret_list_str))

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
c = map(int, input().split())
ans = 0
array = []
for i in itertools.permutations(c):
  i = list(i)
  tmp = 0
  for j in range(N - 1):
    tmp += min(i[ab[j][0] - 1], i[ab[j][1] - 1])
  if ans < tmp:
    array = i
    ans = max(ans, tmp)
print(ans)
print(*array)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
a = []
b = []
l = []
s = 0
dic = {}
for i in range(n-1):
    a1,b1 = [int(i) for i in input().split()]
    a.append(a1)
    b.append(b1)
c = list(map(int,input().split()))
c.sort()
c.reverse()
d = a + b
e = collections.Counter(d)
for i in range(n):
    l.append(e.most_common()[i][0])
for i in range(n):
    dic[l[i]] = c[i]
ans = sorted(dic.items())
for i in range(n-1):
    s = s + min(dic.get(a[i]),dic.get(b[i]))
print(s)
print(" ".join(map(str,dic.values())))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
list=[]
kazulist=[]
for i in range(n):
    list.append([])
    kazulist.append(0)

for i in range(n-1):
    eda=input().split(" ")
    a=int(eda[0])
    b=int(eda[1])
    list[a-1].append(b)
    list[b-1].append(a)

count=1

while count<=n:
    nagasa=len(list)
    for e in range(nagasa):
        if len(list[e])==1:
            list[list[e][0]-1].remove(e+1)
            list[e]=[]
            kazulist[e]=count
            count+=1
        elif list[e]==[] and kazulist[e]==0:
            kazulist[e]=count
            count+=1


kouho = [int(i) for i in input().split()] 
kouho=sorted(kouho)
gokei=sum(kouho[:n-1])
print(gokei)
text=""
for i in range(n-1):
    text+=(str(kouho[kazulist[i]-1])+" ")
text+=str(kouho[kazulist[n-1]-1])
print(text)

Submission status: Time Limit Exceeded

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

def ab(i):
    global c,l,x
    while len(l[i])>0:
        try:
            x[l[i][0]]=c.pop(0)
            l[l[i][0]].remove(i)
            ab(l[i][0])
            l[i].pop(0)
        except:
            pass
    return

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

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

N = int(input())
h = [[0, i] for i in range(N)]
# 次数と頂点番号

es = [[] for idx in range(N)]
# es[idx]:=[隣接リスト]

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

c = list(map(int, input().split()))
c.sort()
# スコアが小さい順にソート

v = [-1] * N
ans = 0

cur = 0
for _ in range(N):
    t = list(sorted(h, key=itemgetter(0)))
    # print(t)
    idx = t[cur][1]
    v[idx] = c[cur]
    ans += c[cur]
    h[idx][0] -= 1
    for nv in es[idx]:
        h[nv][0] -= 1
    cur += 1
ans -= c[-1]
# print(t)
print(ans)
print(*v)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
list=[]
kazulist=[]
for i in range(n):
    list.append([])
    kazulist.append([])

for i in range(n-1):
    eda=input().split(" ")
    a=int(eda[0])
    b=int(eda[1])
    list[a-1].append(b)
    list[b-1].append(a)

#print(list)

count=1

while count<=n:
    nagasa=len(list)
    for e in range(nagasa):
        if len(list[e])==1:
            list[list[e][0]-1].remove(e+1)
            list[e]=[]
            kazulist[e].append(count)
            count+=1
        elif list[e]==[] and len(kazulist[e])==0:
            kazulist[e].append(count)
            count+=1

#print(list)
#print(kazulist)

kouho=input().split(" ")
for k in range(n):
    kouho[k]=int(kouho[k])
kouho=sorted(kouho)
#print(kouho)
gokei=sum(kouho[:n-1])
print(gokei)
text=""
for i in range(n-1):
    #print(kouho[kazulist[i][0]-1])
    text+=(str(kouho[kazulist[i][0]-1])+" ")
text+=str(kouho[kazulist[n-1][0]-1])
print(text)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
A = []
B = []
D = []
for i in range(N-1):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

C = list(map(int, input().split()))
D = C.copy()
_list = []
buff = []
_sum = 0
_d = list(itertools.permutations(D)) # 組み合わせ
ans = 0
for n in range(len(_d)):
    _list = []
    for i in range(N-1):
        _list.append(min(_d[n][A[i]-1],_d[n][B[i]-1]))
    _sum = sum(_list)
    if sum(_list) > ans:
        buff = _d[n]
        ans = _sum


print(ans)
print(" ".join([str(n) for n in buff]))

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())
L = []
for i in range(N-1):
    L.append([int(n) for n in input().split()])

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

score = []
for comb in itertools.permutations(C):
    l = 0
    for a, b in L:
        l += min(comb[a-1], comb[b-1])

    score.append([l, comb])

maxl = max(score, key=lambda x:x[0])

print(maxl[0])
print(' '.join(list(map(str, maxl[1]))))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
d=np.zeros((n+1,n+1),dtype=np.int64)
for i in range(n-1):
     a,b=map(int,input().split())
     d[a][b]=-1
     d[b][a]=-1
for i in range(n):
     d[i+1,0]=np.sum(d[i+1,1:])
c=sorted(list(map(int,input().split())))
idxs=np.argsort(d[1:,0])
for idx in idxs:
     idx+=1
     x=c.pop()
     d[idx,0]=x
     d[0,idx]=x
for i in range(n):
     for j in range(n):
          if d[i+1,j+1]!=-1:
               continue
          d[i+1,j+1]=min(d[i+1,0],d[0,j+1])
print(int(np.sum(d[1:,1:])/2))
d=list(map(str,map(int,list(d[0,1:]))))
print(' '.join(d))

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
input = sys.stdin.readline
from array import array
def solve():
  n = int(input())
  query2 = collections.deque([])
  ans = array('I', [ 0 for i in range(n)])
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query2.append(a)
    query2.append(b)
    
  c = list(int(i) for i in input().split())
  c = sorted(c,reverse =True)
  
  d = collections.Counter(query2)

  for i in range(n):
    ans[d.most_common()[i][0]-1] = c[i]
    
  print(sum(c) +(-1)*max(c))
  #dの処理
  print(*ans)
  
solve()

Submission status: Time Limit Exceeded

Solution code:
import copy
import time


arc_ = []


N = int(input())

len_l = 2
# N = 2 
while len_l == 2:
    line = input().split()
    len_l = len(line)
    if len_l == 2:
        arc_.append([int(line[0]), int(line[1])])
    else:
        c_ = [int(v) for v in line]
start = time.time()
      
max_value = 0
max_c = []

def get_result(arc, c_set):
    sum_v = 0
    for i in range(len(arc)):
        sum_v += min(c_set[arc[i][0]-1], c_set[arc[i][1]-1])
    return sum_v

def poi(ct, arc, c_set=[]):
    global max_value, max_c, start
    
    if time.time() - start >= 1.9:
        return
    
    if len(ct) == 0:
        result = get_result(arc, c_set)
        if result > max_value:
            max_value = result
            max_c = c_set
    else:
        for i in range(len(ct)):
            c_set_tmp = copy.deepcopy(c_set)
            c_set_tmp.append(ct[i])
            ct_tmp = copy.deepcopy(ct)
            ct_tmp.remove(ct[i])
            poi(ct_tmp, arc, c_set_tmp)
            
poi(c_, arc_)

print(max_value)
print(' '.join([str(v) for v in max_c]))

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())
L = []
for i in range(N-1):
    L.append([int(n) for n in input().split()])

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

score = []
for comb in itertools.permutations(C):
    l = 0
    for a, b in L:
        l += min(comb[a-1], comb[b-1])

    score.append([l, comb])


print(max(score, key=lambda x:x[0])[0])
print(' '.join(list(map(str, max(score, key=lambda x:x[0])[1]))))

Submission status: Time Limit Exceeded

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

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

C2 = []
for i in range(n):
    C2.append([C[i],i])

C2.sort()

ans = sum(C)-C2[-1][0]

T = [[] for i in range(n+1)]
for i in range(len(A)):
    T[A[i][0]].append(A[i][1])
    T[A[i][1]].append(A[i][0])

E = []
co = 0
while co < n-1:
    #print(co)
    t = 0
    while t < n+1 :
        if len(T[t]) == 1:
            E.append(t)
            if co == n-2 :
                E.append(T[t][0])
            T[T[t][0]].remove(t)
            T[t] = []
            co += 1
        t += 1



#print(E)

D = [0 for i in range(n)]
for i in range(n):
    D[E[i]-1] = C2[i][0]

print(ans)
s = ""
for i in range(n):
    s += str(D[i])
    s += " "

print(s)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ab = []
abn = [0]*N
abw = [[] for _ in range(N)]
for i in range(N-1):
  a,b = list(map(int,input().split()))
  ab.append([a,b])
  abw[a-1].append(b)
  abw[b-1].append(a)
  abn[a-1] += 1
  abn[b-1] += 1
c = sorted(list(map(int,input().split())))
cn = 0
d = [0]*N
s = [i for i in range(N)]
while cn <N:
  cut = []
  for i in s:
    if (abn[i] == 1 and cn<N) or len(s) == 1:
      d[i] = c[cn]
      cn += 1
      cut.append(i)
      abn[i] -=1
      s.remove(i)
  for j in cut:
    for k in abw[j]:
      abn[k-1] -= 1
print(sum(c)-max(c))
print(" ".join(map(str,d)))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

score = 0
c_zenbu = list(itertools.permutations(c))
for c in c_zenbu:
    ab_score = [min([c[(ab[i][0]-1)],c[(ab[i][1]-1)]]) for i in range(N-1)]
    s = sum(ab_score)
    if s > score:
        score = s
        ans_c = c
print(score)
[print(c[i],end=' ') for i in range(N)]

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
input = sys.stdin.readline
from array import array
def solve():
  n = int(input())
  query2 = []
  ans = array('I', [ 0 for i in range(n)])
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query2.append(a)
    query2.append(b)
    
  c = list(int(i) for i in input().split())
  c = sorted(c,reverse =True)
  
  d = collections.Counter(query2)
  
  nl = 0
  nr = 0
  for i in range(len(d)):
    ans[d.most_common()[i][0]-1] = c[i]
    
  print(sum(c) +(-1)*max(c))
  #dの処理
  print(*ans)
  
solve()

Submission status: Time Limit Exceeded

Solution code:
import copy

arc_ = []


N = int(input())

len_l = 2
# N = 2 
while len_l == 2:
    line = input().split()
    len_l = len(line)
    if len_l == 2:
        arc_.append([int(line[0]), int(line[1])])
    else:
        c_ = [int(v) for v in line]
        
max_value = 0
max_c = []

def get_result(arc, c_set):
    sum_v = 0
    for i in range(len(arc)):
        sum_v += min(c_set[arc[i][0]-1], c_set[arc[i][1]-1])
    return sum_v

def poi(ct, arc, c_set=[]):
    global max_value, max_c
    if len(ct) == 0:
        result = get_result(arc, c_set)
        if result > max_value:
            max_value = result
            max_c = c_set
    else:
        for i in range(len(ct)):
            c_set_tmp = copy.deepcopy(c_set)
            c_set_tmp.append(ct[i])
            ct_tmp = copy.deepcopy(ct)
            ct_tmp.remove(ct[i])
            poi(ct_tmp, arc, c_set_tmp)
            
poi(c_, arc_)

print(max_value)
print(' '.join([str(v) for v in max_c]))

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
input = sys.stdin.readline
from array import array
def solve():
  n = int(input())
  query = []
  query2 = []
  ans = array('I', [])
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query.append((a,b))
    query2.append(a)
    query2.append(b)
  c = list(int(i) for i in input().split())
  c = sorted(c,reverse =True)
  
  d = collections.Counter(query2)
  for i in range(len(d)):
    tmp = d.most_common()[i][0]
    #print(tmp)
    ans.insert(tmp-1,c[i])
  print(sum(c) +(-1)*max(c))
  #dの処理
  print(*ans)
  
solve()

Submission status: Time Limit Exceeded

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict
import math


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def gcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    ret = math.factorial(x)
    ret = ret // (math.factorial(x - y) * math.factorial(y))

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


###############################################################################


def main():
    n = intin()
    ablist = intinl(n - 1)
    clist = intina()

    clist.sort()
    cidx = 0

    ptocount = defaultdict(int)
    linklist = make_linklist(ablist)

    for a, b in ablist:
        ptocount[a] += 1
        ptocount[b] += 1

    ansdict = {}

    while True:
        ptocount_next = {}
        for p, count in ptocount.items():

            if count <= 1:
                for q in linklist[p]:
                    if q not in ansdict:
                        if q in ptocount_next:
                            ptocount_next[q] -= 1
                        else:
                            ptocount_next[q] = ptocount[q] - 1
                ansdict[p] = clist[cidx]
                cidx += 1
            else:
                if p not in ptocount_next:
                    ptocount_next[p] = count

        if cidx >= n:
            break
        ptocount = ptocount_next

    ans = 0
    for a, b in ablist:
        ans += min(ansdict[a], ansdict[b])

    anslist = []
    for i in range(1, n + 1):
        anslist.append(str(ansdict[i]))

    print(ans)
    print(' '.join(anslist))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

import itertools
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 v in 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

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

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
input = sys.stdin.readline

def solve():
  n = int(input())
  query = []
  query2 = []
  ans = []
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query.append((a,b))
    query2.append(a)
    query2.append(b)
  c = list(int(i) for i in input().split())
  c = sorted(c,reverse =True)
  
  d = collections.Counter(query2)
  for i in range(len(d)):
    tmp = d.most_common()[i][0]
    #print(tmp)
    ans.insert(tmp-1,c[i])
  print(sum(c) +(-1)*max(c))
  #dの処理
  print(*ans)
  
solve()

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
input = sys.stdin.readline

def solve():
  n = int(input())
  query = []
  query2 = []
  ans = [0]*n
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query.append((a,b))
    query2.append(a)
    query2.append(b)
  c = list(int(i) for i in input().split())
  c = sorted(c,reverse =True)
  d = collections.Counter(query2)
  for i in range(len(d)):
    tmp = d.most_common()[i][0]
    #print(tmp)
    ans[tmp-1] = c[i]
  print(sum(c) +(-1)*max(c))
  #dの処理
  print(*ans)
  
solve()

Submission status: Time Limit Exceeded

Solution code:
import collections

def solve():
  n = int(input())
  query = []
  query2 = []
  ans = [0]*n
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query.append((a,b))
    query2.append(a)
    query2.append(b)
  c = list(int(i) for i in input().split())
  c = sorted(c,reverse =True)
  d = collections.Counter(query2)
  for i in range(len(d)):
    tmp = d.most_common()[i][0]
    #print(tmp)
    ans[tmp-1] = c[i]
  print(sum(c) +(-1)*max(c))
  #dの処理
  print(*ans)
  
solve()

Submission status: Time Limit Exceeded

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict
import math


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def gcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    ret = math.factorial(x)
    ret = ret // (math.factorial(x - y) * math.factorial(y))

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


###############################################################################


def main():
    n = intin()
    ablist = intinl(n - 1)
    clist = intina()

    clist.sort()
    cidx = 0

    ptocount = defaultdict(int)
    linklist = make_linklist(ablist)

    for a, b in ablist:
        ptocount[a] += 1
        ptocount[b] += 1

    ansdict = {}

    while True:
        ptocount_next = deepcopy(ptocount)
        for p, count in ptocount.items():

            if count <= 1:
                for q in linklist[p]:
                    if q not in ansdict:
                        ptocount_next[q] -= 1
                ansdict[p] = clist[cidx]
                cidx += 1
                del ptocount_next[p]

        if cidx >= n:
            break
        ptocount = ptocount_next

    ans = 0
    for a, b in ablist:
        ans += min(ansdict[a], ansdict[b])

    anslist = []
    for i in range(1, n + 1):
        anslist.append(str(ansdict[i]))

    print(ans)
    print(' '.join(anslist))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
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.sort()
node = [0]*n
used = [False]*n

def dfs(cur,point):
    used[cur] = True
    for nx in G[cur]:
        if used[nx]: continue
        t = c.pop()
        node[nx] = t
        point += min(node[cur],node[nx])
        point = dfs(nx,point)
    return point
node[0] = c.pop()
# print(dfs(0,-1,0))
print(dfs(0,0))
print(*node)

Submission status: Accepted

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] = Cs[0]
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: Accepted

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])
idx = 1
ans = 0
allocation = [-1]*N
allocation[0] = Cs[0]
while Q:
    v = Q.pop()
    for nx in graph[v]:
        if allocation[nx]==-1:
            ans += Cs[idx]
            allocation[nx] = Cs[idx]
            Q.append(nx)
            idx += 1

print(ans)
print(*allocation)

Submission status: Accepted

Solution code:
import heapq
from collections import deque
n = int(input())
graph = [set() for _ in range(n)]

for _ in range(n - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    graph[a].add(b)
    graph[b].add(a)

nodes = [False for _ in range(n)]
values = list(map(lambda x: -int(x), input().split()))
print(-sum(values) + min(values))

heapq.heapify(values)
next_nodes = deque()
next_nodes.append(0)
while next_nodes:
    node = next_nodes.popleft()
    nodes[node] = -heapq.heappop(values)
    for g in graph[node]:
        if not (nodes[g]):
            next_nodes.append(g)

print(*nodes)

Submission status: Accepted

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)
index = 0


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


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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
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
            col[u] = C.pop()
            res += min(col[v], col[u])
            dfs(u, v)

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

    col = [0] * n
    col[0] = C.pop()
    dfs(0, -1)
    print(res)
    print(*col)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
import resource

sys.setrecursionlimit(20000)
n=int(input())
edges=[list(map(int,input().split())) for i in range(n-1)]
e = [[] for i in range(n)]
for a,b in edges:
  a-=1;b-=1
  e[a].append(b);e[b].append(a)
c=sorted(list(map(int,input().split())))
print(sum(c[:-1]))
visited=[False for i in range(n)]
node=[0]*n
cnt=0
def dfs(pos):
  global cnt,node,c
  if visited[pos]:return
  visited[pos]=True
  for p in e[pos]:
    dfs(p)
  node[pos]=c[cnt]
  cnt+=1
dfs(0)
print(' '.join(map(str,node)))

Submission status: Accepted

Solution code:
from collections import deque

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

l = [[] for _ in range(n)]
for a, b in ab:
    a, b = a-1, b-1
    l[a].append(b)
    l[b].append(a)
t = [-1]*n
q = deque([0])
w = [0]*n
w[0] = c.pop()
ans = 0
while q:
    v = q.pop()
    for i in l[v]:
        if i == t[v]:
            continue
        t[i] = v
        q.appendleft(i)
        w[i] = c.pop()
        ans += min(w[v], w[i])
print(ans)
print(*w)