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:
n = int(input())
tree = [[] for _i in range(n)]
for _i in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
from collections import deque
c = deque(sorted(list(map(int, input().split())), reverse=True))
visit = [-1 for _i in range(n)]

def solve(p):
    for i in tree[p]:
        if visit[i] < 0:
            visit[i] = c.popleft()
            solve(i)
solve(0)
print(*visit)

Submission status: Runtime Error

Solution code:
N=int(input())
G=[[]for _ in range(N)]

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

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

cnt=[[0,i] for i in range(N)]

for i in range(N):
    cnt[i][0]=len(G[i])

cnt.sort(reverse=True)
c.sort(reverse=True)

l=[-1 for _ in range(N)]
for i in range(N):
    num=cnt[i][1]
    l[num]=c[i]
#print(l)
ans=0
chk=[[0 for i in range(N)] for _ in range(N)]

def bfs(v,p,chk):
    global ans
    if chk[v][p]==1:
        return
    chk[v][p]=1
    chk[p][v]=1
    ans+=min(l[v],l[p])
    for tmp in G[v]:
        bfs(tmp,v,chk)

for v in range(N):
    bfs(v,G[v][0],chk)

print(ans)
print(*l)

Submission status: Runtime Error

Solution code:
n=int(input())
ab=[[]for _ in range(n)]
for _ in range(n-1):
	a,b=map(int,input().split())
	ab[a-1].append(b-1)
	ab[b-1].append(a-1)
c=list(map(int,input().split()))
c.sort()
print(sum(c)-c[-1])
ans=[-1]*n
cnt=0
node=[]
visited=[0]*n
ans=[-1]*n
def dfs(x):
	global cnt
	ans[x]=c[-cnt-1]
	visited[x]=1
	for next in ab[x]:
		if visited[next]==0:
			cnt+=1
			dfs(next)
