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:
import sys
input = sys.stdin.readline
N = int(input())
if N == 1:
    for i in range(N-1):
        ai,bi = map(int,input().split())
    c = list(map(int,input().split()))
    print(100)
    print(100)
node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

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

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

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

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

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

dfs(neigh,nn,visited)
#ans2 = ' '.join([str(ans[i]) for i in range(N)])
ans2 = str(ans[0])
for i in range(1,N):
    ans2 = ans2+' '+str(ans[i])
print(sum(c)-max(c))
print(ans2)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

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

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
if N == 1:
    print(100)
    print(100)
    exit()
node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

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

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

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

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

Submission status: Runtime Error

Solution code:

 
def main():
    n = int(input())
    e = [[map(int,input().split()),] for x in range(n-1)]
    c = [int(x) for x in input().split()]    
 
    c.sort(reverse=True)

    # c = [c0, c1, c2,..](c0 > c1 > ..)
 
    # 各nodeと繋がっているnodeリスト
    edge = {(i+1):[] for i in range(n)}
    for a,b in e:
        edge[a].append(b)
        edge[b].append(a)
 
    # 頂点に重みをつける
    node = [0]*n
    root = 1
 
    # 頂点1の場所には最も大きな数を置く
    node[0] = c[0]

    # yet=頂点1の枝リスト
    yet = edge[1]
    consume = 1
 
    while consume < n:
        # x=頂点1と繋がっている頂点
        x = yet[consume-1]

        # 頂点1と繋がっている頂点から順に大きい数で埋めていく
        node[x-1] = c[consume]
        consume += 1

    print(sum(c[1:]))
    print(*node)
 
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
node = [0 for i in range(N)]

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

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

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

Submission status: Runtime Error

Solution code:


# https://atcoder.jp/contests/m-solutions2019/submissions/5738704


from collections import deque, heapq

n = int(input())

g = [{"num":0,"neighber":[]} for _ in range(n+1) ]

for _ in range(n-1):

    a, b = map(int, input().split())

    g[a]["neighber"].append(b)
    g[b]["neighber"].append(a)


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

# sum(c[:-1]) 
print( sum(c) - c[-1] )


i = 0
s = [(0,1)]

while i < len(s):
    
    pre, cur = s[i]
    i += 1

    g[cur]["num"] = c.pop()

    for e in g[cur]["neighber"]:
        if e == pre:
            continue

        s.append((cur,e))

print(" ".join(str(g[i]["num"])) for i in range(1,n+1))

Submission status: Runtime Error

Solution code:
from collections import*
n=int(input())
d=defaultdict(list)

start=float("inf")
for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
    start=min(a,start)
p=sorted(map(int,input().split()))

def DFS(point,TFlist):
    global ans
    global score
    if all(TFlist):
        return 1
    for i in d[point]:
        if TFlist[i-1]:
            continue
        TFlist[i-1]=True
        tmp=p.pop()
        ans[i-1]=tmp
        score.append(tmp)
        #print(score)
        DFS(i,TFlist)
        TFlist[i-1]=False
    return score,ans

TFlist=[False]*(n)
TFlist[start-1]=True
ans=[0 for i in range(n)]
score=[]
ans[start-1]=p.pop()
s,t=DFS(start,TFlist)
#print(d)
print(sum(s))
print(*t)

Submission status: Runtime Error

Solution code:
n = int(input())

d = {}
br = []
sum_ = 0
res = ""

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

    try:
        d[a] += 1
    except:
        d[a] = 1

    try:
        d[b] += 1
    except:
        d[b] = 1

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

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

for ind,i in enumerate(c):
    d[ind] = (d[ind][0], i)

d = sorted(d)

# print(br)
# print(d)

# for i,j in br:
#     # print(i,j)
#     if d[i-1][1] < d[j-1][1]:
#         sum += d[i-1][1]
#     else:
#         sum += d[j-1][1]

for c in 

for i,j in d:
    res += str(j) + " "

