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:
from collections import deque
N = int(input())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
C = sorted(list(map(int,input().split())))
A = [0 for _ in range(N+1)]
hist = [0 for _ in range(N+1)]
que = deque([1])
hist[1] = 1
cur = 0
while que:
    i = que.popleft()
    if len(G[i])==1:
        A[i] = C[cur]
        cur += 1
        hist[i] = 2
    flag = 2
    for j in G[i]:
        if hist[j]==0:
            que.append(j)
            hist[j] = 1
            flag = 1
        elif hist[j]==1:
          flag = 1
    if flag==2 and hist[i]==1:
        A[i] = C[cur]
        cur += 1
        hist[i] = 2
    elif hist[i]==1:
        que.append(i)
cnt = 0
hist = {(i,j):0 for i in range(1,N+1) for j in G[i]}
for i in range(1,N+1):
    for j in G[i]:
        if hist[(i,j)]==0:
            cnt += min(A[i],A[j])
            hist[(i,j)] = 1
            hist[(j,i)] = 1
print(cnt)
print(*A[1:])

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

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

m = sum(c_arr) - max(c_arr)
ans = [0]*(n + 1)
a,b = edge.pop()
ans[a] = c_arr.pop()
ans[b] = c_arr.pop()
uf = UnionFind(n)
uf.union(a,b)
while edge:
    for i in range(len(edge)):
        if uf.same_check(a,edge[i][0]):
            if not uf.same_check(a,edge[i][1]):
                ans[edge[i][1]] = c_arr.pop()
                uf.union(edge[i][0],edge[i][1])
                edge.pop(i)
                break
        elif uf.same_check(a,edge[i][1]):
            ans[edge[i][0]] = c_arr.pop()
            uf.union(edge[i][0],edge[i][1])
            edge.pop(i)
            break
print(m)
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
path = []
for _ in range(n - 1):
    a, b = map(int, input().split())
    path.append([a-1,b-1])
c = list(map(int, input().split()))
c.sort(reverse=True)

result = [-1 for _ in range(n)]
path.sort(key=lambda x: x[0] * 10 + x[1])
p = path.pop(0)
result[p[0]] = c[0]
result[p[1]] = c[1]
cx = 2
while cx < len(c):
    for p in path:
        if result[p[0]] > 0 and result[p[1]] < 0:
            result[p[1]] = c[cx]
            path.remove(p)
            break
        elif result[p[0]] < 0 and result[p[1]] > 0:
            result[p[0]] = c[cx]
            path.remove(p)
            break
    cx += 1