dfs(0)
print(*ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A=[[]for i in range(N)]
X=[list(map(int, input().split())) for _ in range(N-1)]
for i in range(N-1):
  a=X[i][0]
  b=X[i][1]
  a-=1
  b-=1
  A[a].append(b)
  A[b].append(a)
D=list(map(int, input().split()))
D=sorted(D)[::-1]
from collections import deque
d=deque(D)
E=[-1]*N
def f(now,pre):
  for i in A[now]:
    if i!=pre and E[i]==-1:
      E[i]=d.popleft()
      f(i,now)
E[0]=d.popleft()
f(0,0)
print(sum(D[1:]))
print(*E)

Submission status: Runtime Error

Solution code:
from collections import Counter

N = int(input())
edges = [[] for _ in range(N)]

for _ in range(N - 1):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edges[to].append(fr)

C = Counter(map(int, input().split()))

def dfs(now, pr, prev):
    ret = 0
    for to in edges:
        if to == pr:
            continue
        for c, n in C.items():
            if n == 0:
                continue
            C[c] -= 1
            ret = max(ret, dfs(to, now, c) + min(prev, c))
            C[c] += 1
    return ret

print(dfs(0, -1, 0))

Submission status: Runtime Error

Solution code:
N = int(input())
visited = [False] * N
edges = [[] for _ in range(N)]
AB = []
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    AB.append((a, b))
    edges[a].append(b)
    edges[b].append(a)
C = list(map(int, input().split()))
C.sort(reverse=True)
scores = [-1] * N
i = 0

def dfs(v):
    if visited[v]:
        return

    visited[v] = True
    global i
    scores[v] = C[i]
    i += 1
    for e in edges[v]:
        if visited[e]:
            continue

        dfs(e)

dfs(0)

total = sum(C) - C[0]
print(total)
print(*scores)

Submission status: Runtime Error

Solution code:
N = int(input())
visited = [False] * N
edges = [[] for _ in range(N)]
AB = []
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    AB.append((a, b))
    edges[a].append(b)
    edges[b].append(a)
C = list(map(int, input().split()))
C.sort(reverse=True)
scores = [-1] * N
i = 0

def dfs(v):
    if visited[v]:
        return

    visited[v] = True
    global i
    scores[i] = C[i]
    i += 1
    for e in edges[v]:
        if visited[e]:
            continue

        dfs(e)

dfs(0)

total = 0
for a, b in AB:
    total += min(scores[a], scores[b])
print(total)
print(*scores)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
N, *L = map(int, open('0').read().split())
dic = [[] for i in range(N)]
ans = [-1]*N
cnt = [0]*N
hq = []
for a,b in zip(*[iter(L[:2*(N-1)])]*2):
  a -= 1
  b -= 1
  dic[a] += [b]
  dic[b] += [a]
  cnt[a] += 1
  cnt[b] += 1
C = L[2*(N-1):]
C.sort()
for i in range(N):
  heappush(hq,(cnt[i],i))
arg = 0
m = sum(C)-C[-1]
while True:
  c, i = heappop(hq)
  if ans[i]!=-1:
    continue
  ans[i] = C[arg]
  arg += 1
  if arg==N:
    break
  for v in dic[i]:
    cnt[v] -= 1
    heappush(hq,(cnt[v],v))
print(m)
print(*ans)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
N, *L = map(int, open('0').read().split())
dic = [[] for i in range(N)]
ans = [-1]*N
cnt = [0]*N
hq = []
for a,b in zip(*[iter(L[:2*(N-1)])]*2):
  a -= 1
  b -= 1
  dic[a] += [b]
  dic[b] += [a]
  cnt[a] += 1
  cnt[b] += 1
C = L[2*(N-1):]
C.sort()
for i in range(N):
  heappush(hq,(cnt[i],i))
arg = 0
m = 0
while True:
  c, i = heappop(hq)
  if ans[i]!=-1:
    continue
  m += C[arg]*cnt[i]
  ans[i] = C[arg]
  arg += 1
  if arg==N:
    break
  for v in dic[i]:
    cnt[v] -= 1
    heappush(hq,(cnt[v],v))
print(m)
print(*ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

V = defaultdict(list)
N = int(input())
for _ in range(N-1):
    a, b = map(int, input().split())
    V[a].append(b)
    V[b].append(a)
*c, = map(int, input().split())
c.sort(reverse=True)

s = {}

cost = [-1]*(N+1)
p = 0
ans = 0
for v, l in sorted(V.items(),key=lambda x:-len(x[1])):
    print(cost[v], v, p, cost)
    if cost[v]==-1:
        cost[v] = c[p]
        p += 1

    for i in l:
        if cost[i]!=-1:continue
        cost[i] = c[p]
        s[(v, i)] = min(cost[i], cost[v])
        p += 1

print(sum(s.values()))
print(*cost[1:])

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
def node(i):
    global cur
    hist[i] = 1
    if i==1 and len(G[i])==1:
        A[i] = C[cur]
        cur += 1
        for j in G[i]:
            if hist[j]==0:
                node(j)
        return
    if i!=1 and len(G[i])==1:
        A[i] = C[cur]
        cur += 1
        return
    for j in G[i]:
        if hist[j]==0:
            node(j)
    A[i] = C[cur]
    cur += 1
    return

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())))
hist = [0 for _ in range(N+1)]
A = [0 for _ in range(N+1)]
cur = 0
node(1)
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: Runtime Error

Solution code:
N = int(input())
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
c = list(map(int,input().split()))
c.sort()
ans = sum(c) - max(c)
F = []
for i in range(1,N+1):
    n = len(G[i])
    if n == 1:
        F.append(i)
d = {}
i = 0
while i != N:
    x = F.pop(0)
    d[x] = c[i]
    i += 1
    if len(G[x]) > 0:
        y = G[x][0]
        G[y].remove(x)
        if y not in F:
            F.append(y)
ANS = []
for i in range(1,N+1):
    ANS.append(d[i])
print(ans)
print(*ANS)

Submission status: Runtime Error

Solution code:
N = int(input())
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
c = list(map(int,input().split()))
c.sort()
ans = sum(c) - max(c)
F = []
for i in range(1,N+1):
    n = len(G[i])
    if n == 1:
        F.append(i)
d = {}
i = 0
while len(F) != 0:
    x = F.pop(0)
    d[x] = c[i]
    i += 1
    if len(G[x]) > 0:
        y = G[x][0]
        G[y].remove(x)
        if y not in F:
            F.append(y)
ANS = []
for i in range(1,N+1):
    ANS.append(d[i])
