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:
def intinput(): return map(int,input().split())

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

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

Submission status: Runtime Error

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

def point(x, prev, turn=0):
    if turn > n:
        return
    dp[x] = c[n - dp.count(0)]
    for i in edge[x]:
        if dp[i] != 0:
            continue
        if i == prev:
            continue
        else:
            point(i, x, turn + 1)
    return

ans = 0
for i in range(n):
    dp = [0] * n
    point(i, -1)

    m = 0
    for a, b in e:
        m += min(dp[a], dp[b])
    if m > ans:
        ans = m
        d = dp

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from collections import deque



## input
N = int(input())
tr = [{-1} for _ in range(N)]
for _ in range(N-1):
  a,b = map(int, input().split())
  tr[a-1].add(b-1)
  tr[b-1].add(a-1)
costs = sorted(list(map(int, input().split())), reverse=True)+[0]

## solve
root = 0
#for i in range(N):
#  if len(tr[root]) < len(tr[i]):
#    root = i

idx = deque()
def make_tr(rt,p):
  idx.append(p)
  for q in tr[p]:
    if q != rt and q > 0:
      make_tr(p,q)

make_tr(-1,root)

ans = [None for _ in range(N)]
j = 0
for i in idx:
  ans[i] = str(costs[j])
  j += 1

## output
print(sum(costs[1:]))
print(" ".join(ans))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
"""<https://github.com/cheran-senthil/PyRival>"""
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    _str = str
    str = lambda x=b"": x if type(x) is bytes else _str(x).encode()


def main():
    N = read_int()
    g = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = read_int_array()
        g[a-1].append(b-1)
        g[b-1].append(a-1)
    C = read_int_array()
    C.sort()
    labels = [None]*N
    labels[0] = C.pop()
    M = sum(C)
    q = [0]
    for x in q:
        for ch in g[x]:
            if labels[ch] is None:
                q.append(ch)
                labels[ch] = C.pop()

    print(M)
    print(' '.join(map(_str, labels)))





# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        if self.buffer.tell():
            return self.buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", b" "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", b"\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip(b"\r\n")


def read():
    return input()


def read_array(sep=None, maxsplit=-1):
    return read().split(sep, maxsplit)


def read_int():
    return int(read())


def read_int_array(sep=None, maxsplit=-1):
    return [int(a) for a in read_array(sep, maxsplit)]

# endregion

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def dfs(N, used, lst):
    if (len(used) == N):
        lst.append(used[:])
    else:
        for i in range(N):
            if i in used:
                continue
            else:
                next = used[:] + [i]
                dfs(N, next, lst)

# input
N = int(input())
ab_list = [list(map(int, input().split())) for _ in range(N-1)]
c_list = list(map(int, input().split()))
# search 
lst = []
dfs(N, [], lst)
max_score = 0
ans = []
for index in lst:
    c = [c_list[i] for i in index]
    score = 0
    for edge in ab_list:
        score += min(c[edge[0]-1], c[edge[1]-1])
    if (score > max_score):
        max_score = score
        ans = c
print(max_score)
print(" ".join(map(str, ans)))

Submission status: Runtime Error