large = max(c)
c.remove(large)
print(sum(c))
print(' '.join([str(v) for v in result]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
path = []
for _ in range(n - 1):
    a, b = map(int, input().split())
    path.append([a-1,b-1])
c = list(map(int, input().split()))
c.sort(reverse=True)

result = [-1 for _ in range(n)]
p = path.pop()
result[p[0]] = c[0]
result[p[1]] = c[1]
cx = 2
while cx < len(c):
    for p in path:
        if result[p[0]] > 0 and result[p[1]] < 0:
            result[p[1]] = c[cx]
            path.remove(p)
            break
        elif result[p[0]] < 0 and result[p[1]] > 0:
            result[p[0]] = c[cx]
            path.remove(p)
            break
    cx += 1
large = max(c)
c.remove(large)
print(sum(c))
print(' '.join([str(v) for v in result]))

Submission status: Time Limit Exceeded

Solution code:
inpl = lambda: list(map(int,input().split()))
N = int(input())
partners = []
for i in range(N):
    partners.append(set())
for i in range(N-1):
    a, b = inpl()
    a -= 1
    b -= 1
    partners[a].add(b)
    partners[b].add(a)
C = sorted(inpl())

def goto_leaf(k):
    prev_k = None
    while len(partners[k]) > 1:
        nodes = list(partners[k])[:2]
        if nodes[0] != prev_k:
            k = nodes[0]
        else:
            k = nodes[1]
        prev_k = k
    return k

def delete_leaf(k):
    stem = list(partners[k])[0]
    partners[stem].remove(k)
    return stem

M = sum(C[:-1])
D = [0]*N
k = 0
for i in range(N-1):
    k = goto_leaf(k)
    D[k] = C[i]
    k = delete_leaf(k)
D[k] = C[N-1]

print(M)
print(' '.join(map(str,D)))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
dic = defaultdict(list)
for n in range(N - 1):
    a, b = map(int, input().split())
    dic[a].append(b)
    dic[b].append(a)
c_list = sorted(map(int, input().split()))
M = sum(c_list[:-1])
d_list = [False] * N
for i in range(N):
    if len(dic[i]) == 1:
        break
blank = N
q = [i]
while blank:
    i = q.pop(0)
    q += dic[i]
    if not d_list[i - 1]:
        d_list[i - 1] = c_list[blank - 1]
        blank -= 1
print(M)
print(' '.join(map(str, d_list)))

Submission status: Time Limit Exceeded

Solution code:
def compute(temp_list):
    sum = 0
    for i in range(N):
        for j in range(i):
           if edge_list[i][j] == 1:
               sum += min (c_list[temp_list[i]],c_list[temp_list[j]])
    return sum


def func(i:int, temp_list:list):
    global ans
    global ans_list
    global temp
    if i == N:
        temp = compute(temp_list)
        if temp>ans:#最大値ならば、結果を保存
            ans = temp
            ans_list = temp_list[:]#コピー作成
        return
    

    for j in range(N):
        if j not in temp_list:#再帰重複を防ぐ
            t = temp_list[:]
            t.append(j)
            func(i+1,t)


N = int(input())
#edge_list = [[0]*N]*N
edge_list = [[0 for i in range(N)] for j in range(N)]

for i in range(N-1):
    a , b  = input().split()
    a = int(a)
    b = int(b)
   # edge_list[a-1][b-1] = 1
    edge_list[b-1][a-1] = 1#辺の接続情報作成


c_list = list(map(int, input().split()))#値リストc1,c2,,,cn
temp_list = []#再帰途中のリストを構成
temp = 0
ans_list = []#答えのリスト
ans = 0
func(0,temp_list)


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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

e = [sorted(list(map(lambda x:int(x)-1,input().split()))) for i in range(N-1)]
e.sort()
c = list(map(int,input().split()))
c.sort()
c.reverse()
ans = sum(c)-c[0]
d = [0]*N
k = 0
d[0] = str(c[k])
k += 1
while e:
    a,b = e.pop(0)
    if d[a]==0 and d[b]!=0:
        d[a] = str(c[k])
        k+=1
    elif d[a]!=0 and d[b]==0:
        d[b] = str(c[k])
        k+=1
    else:
        e.append((a,b))
print(ans)
print(' '.join(d))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

e = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
c = list(map(int,input().split()))
c.sort()
c.reverse()
ans = sum(c)-c[0]
d = [0]*N
k = 0
d[0] = str(c[k])
k += 1
while e:
    a,b = e.pop(0)
    if d[a]==0 and d[b]!=0:
        d[a] = str(c[k])
        k+=1
    elif d[a]!=0 and d[b]==0:
        d[b] = str(c[k])
        k+=1
    else:
        e.append((a,b))
print(ans)
print(' '.join(d))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

e = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
c = list(map(int,input().split()))
c.sort()
c.reverse()
ans = sum(c)-c[0]
d = [0]*N
k = 0
d[0] = str(c[k])
k += 1
for _ in range(N-1):
    for i in range(N-1):
        a,b = e[i]
        if d[a]==0 and d[b]!=0:
            d[a] = str(c[k])
            k+=1
        elif d[a]!=0 and d[b]==0:
            d[b] = str(c[k])
            k+=1
print(ans)
print(' '.join(d))

Submission status: Time Limit Exceeded

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

N = int(input())
AB = []
for i in range(N-1):
  AB.append(list(map(int, input().split())))

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

Nodes = []
for i in range(N+1):
  Nodes.append(Node(i))
  for A,B in AB:
    if A == i:
      Nodes[i].child.append(B)

for Node in Nodes:
  if len(Node.child) >= 1:
    for child in Node.child:
      Nodes[child].depth = Node.depth + 1

Nodes.pop(0)

Nodes = sorted(Nodes, key=lambda x: x.depth)
for Node in Nodes:
  Node.number = max(c)
  c.pop(c.index(max(c)))

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

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

print(ans)

for Node in Nodes:
  print(Node.number,end = " ")

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    N = int(input())
    sides = []
    for x in range(N - 1):
        sides.append([ int(x) for x in input().split() ])
    cn = [ int(x) for x in input().split() ]

    max_sum = 0
    max_cn = []
    for temp_cn in itertools.permutations(cn):
        sum = 0
        for aibi in sides:
            sum += min(temp_cn[aibi[0] - 1], temp_cn[aibi[1] - 1])
        if sum > max_sum:
            max_sum = sum
            max_cn = temp_cn

    print(max_sum)
    print(" ".join(map(str, max_cn)))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
edge=[]
adj=[[] for _ in range(n)]
pri=[0]*n
count = [[0, i] for i in range(n)]
ans=[0]*n
for _ in range(n-1):
  ai, bi = map(int, input().split())
  edge.append([ai-1, bi-1])
  adj[ai-1].append(bi-1)  
  adj[bi-1].append(ai-1)  
  count[ai-1][0]+=1
  count[bi-1][0]+=1
c = sorted(list(map(int, input().split())), reverse=True)

count.sort(key=lambda x: x[0], reverse=True)
for cnti, ci in zip(count, c):
  if list(map(lambda x: x[0], count)).count(cnti)>1:
    swap(count, cnti, pri)
  ans[cnti[1]]=ci
  for a in adj[cnti[1]]:
    pri[a]=1
m=0
for e in edge:
  m+=min(ans[e[0]], ans[e[1]])
print(m)
res=""
for a in ans:
  res+=str(a) + " "
print(res)

def swap(lst, cnt, pri):
  l = lst.index(cnt)
  r = l + lst.count(cnt)//2
  for i in range(l,r):
    if pri[i]==0:
      lst[l+i], lst[r-i] = lst[r+i], lst[l-i]

Submission status: Time Limit Exceeded

Solution code:
import copy

N=int(input())
final=[[0]*2 for _ in range(N-1)]
counter=[0]*N
ans=[0]*N
for n in range(N-1):
    A=list(map(int,input().split()))
    final[n][0]=A[0]
    final[n][1]=A[1]
    mae=A[0]
    ato=A[1]
    counter[mae-1]=counter[mae-1]+1
    counter[ato-1]=counter[ato-1]+1
c=list(map(int,input().split()))
ccc=copy.copy(c)
for n in range(N):
    ans[counter.index(max(counter))]=max(c)
    counter[counter.index(max(counter))]=0
    c[c.index(max(c))]=0
kotae=0
for n in range(N-1):
    kotae=kotae+min(ccc[final[n][0]-1],ccc[final[n][1]-1])
print(kotae)
answer=''
for n in range(N-1):
    answer=answer+str(ans[n])+' '
answer=answer+str(ans[N-1])
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import collections
import copy

N = int(input())
ab = []
for i in range(N-1):
    ab.append(tuple([int(x) for x in input().split(' ')]))

oriab = copy.deepcopy(ab)

c = [int(x) for x in input().split(' ')]
c.sort(reverse=True)
d = [0] * N

def next(ab, c, skip=None):
    while len(ab)>0:
        a, b = zip(*ab)
        count = collections.Counter(a + b)
        if skip is not None:
            del count[skip]
        count = list(count.items())
        count.sort(key=lambda x: x[1], reverse=True)
        while len(count)>0:
            x, y = count.pop(0)
            if d[x-1] == 0:
                d[x-1] = c.pop(0)
                break
        abex = [ab_ for ab_ in ab if x in ab_]
        if len(count) == 0:
            break
        elif len(count) == 1:
            x, y = count.pop(0)
            d[x-1] = c.pop(0)
            break
        next(abex, c, x)
        ab = [ab_ for ab_ in ab if x not in ab_]

next(ab, c)

ans = sum([min(d[a-1], d[b-1]) for a, b in oriab])
print(ans)
print(' '.join(['%i']*len(d)) % tuple(d))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
n = int(input())

edges=[[] for i in range(n+1)]
d=[-1 for i in range(n+1)]
for i in range(1,n):
	a, b=[int(i) for i in input().split()]
	edges[a].append([b,1])
	edges[b].append([a,1])
def kyori(u):
	for v,w in edges[u]:
		if d[v]==-1:
			d[v]=d[u]+w
			kyori(v)

d[1]=0
kyori(1)

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

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

ans_lst[0] = D[0]
now_kyori = 1
idx = 1
m = 1
while m < n:
    for i in range(2, n+1):
        if d[i] == now_kyori:
            ans_lst[i-1] = D[idx]
            idx += 1
            m += 1
    now_kyori += 1


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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush
import sys

input = sys.stdin.readline

N = int(input())
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)
    es[b].append(a)

h = [len(es[i]) for i in range(N)]
# 次数

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

v = [-1] * N
cur = 0

t = [(e, i) for i, e in enumerate(h, 0)]
heapify(t)
while t:
    g, i = heappop(t)
    # print(h, (g, i), v)
    if g > 1:
        heappush(t, (h[i], i))
    elif g == 1:
        v[i] = c[cur]
        h[i] -= 1
        for nv in es[i]:
            h[nv] -= 1
        cur += 1
# print(h, (g, i), v)
ans = sum(c) - c[-1]
print(ans)
v = [vv if vv != -1 else c[-1] for vv in v]
print(' '.join(map(str, v)))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush
 
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):
    a, b= (int(i) for i in input().split()) 
    heappush(list[a-1],b)
    heappush(list[b-1],a)
 