print(ans)
print(*ANS)

Submission status: Runtime Error

Solution code:
N = int(input())
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
c = list(map(int,input().split()))
c.sort()
ans = sum(c) - c[N-1]
F = []
for i in range(N):
    n = len(G[i])
    if n == 1:
        F.append(i)
d = {}
i = 0
while len(F) != 0:
    x = F.pop(0)
    d[x] = c[i]
    i += 1
    if len(G[x]) > 0:
        y = G[x][0]
        G[y].remove(x)
        if y not in F:
            F.append(y)
ANS = []
for i in range(1,N+1):
    ANS.append(d[i])
print(ans)
print(*ANS)

Submission status: Runtime Error

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

print(sum(c) - max(c))
c = list(map(lambda x: x*(-1), c))
heapq.heapify(c)
d = [[0, i] for i in range(N)]
g = [set() for i in range(N)]
for a, b in ab:
    d[a-1][0] += 1
    d[b-1][0] += 1
    g[a-1].add(b-1)
    g[b-1].add(a-1)
d.sort(reverse=True, key=lambda x: x[0])
for i in range(N):
    d[i][0] = -1
d[0][0] = -1 * heapq.heappop(c)


def dfs(start):
    for x in g[start]:

        if d[x][0] == -1:

            d[x][0] = d[x][0] * heapq.heappop(c)

            dfs(x)


dfs(0)
d.sort(key=lambda x: x[1])

ans = [""]*N
for i in range(N):
    ans[i] = str(d[i][0])
print(" ".join(ans))

Submission status: Runtime Error

Solution code:
n, *L = map(int, open(0).read().split())
ab = L[:2 * n - 2]
c = sorted(L[2 * n - 2:])
con = [[] for _ in range(n)]
ans = [0] * n
tot = sum(c) - max(c)
for a, b in zip(*[iter(ab)] * 2):
	con[a - 1].append(b - 1)
	con[b - 1].append(a - 1)
vis = [0] * n
q = [0]
vis[0] = 1
while q:
	cur = q.pop()
	ans[cur] = c.pop()
	for nxt in con[cur]:
		if vis[nxt]:
			continue
		q.append(nxt)
print(tot)
print(*ans)

Submission status: Runtime Error

Solution code:
import heapq

N = int(input())
E = [list(map(lambda x: int(x)-1,input().split())) for _ in range(N-1)]
C = sorted(list(map(lambda x: int(x)*(-1),input().split())))
m = -sum(C[1:])
heapq.heapify(C)

V = [set() for _ in range(N)]
for u,v in E:
  V[u].add(v)
  V[v].add(u)

A = [0 for _ in range(N)]
def dfs(v,s):
  A[v] = -heapq.heappop(C)
  for u in V[v]:
    if u != s:
      dfs(u,v)
dfs(0,-1)

print(m)
print(*A)

Submission status: Runtime Error

Solution code:
import heapq

N = int(input())
E = [list(map(lambda x: int(x)-1,input().split())) for _ in range(N-1)]
C = list(map(lambda x: int(x)*(-1),input().split()))
heapq.heapify(C)

V = [set() for _ in range(N)]
for u,v in E:
  V[u].add(v)
  V[v].add(u)

A = [0 for _ in range(N)]
def dfs(v,s):
  A[v] = -heapq.heappop(C)
  for u in V[v]:
    if u != s:
      dfs(u,v)
dfs(0,-1)
print(*A)

Submission status: Runtime Error

Solution code:
n=int(input())
g=[[] for i in range(n)]
ro=[0]*n
c=list(map(int,input().split()))
c.sort(reverse=True)
for i in range(n-1):
    a,b=map(int,input().split())
    ro[a-1]+=1
    ro[b-1]+=1
    g[a-1].append(b-1)
    g[b-1].append(a-1)
m=max(ro)
mi=ro.index(m)
q=[mi]
ans=[0]*n
v=[0]*n
v[mi]=1
ans[mi]=c.pop()
while len(q)>0:
    s=q.pop()
    for i in g[s]:
        if v[i]==0:
            v[i]=1
            ans[i]=c.pop()
            q.append(i)
print(sum(ans)-max(ans))
print(*ans)

Submission status: Runtime Error