Solution code:
N = int(input())
edge = [list(map(lambda x: x-1, list(map(int, input().split())))) for i in range(N-1)]
c = sorted(list(map(int, input().split())))
c = c[:((N-1)//2)] + c[((N-1)//2):][::-1]


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

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


for i in range(N-1):
    ai, bi = edge[i]
    edge_count[ai][0] += 1
    edge_count[bi][0] += 1

edge_count_old = edge_count.copy()
edge_count = sorted(edge_count, key=lambda x: (x[0], edge_count_old[x[1]][0] ))

for i, eg in enumerate(edge_count):
    ans[eg[1]] = c[i]
ans_sum = 0

for i in range(N-1):
    ai, bi = edge[i]
    ans_sum += min(ans[ai], ans[bi])

print(ans_sum)
print(*ans)

Submission status: Runtime Error

Solution code:


def main():
    n = input()
    edges = []
    nodes = [0] * n
    children = {i: [] for i in xrange(n)}
    for _ in xrange(n - 1):
        a, b = map(int, raw_input().split())
        a -= 1
        b -= 1
        edges.append([a, b])
        nodes[a] += 1
        nodes[b] += 1
        children[a].append(b)
        children[b].append(a)

    def search(i, deg, dist, visited):
        ret = []
        for j in children[i]:
            if nodes[j] < deg:
                return dist
            if nodes[j] > deg:
                continue
            if j in visited:
                continue
            visited.add(j)
            ret.append(search(j, deg, dist + 1, visited))
        if ret:
            return min(ret)
        else:
            return dist

    def key(i):
        deg = nodes[i]
        return deg, search(i, deg, 1, {i})

    nodes = sorted([node for node in xrange(n)],
                   key=lambda i: key(i))
    cc = map(int, raw_input().split())
    cc.sort()
    ans = [0] * n
    for node, c in zip(nodes, cc):
        ans[node] = c
    score = 0
    for a, b in edges:
        score += min(ans[a], ans[b])
    print score
    print ' '.join(map(str, ans))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from collections import deque



## input
N = int(input())
tr = [set() for _ in range(N)]
for _ in range(N-1):
  a,b = map(int, input().split())
  tr[a-1].add(b-1)
  tr[b-1].add(a-1)
costs = sorted(list(map(int, input().split())), reverse=True)+[0]

## solve
root = 0
#for i in range(N):
#  if len(tr[root]) < len(tr[i]):
#    root = i
tr[root].add(-1)

idx = deque()
def make_tr(rt,p):
  idx.append(p)
  for q in tr[p]:
    if q != rt:
      make_tr(p,q)

make_tr(-1,root)

ans = [None for _ in range(N)]
j = 0
for i in idx:
  ans[i] = str(costs[j])
  j += 1

## output
print(sum(costs[1:]))
print(" ".join(ans))

Submission status: Runtime Error

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

    def __lt__(self, other):
        # self < other
        return self.link < other.link

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

N = int(input())
if N == 1:
    c = list(map(int, input().split()))
    print(0)
    print(c[0])
else:
    nodes = [Node(i) 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_b.link += 1
        node_a.nodes.append(node_b)
        node_a.link += 1

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

    max_c = 0
    sum_c = 0
    for tmp in c:
        sum_c += tmp
        max_c = max(max_c, tmp)

    width_search(max(nodes))

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

Submission status: Runtime Error

Solution code:
def dfs(N, used, lst):
    if (len(used) == N):
        lst.append(used[:])
    else:
        for i in range(N):
            if i in used:
                continue
            else:
                next = used[:] + [i]
                dfs(N, next, lst)

# input
N = int(input())
ab_list = [list(map(int, input().split())) for _ in range(N-1)]
c_list = list(map(int, input().split()))
# search 
lst = []
dfs(5, [], lst)
# get_c = lambda c: c[]
tmp = 0
ans = []
for index in lst:
    c = [c_list[i] for i in index]
    score = 0
    for edge in ab_list:
        score += min(c[edge[0]-1], c[edge[1]-1])
    if (score > tmp):
        tmp = score
        ans = c
print(tmp)
print(" ".join(map(str, ans)))

Submission status: Runtime Error

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

    def __lt__(self, other):
        # self < other
        return self.link < other.link

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

N = int(input())
if N == 1:
    c = int(input())
    print(0)
    print(c)
else:
    nodes = [Node(i) 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_b.link += 1
        node_a.nodes.append(node_b)
        node_a.link += 1

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

    max_c = 0
    sum_c = 0
    for tmp in c:
        sum_c += tmp
        max_c = max(max_c, tmp)

    width_search(max(nodes))

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n = int(input())
s = [list(map(int,input().split())) for i in range(n-1)]
c = list(map(int,input().split()))
c.sort()
t = [-1] * n 
p = sum(c[:n-1])
q = defaultdict(list)
for i in range(n-1):
    q[s[i][0]] += [s[i][1]]
    q[s[i][1]] += [s[i][0]]

t1 = [t,1]

def find(q,x,t1):
    r = q[x]
    t1[0][x-1] = 0
    for i in range(len(r)):
        if t1[0][r[i]-1] == 0:
            continue
        else:
            t1 = find(q,r[i],t1)
    t1[0][x-1] = t1[1]
    t1[1] += 1
    return t1

o = find(q,1,t1)
o1 = o[0]
print(p)
b = ""
for i in range(n):
    b += str(c[o1[i]-1]) + " "

print(b)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from collections import deque



## input
N = int(input())
tr = [set() for _ in range(N)]
for _ in range(N-1):
  a,b = map(int, input().split())
  tr[a-1].add(b-1)
  tr[b-1].add(a-1)
costs = sorted(list(map(int, input().split())), reverse=True)

## solve
root = 0
#for i in range(N):
#  if len(tr[root]) < len(tr[i]):
#    root = i
tr[root].add(-1)

idx = deque()
def make_tr(rt,p):
  idx.append(p)
  tr[p].remove(rt)
  for q in tr[p]:
    make_tr(p,q)

make_tr(-1,root)

ans = [None for _ in range(N)]
j = 0
for i in idx:
  ans[i] = costs[j]
  j += 1

## output
print(sum(costs[1:]))
for c in ans:
  print(c,end=" ")
print()

Submission status: Runtime Error

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

    def __lt__(self, other):
        # self < other
        return self.link < other.link

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

N = int(input())
if N == 1:
    print(0)
else:
    nodes = [Node(i) 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_b.link += 1
        node_a.nodes.append(node_b)
        node_a.link += 1

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

    max_c = 0
    sum_c = 0
    for tmp in c:
        sum_c += tmp
        max_c = max(max_c, tmp)

    width_search(max(nodes))

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

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()
edge = [[] for _ in range(N)]
for a, b in ab:
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
ans = 0
count = 0
anse = [None for _ in range(N)]
def dfs(v, p):
    global ans
    global count
    if p != -1:
        ans += min(c[count], c[count+1])
        if anse[p-1] is None:
            anse[p-1] = c[count]
        if anse[v-1] is None:
            anse[v-1] = c[count+1]
        count += 1
    for nv in edge[v]:
        if nv == p:
            continue
        dfs(nv, v)
dfs(0, -1)
print(ans)
print(" ".join(map(str, anse)))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from collections import deque



## input
N = int(input())
tr = [set() for _ in range(N)]
for _ in range(N-1):
  a,b = map(int, input().split())
  tr[a-1].add(b-1)
  tr[b-1].add(a-1)
costs = sorted(list(map(int, input().split())), reverse=True)

## solve
if N == 1:
  print(0)
  print(costs[0])
elif N == 2:
  print(min(costs))
  print(costs[0],costs[1])
else:
  root = 0
  for i in range(N):
    if len(tr[root]) < len(tr[i]):
      root = i
  tr[root].add(-1)

  idx = deque()
  def make_tr(rt,p):
    idx.append(p)
    tr[p].remove(rt)
    for q in tr[p]:
      make_tr(p,q)

  make_tr(-1,root)

  ans = [None for _ in range(N)]
  j = 0
  for i in idx:
    ans[i] = costs[j]
    j += 1

  ## output
  print(sum(costs[1:]))
  for c in ans:
    print(c,end=" ")
  print()

Submission status: Runtime Error

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

    def __lt__(self, other):
        # self < other
        return self.link < other.link

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

N = int(input())

nodes = [Node(i) 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]
    if node_a not in node_b.nodes:
        node_b.nodes.append(node_a)
        node_b.link += 1
    if node_b not in node_a.nodes:
        node_a.nodes.append(node_b)
        node_a.link += 1

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

max_c = 0
sum_c = 0
for tmp in c:
    sum_c += tmp
    max_c = max(max_c, tmp)

width_search(max(nodes))

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

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()
edge = [[] for _ in range(N)]
for a, b in ab:
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
ans = 0
count = 0
anse = [None for _ in range(N)]
def dfs(v, p):
    global ans
    global count
    if p != -1:
        ans += min(c[count], c[count+1])
        anse[p-1] = c[count]
        anse[v-1] = c[count+1]
        count += 1
    for nv in edge[v]:
        if nv == p:
            continue
        dfs(nv, v)
dfs(0, -1)
print(ans)
print(" ".join(map(str, anse)))

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()
c.reverse()
m = c[0]
s = sum(c)
ans = [0] * N

def f(x):
    for i in range(N - 1):
        if ab[i][0] == x:
            if ans[ab[i][1] - 1] == 0:
                ans[ab[i][1] - 1] = c.pop(0)
                f(ab[i][1])
        if ab[i][1] == x:
            if ans[ab[i][0] - 1] == 0:
                ans[ab[i][0] - 1] = c.pop(0)
                f(ab[i][0])

ans[0] = c.pop(0)
f(1)
print(s - m)
print(" ".join(list(map(str, ans))))

Submission status: Runtime Error

Solution code:
class Node():
    def __init__(self, p, l, r, n):
        self.p = p
        self.l = l
        self.r = r
        self.n = n


N = int(input())
T = [Node(-1, -1, -1, -1) for _ in range(N)]
S = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = min(a, b), max(a, b)
    S.append([a - 1, b - 1])
S.sort()
C = sorted(map(int, input().split()), reverse=True)
for s in S:
    if T[s[0]].l == -1:
        T[s[0]].l = s[1]
        T[s[1]].p = s[0]
    else:
        T[l].r = s[1]
        T[s[1]].p = T[l].p
    l = s[1]


def rec(n, cur):
    if n == -1:
        return cur
    T[n].n = C[cur]
    cur += 1
    cur = rec(T[n].l, cur)
    cur = rec(T[n].r, cur)
    return cur


rec(0, 0)
print(sum(C[1:]))
print(' '.join(map(str, [t.n for t in T])))

# for i, t in enumerate(T):
#     print("node: {}, parent: {}, left-child: {}, right-sibling: {}, N: {}"
#           .format(i, t.p, t.l, t.r, t.n))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from collections import deque



## input
N = int(input())
tr = [set() for _ in range(N)]
for _ in range(N-1):
  a,b = map(int, input().split())
  tr[a-1].add(b-1)
  tr[b-1].add(a-1)
costs = sorted(list(map(int, input().split())), reverse=True)

## solve
root = 0
for i in range(N):
  if len(tr[root]) < len(tr[i]):
    root = i
tr[root].add(-1)

idx = deque()
def make_tr(rt,p):
  idx.append(p)
  tr[p].remove(rt)
  for q in tr[p]:
    make_tr(p,q)

make_tr(-1,root)

ans = [None for _ in range(N)]
j = 0
for i in idx:
  ans[i] = costs[j]
  j += 1

## output
print(sum(costs[1:]))
for c in ans:
  print(c,end=" ")
print()

Submission status: Runtime Error

Solution code:
N = int(input())
ab = list(list(map(int,input().split())) for i in range(N-1))
c = list(map(int,input().split()))
c.sort(reverse=True)
tree = [[-1]for i in range(N)]
for a,b in ab:
    tree[a-1].append(b)
    tree[b-1].append(a)
def func(l):
    if tree[l-1][0] != -1:
        return
    tree[l-1][0] = c.pop(0)
    for i in tree[l-1][1:]:
        func(i)
func(1)
for i in tree:
    print(i[0],end = " ")

Submission status: Runtime Error

Solution code:
from operator import itemgetter
from heapq import heappush, heappop
from collections import deque
from collections import defaultdict
N = int(input())
l = []
p = [0]*N
lp = [0]*(N-1)
d =defaultdict(list)
for i in range(N-1):
    ta ,tb = map(int,input().split())
    l.append([ta-1,tb-1])    
li = list(map(int,input().split()))



for i,j in l:
    d[i].append([j,li[j]])
    d[j].append([i,li[i]])
q = deque()
q.append(0)
p[0] = 1
c = li[0]
ll = []
while q:
    t = q.pop()
    c = li[t]
    p[t] = 1
    for i ,j in d[t]:
        if p[i] == 0:
            ll.append(min(c,j))
            lp[t] = c
            q.appendleft(i)
print(sum(ll))
print(*li)

Submission status: Runtime Error

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

M = sum(C[:-1])

adjacent_dict={}
for a,b in AB:
  adjacent_dict.setdefault(a, set()).add(b)
  adjacent_dict.setdefault(b, set()).add(a)
  

leafs = []
adjacents = [0] * (N+1) # a[i]: 頂点i
for k, v in adjacent_dict.items():
  adjacents[k] = len(v)
  if len(v)==1:
    leafs.append(k)

nodes = leafs.copy() #小さい値を入れたい順のノード
visited = [0] * (N+1) # visited[i]: 頂点i
for n in nodes:
  visited[n] = 1
  
stack = leafs.copy()
while stack:
  new_stack=[]
  for v in stack:
    for u in adjacent_dict[v]:
      adjacents[u] -= 1
      if visited[u]==0:
        visited[u]=1
        nodes.append(u)
        new_stack.append(u)
  stack = [v for v in new_stack if adjacents[v]==0]
  
ans = [0]*(N)
for i in range(N):
  ans[nodes[i]-1] = C[i]
  
print(M)
print(*ans)

Submission status: Runtime Error

Solution code:
N = int(input())

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

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

c_list.sort()

d_list = [(len(table[i]), i) for i in range(N)]
d_list.sort()
i_list = [d_list[i][1] for i in range(N)]

scores = [None] * N
for i, s in zip(i_list, c_list):
	scores[i] = s

tree_top = 0
if N > 1:
	while len(table[tree_top]) == 1:
		tree_top = table[tree_top][0]

score = 0
def calc(cur, parent):
	global score
	s1 = scores[cur]
	for v in table[cur]:
		if v != parent:
			s2 = scores[v]
			if s1 < s2:
				score += s1
			else:
				score += s2
			calc(v, cur)

calc(tree_top, None)
print(score)
print(" ".join([str(s) for s in scores]))

Submission status: Runtime Error

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

n = int(input())
ab = [[ (int(i)-1) for i in input().split()] for i in range(n-1)]
c = sorted([int(i) for i in input().split()], reverse=True)

if n==1:
    print(0)
    print(c[0])
    exit()
    
dic = {}
for i in range(n):
    dic[i] = []

cnt = [0]*n
for a,b in ab:
    dic[a].append(b)
    dic[b].append(a)
    cnt[a] += 1
    cnt[b] += 1

c_idx = 0
res = 0
res_arr = [""]*n
used = [0]*n
def f(idx):
    global c_idx, res, used
    used[idx] = 1
    res_arr[idx] = str(c[c_idx])
    for x in dic[idx]:
        if used[x] == 0:
            c_idx += 1
            res += c[c_idx]
            f(x)

f(cnt.index(1))
print(res)
print(" ".join(res_arr))

Submission status: Runtime Error

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

n = int(input())
ab = [[ (int(i)-1) for i in input().split()] for i in range(n-1)]
c = sorted([int(i) for i in input().split()], reverse=True)

dic = {}
for i in range(n):
    dic[i] = []

cnt = [0]*n
for a,b in ab:
    dic[a].append(b)
    dic[b].append(a)
    cnt[a] += 1
    cnt[b] += 1

c_idx = 0
res = 0
res_arr = [""]*n
used = [0]*n
def f(idx):
    global c_idx, res, used
    used[idx] = 1
    res_arr[idx] = str(c[c_idx])
    for x in dic[idx]:
        if used[x] == 0:
            c_idx += 1
            res += c[c_idx]
            f(x)

f(cnt.index(1))
print(res)
print(" ".join(res_arr))

Submission status: Runtime Error

Solution code:
n = int(input())
from collections import defaultdict
graph = defaultdict(list)
edge = []
for i in range(n-1):
  a, b = list(map(int, input().split()))
  edge.append((a, b))
  graph[a].append(b)
  graph[b].append(a)
c = list(map(int, input().split()))
c.sort(reverse=True)
visited = [0 for i in range(n+1)]
ans = [0 for i in range(n+1)]
score = 0

def dfs(x):
  visited[x] = 1
  for next_ in graph[x]:
    if visited[next_]:
      continue
    dfs(next_)
  if all(visited[i] for i in graph[x]):
    ans[x] = c.pop()
    return
  visited[x] = 0

dfs(1)
for a, b in edge:
  score += min(ans[a], ans[b])
print(score)
print(*ans[1:])

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())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

height = [None for _ in range(n)]
root = 0
height[root] = 0

def build(node):
    for to in edges[node]:
        if height[to] == None:
            height[to] = height[node] + 1
            build(to)

build(root)

enum = [(-h, i) for i, h in enumerate(height)]
enum.sort()

score = 0
tree = [None] * n
clst = sorted(map(int, input().split()))

for c, hi in zip(clst, enum):
    h, i = hi
    tree[i] = c

print(sum(clst[:-1]))
print(*tree)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

Int n, u, v;
vector<Int> edge[1080000];
Int a[1080000];
Int ans[1080000];
Int p;
void dfs(Int x, Int last = -1){
    ans[x] = a[p--];
    for(auto to:edge[x]){
        if(to == last)continue;
        dfs(to, x);
    }
}


int main(){
    cin >> n;
    for(int i = 0;i < n-1;i++){
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    for(int i = 0;i < n;i++)cin >> a[i];
    p = n-1;
    sort(a, a + n);
    dfs(1);
    Int res = 0;
    for(int i = 0;i < n-1;i++)res += a[i];
    cout << res << endl;
    for(int i = 1;i <= n;i++)cout << ans[i] << " ";
    cout << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
def main():

    import sys
    input = sys.stdin.readline
    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(map(int,input().split()))

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

Solution code:
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: Runtime Error

Solution code:
N = int(input())

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

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

c_list.sort()
c_list.reverse()

ds = [(len(table[i]), i) for i in range(N)]
ds.sort()
i_list = [ds[i][1] for i in range(N - 1, -1, -1)]

scores = [None] * N
for i, s in zip(i_list, c_list):
	scores[i] = s

tree_top = 0
while len(table[tree_top]) == 1:
	tree_top = table[tree_top][0]

score = 0
def calc(cur, parent):
	global score
	s1 = scores[cur]
	for v in table[cur]:
		if v != parent:
			s2 = scores[v]
			if s1 < s2:
				score += s1
			else:
				score += s2
			calc(v, cur)

calc(tree_top, None)
print(score)
print(" ".join([str(s) for s in scores]))

Submission status: Runtime Error

Solution code:
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=' ')