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

Solution code:

from collections import deque

n = int(input())
tree = [[] for i in range(n+1)]

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

c = list(map(int,input().split()))
#print(c)
#cs = sorted(c, reverse=True)
#print(cs)
cs = sorted(c)
#print(cs)

ansd=[0]*(n)
score=0

stack = deque()
stack.append(1)
ansd[0]=cs.pop()
visitted=[]

while stack:
    cur = stack.popleft()
    visitted.append(cur)
    for v in tree[cur]:
        if v in visitted:
            continue
        stack.append(v)
        ansd[v-1]=cs.pop()
        score += min(ansd[cur-1], ansd[v-1])

print(score)
print(*ansd, sep=' ')
#print(visitted)

Submission status: Accepted

Solution code:
n=int(input())
m = {}
cnt = [0] * (n+1)
edges = []

for i in range(n-1):
    a,b=map(int, input().split())
    edges.append((a, b))
    m[a] = m.get(a, set())
    m[a].add(b)
    m[b] = m.get(b, set())
    m[b].add(a)
    cnt[a] += 1
    cnt[b] += 1

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

from collections import deque

q = deque()
current = 0
ans = [0] * (n+1)
for i in range(1, n+1):
    if cnt[i] == 1:
        q.append(i)

while q:
    node = q.pop()
    ans[node] = c[current]
    current += 1
    for i in m[node]:
        cnt[i] -= 1
        if cnt[i] == 1:
            q.append(i)

print(sum(min([ans[i[0]], ans[i[1]]]) for i in edges))
for i in range(1, n+1):
    print(ans[i])

Submission status: Accepted

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

n = int(input())

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

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

value = 0
ans = [0] * n
memo = [0] * n
q = deque([0])
i = 0

while q:
    v = q.popleft()
    ans[v] = c[i]
    memo[v] = 1
    if i > 0:
        value += c[i]
    i += 1
    for nv in graph[v]:
        if memo[nv] == 1:
            continue
        memo[nv] = 1
        q.append(nv)

print(value)
print(*ans)

Submission status: Accepted

Solution code:
import os
import sys
import numpy as np

sys.setrecursionlimit(2147483647)
INF = float('inf')

if os.getenv('LOCAL'):
    sys.stdin = open('_in.txt')

N = int(sys.stdin.readline())
A, B = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N - 1)]))
C = list(map(int, sys.stdin.readline().split()))


def shortest_path(start, graph):
    stack = [(start, 0)]
    dists = [INF] * (N + 1)
    dists[start] = 0
    while stack:
        v, vw = stack.pop()
        for u, w in graph[v]:
            if dists[u] == INF:
                dists[u] = vw + w
                stack.append((u, vw + w))
    return dists


#: :type: list of (list of (int, int))
graph = [[] for _ in range(N + 1)]
for a, b in zip(A, B):
    graph[a].append((b, 1))
    graph[b].append((a, 1))

# 適当に root 決める
root = 1
distances = shortest_path(root, graph)[1:]

# 葉から小さい順に埋めてく
ans = np.zeros(N, dtype=int)
C.sort(reverse=True)
for i, di in enumerate(np.argsort(distances)):
    ans[di] = C[i]

print(sum(C) - max(C))
print(*ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, AB, C):
    def s(C):
        ret = 0
        for a, b in AB:
            ret += min(C[a-1], C[b-1])
        return ret

    vc = Counter()
    g = defaultdict(list)
    for a, b in AB:
        vc[a] += 1
        vc[b] += 1
        g[a].append(b)
        g[b].append(a)
    v = sorted(list(vc.items()), key=lambda x: x[1])[0]
    C.sort()
    ans = [-1] * (N+1)
    ans[v[0]] = C.pop()

    q = deque([v[0]])
    while q:
        v = q.popleft()
        for u in g[v]:
            if ans[u] == -1:
                ans[u] = C.pop()
                q.append(u)
    ans = ans[1:]
    print(s(ans))
    print(' '.join(map(str, ans)))


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N-1)]
    C = read_int_n()
    (slv(N, AB, C))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
nodes=[[] for i in range(N)]
for i in range(N-1):
    a,b=MAP()
    nodes[a-1].append(b-1)
    nodes[b-1].append(a-1)
C=LIST()

C.sort(reverse=True)