Solution code:
n=int(input())
g=[[] for i in range(n)]
ro=[0]*n
c=list(map(int,input().split()))
c.sort(reverse=True)
for i in range(n-1):
    a,b=map(int,input().split())
    ro[a-1]+=1
    ro[b-1]+=1
    g[a-1].append(b-1)
    g[b-1].append(a-1)
m=max(ro)
mi=ro.index(m)
q=[mi]
ans=[0]*n
v=[0]*n
v[mi]=1
ans[mi]=c.pop()
while len(q)>0:
    s=q.pop()
    for i in g[s]:
        if v[i]==0:
            v[i]=1
            ans[i]=c.pop()
            q.append(i)
print(sum(c)-max(c))
print(*ans)

Submission status: Runtime Error

Solution code:
from collections import deque

N=int(input())
AB=[list(map(int,input().split())) for _ in range(N-1)]
C=deque(sorted(map(int,input().split())))
edges=[[] for _ in range(N)]
for a,b in AB:
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

ps=[0]*N

def dfs(prev, curr):
    ps[curr]=C.pop()
    for dst in edges[curr]:
        if prev==dst:
            continue
        dfs(curr,dst)
dfs(-1,0)

ans=0
for a,b in AB:
    ans += min(ps[a-1],ps[b-1])

print(ans)
print(" ".join([str(p) for p in ps]))

Submission status: Runtime Error

Solution code:
n,k = list(map(int,input().split()))
m = 10**9+7
def inv(x):
  m = 10**9+7
  t = x
  y = 1
  while True:
    if t == 1:
      break
    y *= m // t
    t = m % t
    y *= -1
    y %= m
  return y
def c(x,y):
  t = 1
  for j in range(y):
    t *= x-j
    t *= inv(j+1)
  return t
for i in range(1,k+1):
  print( (c(k-1,i-1) * c(n-k+1,i)) % m )

Submission status: Runtime Error

Solution code:
N=int(input())
edge=[[] for i in range(N+1)]
res=[0 for i in range(N+1)]
for i in range(N-1):
	a,b=[int(i) for i in input().split()]
	edge[a].append(b)
	edge[b].append(a)
c=[int(i) for i in input().split()]
cs=sorted(c)
res[1]=cs.pop(-1)
def tree(i,fro):
	for e in edge[i]:
		if e==fro:
			continue
		res[e]=cs.pop(-1)
		if res[e]>res[i]:
			x=3/0
	for e in edge[i]:
		if e==fro:
			continue
		tree(e,i)
tree(1,0)
print(sum(c)-max(c))
print(" ".join(map(lambda x:str(x),res[1:])))

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)

al = [[] for _ in range(N+1)]
for a,b in ab:
    al[a].append(b)


d = [0] * (N)
d[ab[0][0]-1] = c[0]
cnt = 1
child = al[ab[0][0]]
ans = 0

while cnt < N:
    pi = int(child.pop())
    d[pi-1] = (c[cnt])
    ans += c[cnt]
    if al[pi]:
        child = child + al[pi]
    cnt += 1
    
print(ans)
print(' '.join(map(str,d)))

Submission status: Runtime Error

Solution code:
n = int(input())

tree = [[] for _ in range(n)]

for i in range(n-1):
    u, v = map(int, input().split(" "))
    u -= 1
    v -= 1
    
    tree[u].append(v)
    tree[v].append(u)

c_list = sorted([int(elm) for elm in input().split(" ")], reverse=True)

sort_nodes = [0] * n

#print("tree", tree)

def kettei(jibun_node, parent, count):
    sort_nodes[count] = jibun_node
    count += 1

    tonari_nodes = tree[jibun_node]
    for tonari_node in tonari_nodes:
        if tonari_node == parent:
            continue
        count = kettei(tonari_node, jibun_node, count)

    return count

kettei(0, -1, 0)

#print("sort_nodes", sort_nodes)

if n >= 2:
    val = sum(c_list[1:])
else:
    val = 0
print(val)

out_c_list = ["-1"] * n
for junban, node in enumerate(sort_nodes):
    out_c_list[node] = str(c_list[junban])

#print("out_c_list", out_c_list)

print(" ".join(out_c_list))

Submission status: Runtime Error