count=1
 
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]==[]:
            if 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)
print(sum(kouho[:n-1]))
for i in range(n-1):
    print(kouho[kazulist[i]-1], end=" ")
print(kouho[kazulist[n-1]-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = int(input())
a = []
for i in range(n-1):
    a.append(input().split())
d = list(map(int,input().split()))
D = list(itertools.permutations(d))

ans = 0
True_d = []
for i in D:
    sco = 0
    for j in range(n-1):
        sco += min(i[int(a[j][0])-1], i[int(a[j][1])-1])
    if ans < sco:
        ans = sco
        True_d = []
        True_d.extend(i)
        if ans ==  sum(i) - max(i):
            break
print(ans)
map_ans_2 = map(str,True_d)
ans_2 = ' '.join(map_ans_2)
print(ans_2)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush
 
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):
    a, b= (int(i) for i in input().split()) 
    heappush(list[a-1],b)
    heappush(list[b-1],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]==[]:
            if 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):
    print(kouho[kazulist[i]-1], end=" ")
text+=str(kouho[kazulist[n-1]-1])
print(text)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
AB = []
for _ in range(N-1):
    a, b = map(int, input().split())
    AB.append((a, b))
C = list(map(int, input().split()))
    
  
import queue
node_vals = C[:]

edges = [[0] * (N) for _ in range(N)]
for a, b in AB:
    edges[a-1][b-1] = 1
    edges[b-1][a-1] = 1