print(sum(c[:-1]))
print(res)

Submission status: Runtime Error

Solution code:
from collections import*
n=int(input())
d=defaultdict(list)

start=float("inf")
for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    b[a].append(a)
    start=min(a,start)
p=sorted(map(int,input().split()))

def DFS(point,TFlist):
    global ans
    global score
    if all(TFlist):
        return 1
    for i in d[point]:
        if TFlist[i-1]:
            continue
        TFlist[i-1]=True
        tmp=p.pop()
        ans[i-1]=tmp
        score.append(tmp)
        #print(score)
        DFS(i,TFlist)
        TFlist[i-1]=False
    return score,ans

TFlist=[False]*(n)
TFlist[start-1]=True
ans=[0 for i in range(n)]
score=[]
ans[start-1]=p.pop()
s,t=DFS(start,TFlist)
#print(d)
print(sum(s))
print(*t)

Submission status: Runtime Error

Solution code:
import sys
from heapq import heappush, heappop
sys.setrecursionlimit(10**6)

n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)
num = [0 for _ in range(n)]
c = list(map(int, input().split()))
h = []
for i in range(n):
	heappush(h, -c[i])

def dfs(x):
	global h
	for v in adj[x]:
		if num[v] != 0:
			continue
		num[v] = -heappop(h)
		dfs(v)
	return

num[0] = -heappop(h)
dfs(0, -1)
print(sum(c) - max(c))
print(*num)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)
num = [0 for _ in range(n)]
c = list(map(int, input().split()))
h = []
for i in range(n):
	heappush(h, -c[i])

def dfs(x, par):
	global h
	for v in adj[x]:
		if num[v] != 0:
			continue
		num[v] = -heappop(h)
		dfs(v, x)
	return

num[0] = -heappop(h)
dfs(0, -1)
print(sum(c) - max(c))
print(*num)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from sys import setrecursionlimit, getrecursionlimit

setrecursionlimit(10*getrecursionlimit())

N = int(input())
g = defaultdict(list)
K = []
for i in range(N-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
    K.append((a,b))

C = sorted([int(i) for i in input().split()], reverse=True)

a = {i:0 for i in range(1, N+1)}

visited = defaultdict(bool)
ct = 0
def dfs(v):
    global ct
    visited[v] = True
    a[v] = C[ct]
    ct += 1
    for c in g[v]:
        if not visited[c]:
            dfs(c)

dfs(1)

ans1 = 0
ans2 = ' '.join([str(b) for b in a.values()])
for b, c in K:
    ans1 += min(a[b], a[c])

print(ans1)
print(ans2)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

N = int(input())
g = defaultdict(list)
K = []
for i in range(N-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
    K.append((a,b))

C = sorted([int(i) for i in input().split()], reverse=True)

a = {i:0 for i in range(1, N+1)}

visited = defaultdict(bool)
ct = 0
def dfs(v):
    global ct
    visited[v] = True
    a[v] = C[ct]
    ct += 1
    for c in g[v]:
        if not visited[c]:
            dfs(c)

dfs(1)

ans1 = 0
ans2 = ' '.join([str(b) for b in a.values()])
for b, c in K:
    ans1 += min(a[b], a[c])

print(ans1)
print(ans2)

Submission status: Runtime Error

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

if N == 1:
    print(0)
    print(c[0])
    exit()

c.sort(reverse = True)
edge = [[] for _ in range(N)]
for a, b in ab:
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v, p):
    global ans
    global count
    if p != -1:
        anse[v] = c[count+1]
        ans += min(anse[v], anse[p])
        count += 1
    for nv in edge[v]:
        if nv == p:
            continue
        dfs(nv, v)

#search = [i for i, e in enumerate(edge) if len(e) == 1]
search = [0]
res = 0
rese = [None for _ in range(N)]
for i in search:
    count = 0
    ans = 0
    anse = [None for _ in range(N)]
    anse[i] = c[0]
    dfs(i, -1)
    if res < ans:
        res = ans
        rese = anse
print(res)
print(" ".join(map(str, rese)))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
node = [0 for i in range(N)]

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

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

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

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)
num = [0 for _ in range(n)]
c = list(map(int, input().split()))
h = []
for i in range(n):
	heappush(h, -c[i])