Solution code:
n = int(input())

tree = [[] for _ in range(n)]

for i in range(n-1):
    u, v = map(int, input().split(" "))
    u -= 1
    v -= 1
    
    tree[u].append(v)
    tree[v].append(u)

c_list = sorted([int(elm) for elm in input().split(" ")], reverse=True)

sort_nodes = [0] * n

#print("tree", tree)

def kettei(jibun_node, parent, count):
    sort_nodes[count] = jibun_node
    count += 1

    tonari_nodes = tree[jibun_node]
    for tonari_node in tonari_nodes:
        if tonari_node == parent:
            continue
        count = kettei(tonari_node, jibun_node, count)

    return count

kettei(0, -1, 0)

#print("sort_nodes", sort_nodes)

if n >= 2:
    val = sum(c_list[1:])
else:
    val = 0
print(val)

#out_c_list = [str(c_list[node]) for node in sort_nodes]
out_c_list = [-1] * n
for junban, node in enumerate(sort_nodes):
    out_c_list[node] = str(c_list[junban])

print(" ".join(out_c_list))

Submission status: Runtime Error

Solution code:
n = int(input())

tree = [[] for _ in range(n)]

for i in range(n-1):
    u, v = map(int, input().split(" "))
    u -= 1
    v -= 1
    
    tree[u].append(v)
    tree[v].append(u)

c_list = sorted([int(elm) for elm in input().split(" ")], reverse=True)

sort_nodes = [0] * n

def kettei(jibun_node, parent, count):
    sort_nodes[count] = jibun_node
    count += 1

    tonari_nodes = tree[jibun_node]
    for tonari_node in tonari_nodes:
        if tonari_node == parent:
            continue
        count = kettei(tonari_node, jibun_node, count)

    return count

kettei(0, -1, 0)

#print(sort_nodes)

val = sum(c_list[1:])
print(val)

out_c_list = [str(c_list[node]) for node in sort_nodes]

print(" ".join(out_c_list))

Submission status: Runtime Error

Solution code:
n = int(input())

tree = [[] for _ in range(n)]

for i in range(n-1):
    u, v = map(int, input().split(" "))
    u -= 1
    v -= 1
    
    tree[u].append(v)
    tree[v].append(u)

c_list = sorted([int(elm) for elm in input().split(" ")], reverse=True)

sort_nodes = [0] * n

def kettei(jibun_node, parent, count):
    sort_nodes[count] = jibun_node
    count += 1

    tonari_nodes = tree[jibun_node]
    for tonari_node in tonari_nodes:
        if tonari_node == parent:
            continue
        count = kettei(tonari_node, jibun_node, count)

    return count

kettei(0, -1, 0)

print(sort_nodes)

val = sum(c_list[1:])
print(val)

out_c_list = [str(c_list[node]) for node in sort_nodes]

print(" ".join(out_c_list))

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self):
        self.adj = []
        self.weight = 0

    def connect(self, v):
        self.adj.append(v)

    def __lt__(self, other):
        return len(self.adj) < len(other.adj)

    def dfs(self, parent):
        ret = 0
        for v in self.adj:
            if v == parent:
                continue
            ret += v.dfs(self) + min(self.weight, v.weight)
        return ret


def main():
    n = int(input())
    nodes = [Node() for i in range(n)]
    for i in range(n - 1):
        u, v = [int(x) for x in input().split()]
        nodes[u - 1].connect(nodes[v - 1])
        nodes[v - 1].connect(nodes[u - 1])
    sorted_nodes = sorted(nodes, reverse=True)
    sorted_weight = sorted([int(x) for x in input().split()], reverse=True)
    for i in range(n):
        sorted_nodes[i].weight = sorted_weight[i]
    ans = sorted_nodes[0].dfs(sorted_nodes[0])
    print(ans)
    print(*[v.weight for v in nodes])


main()
# print(*data, sep='\n')

Submission status: Runtime Error

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