q = queue.Queue()
q.put(([], node_vals[:], 0))


ans = 0
while not q.empty():
    selected, rest, score = q.get()
    #print(selected, rest, score)
    if len(rest) == 0 and ans < score:
        ans = score
        ans_list = selected
    
    for i, v in enumerate(rest):
        add_score = 0
        for j, v2 in enumerate(selected):
            if edges[len(selected)][j] == 1:
                #print(selected, i,j)
                add_score += min(v2, v)
        q.put((selected[:]+[v], rest[:i] + rest[i+1:], add_score+score))
        
print(ans)
print(' '.join(map(str, ans_list)))

Submission status: Time Limit Exceeded

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

# naive
import itertools
max_val = 0
max_v = 0
for it in itertools.permutations(c):
    v_val = [0] + list(it)
    val = calcCost(D, v_val)
    if val > max_val:
        max_val = val
        max_v = v_val
print(max_val)
print(' '.join(map(str, max_v[1:])))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = int(input())
a = []
for i in range(n-1):
    a.append(input().split())
d = list(map(int,input().split()))
D = list(itertools.permutations(d))

ans = 0
True_d = []
for i in D:
    sco = 0
    for j in range(n-1):
        sco += min(i[int(a[j][0])-1], i[int(a[j][1])-1])
    if ans < sco:
        ans = sco
        True_d.extend(i)