ans=[0]*N
cnt=0
def rec(cur):
    global cnt
    if ans[cur]:
        return
    ans[cur]=C[cnt]
    cnt+=1
    for nxt in nodes[cur]:
        rec(nxt)
rec(0)

if N==1:
    print(0)
else:
    print(sum(C[1:]))
print(*ans)

Submission status: Accepted

Solution code:
n = int(input())

tree = [[] for i in range(n)]
connect = [0 for i in range(n)]

inf = float('inf')

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

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

c.sort()

m = 0
d = [0 for i in range(n)]

for i in range(n):
    ind = connect.index(min(connect))
    m += max(connect[ind] * c[i], 0)
    d[ind]=c[i]
    connect[ind] = inf
    for j in range(len(tree[ind])):
        connect[tree[ind][j]]-=1
        if connect[j]==0:
            connect[j] = inf

print(m)
print(' '.join(map(str,d)))

Submission status: Accepted

Solution code:
def main():

    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**5)
    from collections import deque


    N = int(input())
    edges = []
    ad = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = map(int,input().split())
        a -= 1; b -= 1
        ad[a].append(b)
        ad[b].append(a)
        edges.append((a,b))

    C = deque(sorted(map(int,input().split()), reverse=True))

    nodes = [-1]*N

    def dfs(v=0,pv=-1):
        for nv in ad[v]:
            if nv == pv:
                continue
            dfs(nv,v)
        nodes[v] = C.pop()

    dfs()
    ans = 0

    for a,b in edges:
        ans += min(nodes[a],nodes[b])

    print(ans)
    print(*nodes)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

def dfs(v):
    vs.append(v)
    useds[v] = True
    for v2 in adjL[v]:
        if not useds[v2]:
            dfs(v2)

N = int(input())
adjL = [[] for _ in range(N)]
ABs = []
for _ in range(N-1):
    a, b = map(int, input().split())
    adjL[a-1].append(b-1)
    adjL[b-1].append(a-1)
    ABs.append((a-1, b-1))
cs = list(map(int, input().split()))

cs.sort(reverse=True)

vs = []
useds = [False] * N
dfs(0)

anss = [0] * N
for v, c in zip(vs, cs):
    anss[v] = c

score = 0
for A, B in ABs:
    score += min(anss[A], anss[B])

print(score)
print(*anss)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

n = int(input())
ab = [[int(item) for item in input().split()] for _ in range(n-1)]
c = [int(item) for item in input().split()]
c.sort()
c.reverse()
sum_score = sum(c[1:])

edge = [[] for _ in range(n)]
score = [0] * n

for a, b in ab:
    a-=1; b-=1
    edge[a].append(b)
    edge[b].append(a)

it = 0
def dfs(f ,n):
    global it
    score[n] = c[it]
    it += 1
    for item in edge[n]:
        if item == f:
            continue
        dfs(n, item)
    return True

dfs(-1, 0)
print(sum_score)
print(" ".join([str(item) for item in score]))

Submission status: Accepted

Solution code:
N = int(input())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]
*C, = map(int,input().split())

connect = [[] for _ in [0]*N]
for a,b in AB:
    connect[a-1].append(b-1)
    connect[b-1].append(a-1)
d = [-1]*N
d[0] = 0
q = [0]
while q:
    qq = []
    for i in q:
        for j in connect[i]:
            if d[j] == -1:
                d[j] = d[i]+1
                qq.append(j)
    q = qq

o = sorted(zip(d,range(N)),key =lambda x:-x[0])
C.sort()
ans = [0]*N
for j,tmp in enumerate(o):
    d,i = tmp
    ans[i] = C[j]
print(sum(C)-C[-1])
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
import heapq
N = int(input())
T = [[] for i in range(N)]
Edge = []
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    T[a].append(b)
    T[b].append(a)
    Edge.append((a, b))
C = sorted(list(map(int, input().split())))

out = [(len(T[i]), i) for i in range(N)]
out.sort(reverse=True)

P = [-1] * N
que = [out[0]]
while que:
    u, n = heapq.heappop(que)
    P[n] = C.pop()
    for to in T[n]:
        if not P[to] < 0:
            continue
        heapq.heappush(que, [len(T[to]), to])

ans = 0
for a, b in Edge:
    ans += min(P[a], P[b])

print(ans)
print(*P, sep=' ')

Submission status: Accepted

Solution code:
import sys

n = int(input())
lines = sys.stdin.readlines()
links = [set() for _ in [0] * n]
for line in lines[:n - 1]:
    a, b = list(map(int, line.split()))
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