class UnionFind:
    def __init__(self, N):
        # par = parent
        self.par = [i for i in range(N)]
        self.N = N
        self.hop = {i: -1 for i in range(N)}
        self.adj = [[] for i in range(N)]
        return

    def root(self, x):
        if self.par[x] == x:
            return (x)
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def same(self, x, y):
        return (self.root(x) == self.root(y))

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if (x == y):
            return False

        self.par[x] = min(x, y)
        self.par[y] = min(x, y)
        return True

    def find_root(self):
        for i in range(self.N):
            if i == self.root(i):
                return i
        return

    def dfs(self, i):
        for nh in self.adj[i]:
            if self.hop[nh] != -1:
                continue
            else:
                self.hop[nh] = self.hop[i] + 1
                self.dfs(nh)
        return


N = int(input())
uf = UnionFind(N)
AB = [[0, 0] for i in range(N - 1)]

for i in range(N - 1):
    a, b = inpl()
    a -= 1
    b -= 1
    AB[i][0] = a
    AB[i][1] = b
    uf.adj[a].append(b)
    uf.adj[b].append(a)

C = inpl()

for a, b in AB:
    uf.union(a, b)

root_num = uf.find_root()
uf.hop[root_num] = 0
uf.dfs(root_num)

dic2 = sorted(uf.hop.items(), key=lambda x: x[1], reverse=True)

ans = [0 for i in range(N)]
for i, k in enumerate(dic2):
    ans[k[0]] = i

C.sort()

print(sum(C[:-1]))
for i in range(N):
    if i != 0:
        print(" ", end="")
    print(C[ans[i]], end="")
print("")

Submission status: Runtime Error