def dfs(x, par):
	global h
	for v in adj[x]:
		if v == par:
			continue
		num[v] = -heappop(h)
		dfs(v, x)
	return

num[0] = -heappop(h)
dfs(0, -1)
print(sum(c) - max(c))
print(*num)

Submission status: Runtime Error

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

if N == 1:
    print(0)
    print(c[0])
    exit()

c.sort(reverse = True)
edge = [[] for _ in range(N)]
for a, b in ab:
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v, p):
    global ans
    global count
    if p != -1:
        anse[v] = c[count+1]
        ans += min(anse[v], anse[p])
        count += 1
    for nv in edge[v]:
        if nv == p:
            continue
        dfs(nv, v)

#search = [i for i, e in enumerate(edge) if len(e) == 1]
search = [0]
res = 0
rese = [None for _ in range(N)]
for i in search:
    count = 0
    ans = 0
    anse = [None for _ in range(N)]
    anse[i] = c[0]
    dfs(i, -1)
    if res < ans:
        res = ans
        rese = anse
print(res)
print(" ".join(map(str, rese)))

Submission status: Runtime Error

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

if N == 1:
    print(0)
    print(c[0])
    exit()

c.sort(reverse = True)
edge = [[] for _ in range(N)]
for a, b in ab:
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v, p):
    global ans
    global count
    if p != -1:
        anse[v] = c[count+1]
        ans += min(anse[v], anse[p])
        count += 1
    for nv in edge[v]:
        if nv == p:
            continue
        dfs(nv, v)

#search = [i for i, e in enumerate(edge) if len(e) == 1]
search = [0]
res = 0
rese = [None for _ in range(N)]
for i in search:
    count = 0
    ans = 0
    anse = [None for _ in range(N)]
    anse[i] = c[0]
    dfs(i, -1)
    if res < ans:
        res = ans
        rese = anse
print(res)
print(" ".join(map(str, rese)))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
node = [0 for i in range(N)]

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

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
node = [0 for i in range(N)]

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

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
class Node():
    def __init__(self, id):
        self.id = id
        self.children = []
        self.value = None

    def add_child(self, node):
        self.children.append(node)



def write(q, values):
    if len(values) == 0:
        return

    node = q.pop(0)
    node.value = values.pop()
    q.extend(node.children)
    write(q, values)

n = int(input())