ccc = list(map(int, lines[-1].split()))
ccc.sort(reverse=True)
ans = [-1] * n
ans_sum = 0
leaves = {i for i, l in enumerate(links) if len(l) == 1}

while leaves:
    v = leaves.pop()
    c = ccc.pop()
    ans[v] = c
    if not ccc:
        break
    ans_sum += c
    for u in links[v]:
        lu = links[u]
        lu.remove(v)
        if len(lu) == 1:
            leaves.add(u)

print(ans_sum)
print(*ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify, heapreplace
from collections import defaultdict

class Solution:
    def main(self):
        N = int(input())
        A = []
        B = []
        path =  defaultdict(set)
        for _ in range(N-1):
            a, b = map(int, input().split())
            path[a-1].add(b-1)
            path[b-1].add(a-1)
            A.append(a-1)
            B.append(b-1)
        c = sorted(list(map(int, input().split())))

        cnt = [None] * N
        max_idx = 0
        max_val = 0
        for i in range(N):
            cnt[i] = len(path[i])
            if max_val < cnt[i]:
                max_val = cnt[i]
                max_idx = i

        stack = [max_val]
        res = [None] * N
        while stack:
            p = stack.pop(0)
            if res[p] == None:
                res[p] = c.pop()
                for n in path[p]:
                    stack.append(n)

        score = 0
        for a, b in zip(A, B):
            score += min(res[a], res[b])

        print(score)
        print(' '.join([str(v) for v in res]))


if __name__ == '__main__':
    Solution().main()

Submission status: Accepted

Solution code:
n=int(input())
ab=[list(map(int,input().split())) for i in range(n-1)]
c=list(map(int,input().split()))
c.sort(reverse=True)
l=[[] for i in range(n+1)]
ans=[0 for i in range(n+1)]
ans[1]=c[0]
q=[1]
ci=1
for a,b in ab:
    l[a].append(b)
    l[b].append(a)
while(len(q)>0):
    t=q.pop()
    tl=l[t]
    for i in tl:
        if(ans[i]==0):
            ans[i]=c[ci]
            ci+=1
            q.append(i)
print(sum(c[1:]))
print(" ".join(map(str,ans[1:])))

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr, stdin
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect
import functools

setrecursionlimit(10**7)

def input():
  return stdin.readline().strip()

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N = read()
edges = [set() for _ in range(N)]
for _ in range(N-1):
  a, b = reads()
  a, b = a-1, b-1
  edges[a].add(b)
  edges[b].add(a)
c = reads()
c.sort()

M = sum(c[:-1])
visited = [False] * N
idx = 0

result = [0] * N

def dfs(x):
  global idx
  for y in edges[x]:
    edges[y].remove(x)
    dfs(y)
  result[x] = c[idx]
  idx += 1

dfs(0)

print(M)
print(" ".join(str(x) for x in result))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

N = int(input())
a, b = (
    zip(*(map(int, input().split()) for _ in range(N - 1))) if N - 1 else
    ((), ())
)
c = list(map(int, input().split()))

INF = 10**10
G = [{} for _ in range(N + 1)]
for x, y in zip(a, b):
    G[x][y] = 1
    G[y][x] = 1


def dijkstra(G, s):
    dp = [INF for _ in range(len(G))]
    q = []
    heappush(q, (0, s))
    while q:
        c, i = heappop(q)
        if dp[i] == INF:
            dp[i] = c
            for j, w in G[i].items():
                heappush(q, (c + w, j))
    return dp


dp = dijkstra(G, 1)
dp2 = dict()

for x, (_, z) in zip(
    sorted(c), sorted(zip(dp[1:], range(1, N + 1)), reverse=True)
):
    dp2[z] = x

ans = 0
for x, y in zip(a, b):
    ans += min(dp2[x], dp2[y])
print(ans)
ans2 = ' '.join(
    str(dp2[i])
    for i in range(1, N + 1)
)
print(ans2)

Submission status: Accepted

Solution code:
N = int(input())
g = {i: [] for i in range(N)}
for i in range(N - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
c = list(map(int, input().split()))
c.sort()
print(sum(c[:-1]))
nums = [0] * N
stack = [0]
while stack:
    d = stack.pop()
    nums[d] = c.pop()
    for node in g[d]:
        if nums[node] == 0:
            stack.append(node)
print(' '.join(map(str, nums)))

Submission status: Accepted

Solution code:
N=int(input())
A=[[] for i in range(N+1)]
B=[0 for i in range(N+1)]
for i in range(N-1):
    a,b=[int(x) for x in input().split()]
    A[a].append(b)
    A[b].append(a)
    B[a]+=1
    B[b]+=1
C=sorted( [int(x) for x in input().split()] )
D=[-1 for i in range(N+1)]
M=sum(C) - C[-1]
isEnd=[]
for i in range(1,N+1):
    if B[i]==1:
        isEnd.append(i)

for c in C:
    d=isEnd.pop()
    D[d]=c
    B[d]=0
    #M += c
    for k in A[d]:
        A[k].remove(d)
        B[k]-=1
        if B[k]==1:
            isEnd.append(k)
print (M)
print (' '.join([str(x) for x in D[1:]]) )

Submission status: Accepted

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

R = {}
for a, b in ab:
  if a - 1 in R:
    R[a - 1].append(b - 1)
  else:
    R[a - 1] = [b - 1]
  if b - 1 in R:
    R[b - 1].append(a - 1)
  else:
    R[b - 1] = [a - 1]

L = [0] * N
L[0] = 1
F = []
RL = {}
RL[1] = [0]
RL[2] = []
for i in R[0]:
  F.append(i)
  L[i] = 2
  RL[2].append(i)

k = 2
while F != []:
  k += 1
  Ft = []
  RL[k] = []
  for i in F:
    for j in R[i]:
      if L[j] == 0:
        L[j] = k
        Ft.append(j)
        RL[k].append(j)
  F = Ft

Ans = [0] * N
c.sort()
cnt = 0
for i in range(k - 1, 0, -1):
  for j in RL[i]:
    Ans[j] = c[cnt]
    cnt += 1
print(sum(c) - max(c))
s = str(Ans[0])
for i in range(1, N):
  s += " " + str(Ans[i])
print(s)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

n = int(input())

graph = [[] for i in range(n)]
edge_cnt = [0] * n
for i in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    edge_cnt[a-1] += 1
    edge_cnt[b-1] += 1


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

v = 0
for i in range(n):
    if edge_cnt[i] == 1:
        v = i
        break

nodes = [0] * n
total_score = -c[-1]


def dfs(v):
    global total_score
    if nodes[v] > 0:
        return
    nodes[v] = c.pop()
    total_score += nodes[v]
    for nv in graph[v]:
        if nodes[nv] > 0:
            continue
        dfs(nv)


dfs(v)
print(total_score)
print(*nodes, sep=' ')

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    print(180*(n-2))
    return

#B
def B():
    s = S()
    res = 15-len(s)
    k = s.count("o")
    if k+res >= 8:
        print("YES")
    else:
        print("NO")
    return

#C
def C():
    n,a,b,c = LI()
    return

#D
def D():
    n = I()
    v = [[] for i in range(n)]
    f = [[0,i] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        f[a][0] += 1
        f[b][0] += 1
    f.sort(key = lambda x:-x[0])
    s = f[0][1]
    c = LI()
    c.sort(key = lambda x:-x)
    f[0][0] = c[0]
    q = deque()
    q.append(s)
    bfs = [1 for i in range(n)]
    f.sort(key = lambda x:x[1])
    bfs[s] = 0
    k = 1
    while q:
        x = q.popleft()
        for y in v[x]:
            if bfs[y]:
                bfs[y] = 0
                f[y][0] = c[k]
                k += 1
                q.append(y)
    ans = 0
    q.append(s)
    bfs = [1 for i in range(n)]
    bfs[s] = 0
    while q:
        x = q.popleft()
        for y in v[x]:
            ans += min(f[x][0],f[y][0])
            if bfs[y]:
                bfs[y] = 0
                q.append(y)
    print(ans//2)
    for i, j in f[:-1]:
        print(i,end = " ")
    print(f[-1][0])
    return

#E
def E():
    n = I()
    return

#F
def F():
    n = I()
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
n = int(input())
ab = [list(map(int,input().split())) for _ in range(n-1)]
c = list(map(int,input().split()))
c = sorted(c)[::-1]
g = {}
for i in range(1,n+1):
    g[i] = []
for a,b in ab:
    g[a].append(b)
    g[b].append(a)
from collections import deque
q = deque([g[1]])
done = [0]*(n+1)
done[1] = 1
ans = [0]*n
ans[0] = c[0]
cnt = 1
while q:
    v = q.popleft()
    for v_ in v:
        if done[v_]==0:
            done[v_] = 1
            ans[v_-1] = c[cnt]
            cnt += 1
            q.append(g[v_])
print(sum(c[1:]))
for i in ans:
    print(i,end=' ')
print()

Submission status: Accepted

Solution code:
def build_tree(N, edge_list):

    G = dict()
    for i in range(1, N+1):
        G[i] = dict()

    for i in range(N-1):
        a, b = edge_list[i]
        G[a][b] = 1
        G[b][a] = 1

    leaves = []
    for i in range(1, N+1):
        if len(G[i].keys()) == 1:
            leaves.append(i)

    return G, leaves


def pop_leaf_loop(G, leaves, c_list):

    res_list = [""]*N

    for i in range(N):
        leaf = leaves[i]
        res_list[leaf-1] = str(c_list[i])
        for j in G[leaf]:
            del G[j][leaf]
            if len(G[j].keys()) == 1:
                leaves.append(j)

    return res_list


if __name__ == "__main__":
    N = int(input())
    edge_list = [[] for _ in range(N-1)]
    for i in range(N-1):
        edge_list[i] = list(map(int, input().split()))
    c_list = list(sorted(list(map(int, input().split()))))
    G, leaves = build_tree(N, edge_list)
    res_list = pop_leaf_loop(G, leaves, c_list)
    print(sum(c_list) - max(c_list))
    print(" ".join(res_list))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import collections


class Node(object):

  def __init__(self):
    self.value = 0
    self.edges = []


def main():
  n = int(input())
  nodes = [Node() for _ in range(n)]

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

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

  print(sum(values[1:]))

  queue = collections.deque()
  queue.append(nodes[0])
  index = 0

  while len(queue) != 0:
    node = queue.popleft()
    node.value = values[index]
    index += 1

    queue.extend(n for n in node.edges if n.value == 0)

  print(' '.join(str(n.value) for n in nodes))


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)


def main():
    n = I()
    aa = [LI_() for _ in range(n-1)]
    c = sorted(LI(), reverse=True)
    e = collections.defaultdict(set)
    for a,b in aa:
        e[a].add(b)
        e[b].add(a)

    ci = 0
    q = [0]
    v = set([0])
    r = [0] * n
    while q:
        nq = []
        for t in q:
            r[t] = c[ci]
            ci += 1
            for nt in e[t]:
                if nt in v:
                    continue
                v.add(nt)
                nq.append(nt)
        q = nq

    return '{}\n{}'.format(sum(c[1:]), ' '.join(map(str, r)))


print(main())

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int,input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
c = list(map(int,input().split()))
L = [0] * N

c.sort(reverse = True)

def dfs(x, par, index):
    L[x] = c[index]
    for u in edges[x]:
        if u != par:
            index += 1
            index = dfs(u, x, index)
    return index

dfs(0, -1, 0)

print(sum(L[1:]))
print(*L)

Submission status: Runtime Error

Solution code:
from collections import deque

n=int(input())
to=[[] for _ in range(n)]
eda=[]
for _ in range(n-1):
  a,b=map(int,input().split())
  to[a-1].append(b-1)
  to[b-1].append(a-1)
  eda.append([a-1,b-1])
  
c=list(map(int,input().split()))

c.sort(reverse=True)

cd=deque(c)
poi=[0 for _ in range(n)] 
vi=[-1 for _ in range(n)]

vi[0]+=1
def dfs(now):
  vi[now]+=1
  v=cd.popleft()
  poi[now]+=v
  for i in to[now]:
    if vi[i]==-1:
      dfs(i)
  
dfs(0)

ans=0

for u in eda:
  x,y=u
  ans+=min(poi[x],poi[y])
  
print(ans)
for u in range(n):
  poi[u]=str(poi[u])
  
print(' '.join(poi))

Submission status: Runtime Error

Solution code:
def DFS(num,pre):
    global point
    if color[num]=="white":
        A[num]=C.pop()
        point +=min(A[num],pre)
        color[num]="black"
        for i in tree[num]:
            DFS(i,A[num])


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

color=["white" for _ in range(n+1)]
tree=[[] for _ in range(n+1)]
for a,b in AB:
    tree[a].append(b)
    tree[b].append(a)

A=[0 for _ in range(n+1)]
point=0
DFS(1,0)

print(point)
print(*A[1:])

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())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
c=list(map(int,input().split()))

d=[-1]*N

def depth(n):
    seen[n]=1
    ret=0
    for g in G[n]:
        if seen[g]==1:continue
        seen[g]=1
        temp=1+depth(g)
        ret=max(ret,temp)
    return ret

dep=[]
for i in range(N):
    seen=[0]*N
    de=depth(i)
    d[i]=de
    dep.append([de,i])

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

ans=[-1]*N
for i in range(N):
    ans[dep[i][1]]=c[i]

print(*ans)

Submission status: Runtime Error

Solution code:
5
1 2
1 3
1 4
1 5
3141 59 26 53 59

Submission status: Runtime Error

Solution code:
N = int(input())
edge = [[] for _ in range(N)]
cnt = [[0,i] for i in range(N)]

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

cnt.sort()
C = list(map(int, input().split()))
C.sort()
nodes = [0] * N
for idx, (c, i) in enumerate(cnt):
    nodes[i] = C[idx]

#print(nodes)

ans = []

def dfs(v, pv, w):
    ans.append(min(w, nodes[v]))
    for nv in edge[v]:
        if pv == nv: continue
        dfs(nv, v, nodes[v])

dfs(0, 0, 0)
print(sum(ans))
print(*nodes, sep=" ")

Submission status: Runtime Error

Solution code:
n = int(input())
edges = [[]for _ in range(n)]
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    edges[a].append(b)
    edges[b].append(a)


cost = sorted(map(int, input().split()), reverse=True)

priority = [(len(edge), v) for v, edge in enumerate(edges)]
priority.sort(reverse=True)
ans = [None]*n
while priority:
    d, v = priority.pop()
    c = cost.pop()
    ans[v] = c

m = 0


def dfs(v, parent):
    if parent != -1:
        global m
        m += min(ans[v], ans[parent])

    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v)


dfs(0, -1)
print(m)
print(*ans)

Submission status: Runtime Error

Solution code:
from collections import deque

n = int(input())

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

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

ans = []
s = [0] * n
que = deque([0])
while que:
    t = que.popleft()
    ans.append(c.pop())
    s[t] = 1
    for e in g[t]:
        if not s[e]:
            que.append(e)

print(sum(c) - max(c))
print(*ans)

Submission status: Runtime Error

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

D = [0] * N

def dfs(x, parent, index):
    D[x] = C[index]
    index += 1
    for u in edges[x]:
        if u != parent:
            index = dfs(u, x, index)
    return index

dfs(0, -1, 0)

print(sum(C[1:]))
print(*D)

Submission status: Runtime Error

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

D = [0] * N

index = 0
def dfs(x, parent):
    global index
    D[x] = C[index]
#     index += 1
    for u in edges[x]:
        if u != parent:
            dfs(u, x)

dfs(0, -1)

print(sum(C[1:]))
print(*D)

Submission status: Runtime Error

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

D = [0] * N

index = 0
def dfs(x, parent):
    global index
    D[x] = C[index]
    index += 1
    for u in edges[x]:
        if u != parent:
            dfs(u, x)

dfs(0, -1)
print(0)
# print(sum(C[1:]))
print(*D)

Submission status: Runtime Error

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

D = [0] * N

index = 0
def dfs(x, parent):
    global index
    D[x] = C[index]
    index += 1
    for u in edges[x]:
        if u != parent:
            dfs(u, x)

dfs(0, -1)

print(sum(C[1:]))
print(*D)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)


def DFS(num):
    if color[num]=="white":
        ans[num]=C.pop()
        color[num]="black"
        for i in T[num]:
            DFS(i)


n=int(input())
AB=[list(map(int,input().split())) for _ in range(n-1)]
C=sorted(list(map(int,input().split())))
color=["white" for _ in range(n)]

T=[[] for _ in range(n)]
for a,b in AB:
    T[a-1].append(b-1)
    T[b-1].append(a-1)

ans=[0 for _ in range(n)]
DFS(0)

point=0
color=["white" for _ in range(n)]
for i in range(1,n+1):
    if len(T[i])>0:
        color[i-1]="black"
        for j in T[i]:
            if color[j-1]=="white":
                point +=min(ans[i-1],ans[j-1])
                color[j-1]="black"

print(point)
print(*ans)