Solution code:
inpl = lambda: list(map(int,input().split()))
class SegmentTree:
    def __init__(self, value, N=0, comp=lambda x,y: x<=y):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+1]
            left_v, right_v = self.get_value(left_i), self.get_value(right_i)
            if self.comp(left_v, right_v):
                self.node[i] = left_i
            else:
                self.node[i] = right_i

    def set_value(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.get_value(left_i), self.get_value(right_i)
            if self.comp(left_v, right_v):
                new_i = left_i
            else:
                new_i = right_i
            if new_i == self.node[i] and new_i != v:
                break
            else:
                self.node[i] = new_i

    def get_value(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def get_min(self, a=0, b=-1):
        return self.value[self.get_min_index(a,b)]

    def get_min_index(self,
                     a=0, b=-1,
                     k=0, l=0, r=-1):
        if b < 0:
            b = self.N
        if r < 0:
            r = self.N
        if a <= l and r <= b:
            return self.node[k]
        elif r <= a or b <= l:
            return None
        else:
            left_i = self.get_min_index(a,b,2*k+1,l,(l+r)//2)
            right_i = self.get_min_index(a,b,2*k+2,(l+r)//2,r)
            left_v, right_v = self.get_value(left_i), self.get_value(right_i)
            if self.comp(left_v, right_v):
                return left_i
            else:
                return right_i

N = int(input())
partners = []
orders = [0]*N
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)
    orders[a] += 1
    orders[b] += 1
sg = SegmentTree(orders)
C = sorted(inpl())
D = [0]*N
M = 0
for i in range(N-1):
    k = sg.get_min_index()
    D[k] = C[i]
    M += C[i]
    for p in partners[k]:
        partners[p].remove(k)
        sg.set_value(p, sg.get_value(p)-1)
    sg.set_value(k, None)
k = sg.get_min_index()
D[k] = C[N-1]

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

Submission status: Runtime Error

Solution code:
class Node:
    def __init__(self, i):
        self.index = i
        self.val = -1
        self.links = 0
        self.nodes = []

def depth_search(node):
    if node.val == -1:
        node.val = c.pop(0)
        for child in node.nodes:
            if child != node:
                depth_search(child)

N = int(input())

nodes = [Node(i) for i in range(N)]
count = [0 for i in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    node_a = nodes[a-1]
    node_b = nodes[b-1]
    node_b.nodes.append(node_a)
    node_a.links += 1
    node_a.nodes.append(node_b)
    node_b.links += 1

c = list(map(int, input().split()))
c = sorted(c, reverse=True)
max_c = max(c)

print(sum(c) - max_c)

depth_search(nodes[0])

for i in range(N-1):
    print(nodes[i].val, end=" ")
print(nodes[-1].val)

Submission status: Runtime Error

Solution code:
N = int(input())
Nodes = [[int(i) for i in input().split()] for j in range(N - 1)]
C = [int(i) for i in input().split()]
C.sort()
# 根から始め、巡回した葉にCの大きなものから順に書き込んで行く。
# int_list = list(sorted(C))
graph = [[] for _ in range(N)]
for u, v in Nodes:  # 0-basedとする
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)
# print(Nodes)
# print(graph)

# 各頂点にCの値が大きなもの順に書き込んでいく
ret = [0] * N
def dfs(c):
    if min(ret) > 0:    # 全て処理済み
        return 1
    # ret[c] = int_list.pop()
    ret[c] = C.pop()
    for next_edge in graph[c]:
        if ret[next_edge] == 0:  # まだ見ていない頂点だけ調べる
            dfs(next_edge)
    return 1
dfs(c=0)

print(sum(ret[1:]))
print(" ".join(map(str, ret)))

Submission status: Runtime Error

Solution code:
N = int(input())
Nodes = [[int(i) for i in input().split()] for j in range(N - 1)]
C = [int(i) for i in input().split()]
C.sort()
# 根から始め、巡回した葉にCの大きなものから順に書き込んで行く。
# int_list = list(sorted(C))
graph = [[] for _ in range(N)]
for u, v in Nodes:  # 0-basedとする
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)
# print(Nodes)
# print(graph)

# 各頂点にCの値が大きなもの順に書き込んでいく
ret = [0] * N
def dfs(c):
    # ret[c] = int_list.pop()
    ret[c] = C.pop()
    for next_edge in graph[c]:
        if ret[next_edge] == 0:  # まだ見ていない頂点だけ調べる
            dfs(next_edge)
dfs(c=0)

print(sum(ret[1:]))
print(" ".join(map(str, ret)))

Submission status: Runtime Error

Solution code:
N = int(input())
Nodes = [[int(i) for i in input().split()] for j in range(N - 1)]
C = [int(i) for i in input().split()]
C.sort()
# 根から始め、巡回した葉にCの大きなものから順に書き込んで行く。
# int_list = list(sorted(C))
graph = [[] for _ in range(N)]
for u, v in Nodes:  # 0-basedとする
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)
# print(Nodes)
# print(graph)

# 各頂点にCの値が大きなもの順に書き込んでいく
ret = [0] * N
def dfs(p, c):
    # ret[c] = int_list.pop()
    ret[c] = C.pop()
    for next_edge in graph[c]:
        if next_edge != p and ret[next_edge] == 0:  # 木を「逆戻り」しない頂点だけ調べる
            dfs(c, next_edge)
dfs(p=-1, c=0)

print(sum(ret[1:]))
print(" ".join(map(str, ret)))

Submission status: Runtime Error

Solution code:
def d_maximum_sum_of_minimum(N, Nodes, C):
    # 根から始め、巡回した葉にCの大きなものから順に書き込んで行く。

    int_list = list(sorted(C))
    graph = [[] for _ in range(N)]
    for u, v in Nodes:  # 0-basedとする
        graph[u - 1].append(v - 1)
        graph[v - 1].append(u - 1)

    def traverse_tree(parent, current, ret=[0] * N):
        """各頂点にCの値が大きなもの順に書き込んでいく"""
        def dfs(p, c):
            ret[c] = int_list.pop()
            for next_edge in graph[c]:
                if next_edge != p:  # 木を「逆戻り」しない頂点だけ調べる
                    dfs(c, next_edge)
        dfs(parent, current)
        return ret
    tmp = traverse_tree(-1, 0)
    return str(sum(tmp[1:])) + '\n' + ' '.join(map(str, tmp))

N = int(input())
Nodes = [[int(i) for i in input().split()] for j in range(N - 1)]
C = [int(i) for i in input().split()]
print(d_maximum_sum_of_minimum(N, Nodes, C))

Submission status: Runtime Error

Solution code:
N = int(input())
Nodes = [[int(i) for i in input().split()] for j in range(N - 1)]
C = [int(i) for i in input().split()]
C.sort()

graph = [[] for _ in range(N)]
for u, v in Nodes:
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)

ret = [0] * N
def dfs(p, c):
    ret[c] = C.pop()
    for next_edge in graph[c]:
        if next_edge != p:
            dfs(c, next_edge)
dfs(p=-1, c=0)

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