print(ans)
map_ans_2 = map(str,True_d)
ans_2 = ' '.join(map_ans_2)
print(ans_2)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush

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])
    heappush(list[a-1],b)
    heappush(list[b-1],a)


count=1
switch=0
 
nagasa=len(list)
 
while count<=n:
    newkoho=[]
    if switch==0:
        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
            else:
                koho.append(e)
        switch=1
    
    else:
        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):
    print(kouho[kazulist[i]-1], end=" ")
text+=str(kouho[kazulist[n-1]-1])
print(text)

Submission status: Time Limit Exceeded

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()))
    lr_list = []
    return n, a_list, b_list, c_list


def solve(n, a_list, b_list, c_list):
    total = 0
    c_list = sorted(c_list, reverse=True) # Because maximum number is not selected at all.
    import itertools
    current_max = 0
    current_list = []

    c_list_new = [c_list[item-1] for item in set(a_list + b_list)]
    for new_list in itertools.permutations(c_list_new, n):
        total = 0
        for i in range(n - 1):
            total += min(new_list[a_list[i]-1], new_list[b_list[i]-1])
        if total >= current_max:
            current_max = total
            current_list = new_list

    return str(current_max) + "\n" + " ".join(map(str, current_list))


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

Solution code:
import copy
import queue


def read():
    N = int(input().strip())
    edge = [-1 for _ in range(N+1)]
    for i in range(1, N+1):
        edge[i] = list()
    for _ in range(N-1):
        a, b = list(map(int, input().strip().split()))
        edge[a].append(b)
        edge[b].append(a)
    C = list(map(int, input().strip().split()))
    return N, edge, C


def center_of_tree(N, edge):
    # 端点を削除していく。最後に残ったものが中心。
    n = N
    previous_parent = -1
    e = copy.deepcopy(edge)
    while n > 1:
        for child in range(1, N+1):
            if len(e[child]) == 1:
                parent = e[child][0]
                e[parent].remove(child)
                e[child].remove(parent)
                n -= 1
                previous_parent = parent
    return previous_parent


def write_node_weights(N, parent, edge, C):
    C = list(sorted(C))
    node_weight = [-1 for _ in range(N+1)]
    node_weight[parent] = C.pop()
    q = queue.Queue()
    q.put(parent)
    while len(C) > 0:
        parent = q.get()
        for child in edge[parent]:
            if node_weight[child] == -1:
                node_weight[child] = C.pop()
                q.put(child)
    return node_weight


def sum_of_edge_weights(N, node_weight, edge):
    sum_of_edge_weights = 0
    for a in range(1, N+1):
        for b in edge[a]:
            if a < b:
                sum_of_edge_weights += min(node_weight[a], node_weight[b])
    return sum_of_edge_weights


def solve(N, edge, C):
    center = center_of_tree(N, edge)
    node_weight = write_node_weights(N, center, edge, C)
    edge_weights = sum_of_edge_weights(N, node_weight, edge)
    return edge_weights, node_weight[1:]


if __name__ == '__main__':
    inputs = read()
    edge_weights, node_weight = solve(*inputs)
    print(edge_weights)
    print(' '.join(map(str, node_weight)))

Submission status: Time Limit Exceeded

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 = 0
for i in range(N-1):
  s += min(T[A[i]-1], T[B[i]-1])
print(s)
print(*T)

Submission status: Time Limit Exceeded

Solution code:
import copy
import queue