t = [Node(i) for i in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    parent = min(a, b)
    child = max(a, b)
    t[parent].add_child(t[child])

c = list(map(int, input().split()))
_c = sorted(c)
write([t[0]], _c)

out = [node.value for node in t]

print(sum(c) - max(c))
print(" ".join(list(map(str, out))))

Submission status: Runtime Error

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

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

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

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

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

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

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

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

ans = 0
ans_list = []

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

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

Submission status: Runtime Error

Solution code:
N = int(input())
ab = [list(map(int, input().split())) for _ in range(max(1, N-1))]
c = list(map(int, input().split()))
c.sort(reverse = True)
edge = [[] for _ in range(N)]
for a, b in ab:
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
if N == 1:
    print(c[0])
    exit()

def dfs(v, p):
    global ans
    global count
    if p != -1:
        anse[v] = c[count+1]
        ans += min(anse[v], anse[p])
        count += 1
    for nv in edge[v]:
        if nv == p:
            continue
        dfs(nv, v)

#search = [i for i, e in enumerate(edge) if len(e) == 1]
search = [0]
res = 0
rese = [None for _ in range(N)]
for i in search:
    count = 0
    ans = 0
    anse = [None for _ in range(N)]
    anse[i] = c[0]
    dfs(i, -1)
    if res < ans:
        res = ans
        rese = anse
print(res)
print(" ".join(map(str, rese)))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
node = [[0,i] for i in range(N)]
ab = []
neigh = [[0 for i in range(N)] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1
def dfs(neighbor,start,visited,c):
    global k
    if sum(visited) == N:
        return ans
    for i in range(N):
        if visited[i] == 0 and neighbor[start][i] == 1:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            dfs(neighbor,i,visited,c)

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1][0] += 1
    node[bi-1][0] += 1
    neigh[ai-1][bi-1] = 1
    neigh[bi-1][ai-1] = 1
    ab.append([ai-1,bi-1])
c = list(map(int,input().split()))
c.sort(reverse=True)
node.sort(key=lambda x:x[0],reverse=True)
m = max([node[i][0] for i in range(N)])
max_node = [node[i][1] for i in range(N) if node[i][0] == m]

nn = max_node[0]
can = 0
visited[nn] = 1
ans[nn] = max(c)

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

Submission status: Runtime Error

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

c = sorted(list(map(int,input().split())))
vcost = [-1]*(N+1)
vcost[1]=c.pop()
ans = 0
def dfs(i):
    global ans
    for j in D[i]:
        if vcost[j]==-1:
            vcost[j]=c.pop()
            ans += vcost[j]
            dfs(j)
dfs(1)
print(ans)
print(*vcost[1:])

Submission status: Runtime Error

Solution code:
N = int(input())
node = [[0,i] for i in range(N)]
ab = []
neigh = [[0 for i in range(N)] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
def dfs(neighbor,start,visited,k,c):
    if sum(visited) == N:
        return ans
    for i in range(N):
        if visited[i] == 0 and neighbor[start][i] == 1:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            dfs(neighbor,i,visited,k,c)

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1][0] += 1
    node[bi-1][0] += 1
    neigh[ai-1][bi-1] = 1
    neigh[bi-1][ai-1] = 1
    ab.append([ai-1,bi-1])
c = list(map(int,input().split()))
c.sort(reverse=True)
node.sort(key=lambda x:x[0],reverse=True)
m = max([node[i][0] for i in range(N)])
max_node = [node[i][1] for i in range(N) if node[i][0] == m]

nn = max_node[0]
can = 0
visited[nn] = 1
ans[nn] = max(c)
dfs(neigh,nn,visited,1,c)



ans2 = ' '.join([str(ans[i]) for i in range(N)])


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

print(ans2)

Submission status: Runtime Error

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

def dfs(v, p):
    global ans
    global count
    if p != -1:
        anse[v] = c[count+1]
        ans += min(anse[v], anse[p])
        count += 1
    for nv in edge[v]:
        if nv == p:
            continue
        dfs(nv, v)

#search = [i for i, e in enumerate(edge) if len(e) == 1]
search = [0]
res = 0
rese = [None for _ in range(N)]
for i in search:
    count = 0
    ans = 0
    anse = [None for _ in range(N)]
    anse[i] = c[0]
    dfs(i, -1)
    if res < ans:
        res = ans
        rese = anse
print(res)
print(" ".join(map(str, rese)))

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):
    try:
        tmp_lst = tree_dic[current_node][:]
    except:
        pass

    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:   #   次のノードにつながっている辺があるとき
#            try: 
            ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)

#            except:
#                pass

    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:
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]#   探索し終えたノードの削除

        try:

            else:   #   次のノードにつながっている辺があるとき
                ans = search_next_node_and_add_side_wate(tree_dic, ans, next_node, c_lst, ans_lst)
 
 
        except:
            return ans

    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-1)
b = [0]*(n-1)
for i in range(n-1):
    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], reverse=True)

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

        try:
            if len(tree_dic[current_node]) == 0:
                del tree_dic[current_node]#   探索し終えたノードの削除
            if len(tree_dic[next_node]) == 0:
                del tree_dic[next_node]#   探索し終えたノードの削除
        except:
            return ans


        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)