def read():
    N = int(input().strip())
    edge = dict()
    for i in range(1, N+1):
        edge[i] = list()
    for _ in range(N-1):
        a, b = list(map(int, input().strip().split()))
        edge[a].append(b)
        edge[b].append(a)
    C = list(map(int, input().strip().split()))
    return N, edge, C


def center_of_tree(N, edge):
    # 端点を削除していく。最後に残ったものが中心。
    n = N
    previous_parent = -1
    e = copy.deepcopy(edge)
    while n > 1:
        for child in range(1, N+1):
            if len(e[child]) == 1:
                parent = e[child][0]
                e[parent].remove(child)
                e[child].remove(parent)
                n -= 1
                previous_parent = parent
    return previous_parent


def write_node_weights(N, parent, edge, C):
    C = list(sorted(C))
    node_weight = [-1 for _ in range(N+1)]
    node_weight[parent] = C.pop()
    q = queue.Queue()
    q.put(parent)
    while len(C) > 0:
        parent = q.get()
        for child in edge[parent]:
            if node_weight[child] == -1:
                node_weight[child] = C.pop()
                q.put(child)
    return node_weight


def sum_of_edge_weights(N, node_weight, edge):
    sum_of_edge_weights = 0
    for a in range(1, N+1):
        for b in edge[a]:
            if a < b:
                sum_of_edge_weights += min(node_weight[a], node_weight[b])
    return sum_of_edge_weights


def solve(N, edge, C):
    center = center_of_tree(N, edge)
    node_weight = write_node_weights(N, center, edge, C)
    edge_weights = sum_of_edge_weights(N, node_weight, edge)
    return edge_weights, node_weight[1:]


if __name__ == '__main__':
    inputs = read()
    edge_weights, node_weight = solve(*inputs)
    print(edge_weights)
    print(' '.join(map(str, node_weight)))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush

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])
    heappush(list[a-1],b)
    heappush(list[b-1],a)
    #list[a-1].heappush(b)
    #list[b-1].heappush(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):
    print(kouho[kazulist[i]-1], end=" ")
text+=str(kouho[kazulist[n-1]-1])
print(text)

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):
    print(kouho[kazulist[i]-1], end=" ")
text+=str(kouho[kazulist[n-1]-1])
print(text)

Submission status: Time Limit Exceeded

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

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
switch=0
nagasa=len(list)

while count<=n:
    newkoho=[]
    if switch==0:
        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
        switch=1
    else:
        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):
    print(kouho[kazulist[i]-1], end=" ")
text+=str(kouho[kazulist[n-1]-1])
print(text)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())
ab_ls = []
count = 0
while count < n-1:
    ab_ls.append(list(map(int, input().split())))
    count = count + 1
c_ls = list(map(int, input().split()))
hoge = []
for i in itertools.permutations(c_ls):
    min_sum = 0
    for ab in ab_ls:
        min_sum = min_sum + min(i[ab[0]-1],i[ab[1]-1])
    hoge.append([min_sum, i])
hoge.sort(key=lambda x: -x[0])
print(hoge[0][0])
print((str(hoge[0][1])).strip('()').replace(',', ' '))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
G = np.zeros((N,N),dtype = np.bool)

pairs = []

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

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


links = [0 for i in range(N)]

for i in range(N):
    links[i] = G[i,:].sum()

nodeval = np.array([0 for i in range(N)])

# print(links)

disabled = [False for i in range(N)]
while len(Cs) > 0:
    mx = 0
    for i,l in enumerate(links):
        if not disabled[i]:
            mx = max(l,mx)
    # print("mx",mx, "da", disabled)
    for i,l in enumerate(links):
        if not disabled[i] and l == mx:
            break
    disabled[i] = True
    # max connected node
    # print(i)
    nodeval[i] = Cs.pop(-1)

# print(nodeval)

sumval = 0
for p in pairs:
    sumval += min(nodeval[p[0]-1], nodeval[p[1]-1] )

print(sumval)
for i,l in enumerate(nodeval):
    print(l,end=" " if i!=N-1 else "\n")