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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

n = int(input())
ch = [[0,i] for i in range(n)]
graph = [[] for i in range(n)]

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

use =[0 for i in range(n)]

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

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

stack = [ch[0][1]]
count = 1
use[ch[0][1]] = 1
ans[ch[0][1]] = c[0]
while len(stack) > 0:
    now = stack.pop()
    data = graph[now]
    for i in data:
        if use[i] == 0:
            use[i] = 1
            ans[i] = c[count]
            count += 1
            stack.append(i)




print(sum(c)-c[0])
for i in ans:
    print(i,end=' ')

print()

Submission status: Accepted

Solution code:
import numpy as np
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
def rec(start, p):
    if ans[start] != -1:
        return p
    ans[start] = C[p]
    p += 1
    for node in tree[start+1]:
        p = rec(node-1, p)
    return p

N = int(input())
tree = defaultdict(list)
degree = [0 for i in range(N)]
edges = [0 for i in range(N-1)]
for i in range(N-1):
    a, b = map(int, input().split())
    edges[i] = (a, b)
    tree[a].append(b)
    tree[b].append(a)
for k, v in tree.items():
    degree[k-1] = len(v)
# print(degree)
sort_i = np.argsort(degree)[::-1]
# max_di = sort_i[-1]
# print(sort_i)
C = list(map(int, input().split()))
C = sorted(C, reverse=True)
# C = list(sorted(zip(sorted(C), list(sort_i)),key=lambda x: x[1]))
# print(C[sort_i])
ans = 0
visited_e = []
# start = max_di + 1
visited = [False for i in range(N)]
p = 0
ans = [-1 for i in range(N)]
M = 0

rec(sort_i[0], p)

for e in edges:
    M += min(ans[e[0]-1], ans[e[1]-1])
    # print(ans)
print(M)
print(' '.join(list(map(lambda x: str(x), ans))))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import heapq
INF = float("inf")


def argmax(a):
    m, n = -(1 << 31), -1
    for i, v in enumerate(a):
        if m < v:
            m, n = v, i
    return n


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])  # 無向グラフを仮定。逆向きにも辺を張る

        pass


def shortestPath(g: Graph, s: int):
    """ グラフgにおいて、始点sから各頂点への最短路を求める
    引数
    g: グラフ, s: 始点
    返り値
    dist: 始点からの距離が格納されたリスト
    prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    """
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    g = Graph(N)
    for _f, _t in zip(a, b):
        g.add_edge([_f-1, _t-1])
    dist, prev = shortestPath(g, 0)
    s = argmax(dist)
    dist, prev = shortestPath(g, s)
    g = argmax(dist)

    c.sort()

    # print(dist, prev)
    ans = -1
    haichi = [0]*N
    while True:
        haichi[g] = c.pop()
        if ans == -1:
            ans = 0
        else:
            ans += haichi[g]
        if prev[g] == None:
            break
        else:
            g = prev[g]
    # 残っている箇所はスタートから近い順に埋めていく。
    buf = []
    for i in range(N):
        if haichi[i] == 0:
            buf.append(i)
    buf.sort(key=lambda x: dist[x])
    for b in buf:
        haichi[b] = c.pop()
        ans += haichi[b]
    print(ans)
    print(*haichi)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]"
    b = [int()] * (N-1)  # type: "List[int]"
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    c = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a, b, c)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

from queue import PriorityQueue

def readInts():
  return [int(s) for s in input().split(" ")]

def main():
  N = readInts()[0]
  counts = [0 for _ in range(N)]
  edges = [[] for _ in range(N)]

  maxP = 0

  A = [0 for _ in range(N-1)]
  B = [0 for _ in range(N-1)]

  for i in range(N-1):
    A[i], B[i] = readInts()
    a, b = A[i] - 1, B[i] - 1
    counts[a] += 1
    counts[b] += 1
    if counts[a] > counts[maxP]:
      maxP = a
    if counts[b] > counts[maxP]:
      maxP = b

    edges[a].append(b)
    edges[b].append(a)

  c = readInts()
  c.sort(reverse=True)
  cursor = 0
  ans = [0 for _ in range(N)]

  visited = [False for _ in range(N)]

  queue = PriorityQueue()
  queue.put( (-1 * counts[maxP], maxP) )
  while not queue.empty():
    _, n = queue.get()
    ans[n] = c[cursor]
    cursor += 1
    visited[n] = True

    for p in edges[n]:
      if not visited[p]:
        queue.put( (-1 * counts[p], p) )

  s = 0
  for i in range(N-1):
    a, b = A[i] - 1, B[i] - 1
    s += min(ans[a], ans[b])

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

if __name__ == "__main__":
  main()

Submission status: Accepted

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

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

d_table = {}
d_rev = [None] * N
for i in range(N):
	d = len(table[i])
	if d in d_table:
		d_table[d].add(i)
	else:
		d_table[d] = {i}
	d_rev[i] = d

scores = [None] * N
for i in range(N):
	if i in d_table:
		n_set = d_table[i]
		while n_set:
			n = n_set.pop()
			scores[n] = c_list.pop()
			for n2 in table[n]:
				d = d_rev[n2]
				d_rev[n2] = d - 1
				n_set2 = d_table[d]
				if n2 in n_set2:
					n_set2.remove(n2)
					if d - 1 in d_table:
						d_table[d - 1].add(n2)
					else:
						d_table[d - 1] = {n2}

for i in range(N):
	if scores[i] == None:
		scores[i] = c_list[0]

score = 0
stack = [0]
visited = set()
visited.add(0)
while stack:
	cur = stack.pop()
	s1 = scores[cur]
	for n in table[cur]:
		if not n in visited:
			s2 = scores[n]
			if s1 < s2:
				score += s1
			else:
				score += s2
			stack.append(n)
			visited.add(n)

print(score)
print(" ".join([str(s) for s in scores]))

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)
        self.node = defaultdict(int)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def get_nodes(self):
        return self.graph.keys()

def getlist():
	return map(int, input().split())


G = Graph()
N = int(input())
for i in range(N - 1):
	a, b = getlist()
	G.add_edge(a - 1, b - 1)
	G.add_edge(b - 1, a - 1)
	G.node[a - 1] += 1
	G.node[b - 1] += 1

c = getlist()
c = sorted(c)

cnt = []
for i in G.node:
	cnt.append([G.node[i], i])

D = defaultdict(int)
Q = deque()
for i in G.node:
	if G.node[i] == 1:
		Q.append(i)


val = 0
while Q:
	x = Q.popleft()
	D[x] = c[val]
	val += 1
	for i in G.graph[x]:
		G.node[i] -= 1
		if G.node[i] == 1:
			Q.append(i)




M = sum(c) - c[-1]
print(M)

ansL = []
for i in range(N):
	ansL.append(D[i])

ansL = list(map(str, ansL))
print(" ".join(ansL))

Submission status: Accepted

Solution code:
n = int(input())
x= [[] for _ in range(n+1)]
c = [0 for _ in range(n+1)]
flag = n
for i in range(n-1):
  ai,bi = map(int,input().split())
  x[ai].append(bi)
  x[bi].append(ai)
  c[ai] += 1
  c[bi] += 1
cc = list(map(int,input().split()))
cc.sort(reverse=True)
print(sum(cc[1:]))
d = [0 for _ in range(n+1)]
e = [i for i in range(1,n+1)]
flag = 1
while flag <= n-1 :
  for i in e:
    if c[i] == 1:
      d[i] = flag
      flag += 1
      e.remove(i)
      c[i] = 0
      j = x[i][0]
      x[j].remove(i)
      c[j] -= 1
for i in range(1,n+1):
  print(cc[-d[i]],end=" ")

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
eg = []
v_cnt = [0 for i in range(N)]
v_to = [[] for i in range(N)]
v_ans = [0 for i in range(N)]
v_visited = [False for i in range(N)]

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

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

v_m = 0
for i in range(N):
    if v_m < v_cnt[i]:
        v_m = i

q = deque([v_m])
while len(q) > 0:
    i = q.popleft()

    v_ans[i] = c.pop()
    v_visited[i] = True
    for ni in v_to[i]:
        if not v_visited[ni]:
            q.append(ni)

ans = 0
for a, b in eg:
    ans += min(v_ans[a], v_ans[b])

print(ans)
print(*v_ans)

Submission status: Accepted

Solution code:
import copy
import queue
q = queue.Queue()
n = int(input())

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

def bfs():
    start = 0
    valid = [1]*100001
    q.put((start,0)) 
    valid[start] = 0
    level[start][1] = 0
    while not q.empty():
        p,d = q.get()
        for nei in neib[p]:
            if valid[nei]:
                valid[nei]=0
                level[nei][1] = d+1
                q.put((nei,d+1))
bfs()

level.sort(key = lambda x:x[1])
c = list(map(int,input().split()))
c.sort(reverse=True)
res = 0
for i in range(n):
    level[i].append(c[i])
    res += c[i]
res -= c[0]
print(res)
level.sort(key = lambda x:x[0])
for i in range(n):
    print(level[i][2],end=" ")
print("")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

N=int(input())

L=[[]for i in range(N+1)]
C=[0 for i in range(N+1)]
for i in range(N-1):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)
    C[a]+=1
    C[b]+=1
M=0
m=0
for i in range(1,N+1):
    if len(L[i])>m:
        m=len(L[i])
        M=i
C=list(map(int,input().split()))
C.sort(reverse=True)
#print(C)
l=[-1 for i in range(N+1)]
l[M]=0

X=[0 for i in range(N+1)]
X[M]=C[0]
cnt=1
def dfs(x):
    for i in L[x]:
        if l[i]==-1:
            l[i]=l[x]+1
            global cnt
            X[i]=C[cnt]
            cnt+=1
            dfs(i)
dfs(M)
#print(l)
#print(X)
print(sum(X)-max(X))
ans=str(X[1])
for i in range(2,N+1):
    ans+=" "+str(X[i])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


N = int(input())
branch = [0] * (N - 1)
for i in range(N-1):
    branch[i] = list(map(int, input().split()))
C = list(map(int, input().split()))
C.sort(reverse=True)
M = sum(C[1:])

adj = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = branch[i]
    adj[a].append(b)
    adj[b].append(a)

ans = [-1] * (N+1)
deq = deque()
deq.appendleft(1)
while len(deq) > 0:
    v = deq.pop()
    ans[v] = C.pop(0)
    for u in adj[v]:
        if ans[u] == -1:
            deq.appendleft(u)

print(M)
print(' '.join(map(str, ans[1:])))

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 7)
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: Accepted

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

n = inn()
edges = []
dst = [ [] for i in range(n) ]
for i in range(n-1):
    a,b = inm()
    a -= 1
    b -= 1
    dst[a].append(b)
    dst[b].append(a)
    edges.append((a,b))
c = inl()

c.sort(reverse=True)
labs = [-1] * n
q = []
for i in range(n):
    if len(dst[i]) == 1:
        q.append(i)

while(len(q)>1):
    i = q.pop()
    labs[i] = c.pop()
    d = dst[i][0]
    dst[d].remove(i)
    if len(dst[d]) == 1:
        q.append(d)

i = q.pop()
labs[i] = c.pop()

m = 0
for z in edges:
    m += min(labs[z[0]], labs[z[1]])
print(m)
for i in range(n):
    printn(str(labs[i]) + ' ')
print("")

Submission status: Accepted

Solution code:
from collections import deque
 

N = int(input())
edge = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  edge[a-1] += [b-1]
  edge[b-1] += [a-1]
A = list(map(int, input().split()))
A.sort(reverse = 1)
print(sum(A[1:]))

ans = [[0, A[0]]]#0番目の頂点には最大値を入れる
cnt = 1#頂点数
visited = [1] + [0]*(N-1)#訪問フラグ
que = deque([0]) 
while que:
  u = que.pop()
  for v in edge[u]:
    if visited[v] == 0:#未訪問なら値を入れる
      que.append(v)
      visited[v] = 1
      ans += [[v,A[cnt]]]
      cnt += 1
ans.sort()

ans2 = []
for i in range(N):
  ans2 += [ans[i][1]]
print(' '.join(map(str, ans2)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(1000000)

n = int(input())
d = [0] * n
a = []
b = []
connected = [[] for _ in range(n)]
for i in range(n - 1):
    ai, bi = list(map(int, input().split()))
    d[ai-1] += 1
    d[bi-1] += 1
    a.append(ai-1)
    b.append(bi-1)
    connected[ai-1].append(bi-1)
    connected[bi-1].append(ai-1)
# 次数
c = list(map(int, input().split()))
parents = [-1] * n
result = [0] * n
sortedc = sorted(c, reverse=True)

def dfs(current, parent):
    parents[current] = parent
    parent = parents[current]
    for i in connected[current]:
        if i != parent:
            dfs(i, current)

# 深さ+次数優先
def ddfs(current):
    result[current] = sortedc.pop(0)
    nexts = []
    for i in connected[current]:
        if parents[current] != i:
            nexts.append((i, d[i]))
    sortedNexts = sorted(nexts, reverse=True, key=lambda x: x[1])

    for nxt, _ in sortedNexts:
        ddfs(nxt)

def main():

    dandi = []
    for i, di in enumerate(d):
        dandi.append((i, di))
    sortedd = sorted(dandi, reverse=True, key=lambda x: x[1])

    root = sortedd[0][0]
    dfs(root, -1)
    ddfs(root)

    resultSum = 0
    for i in range(n-1):
        resultSum += min(result[a[i]], result[b[i]])
    print(resultSum)
    print(' '.join(map(str, result)))



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
E = [[] for _ in range(N)]
for a, b in [[int(i) - 1 for i in input().split()] for _ in range(N - 1)]:
    E[a].append(b)
    E[b].append(a)
C = [int(i) for i in input().split()]
C.sort(reverse=True)

ans = [0] * N

def bfs(i):
    cur = 0
    Q = deque()
    Q.append(0)
    visited = [False] * N
    while Q:
        v = Q.popleft()
        visited[v] = True
        ans[v] = C[cur]
        cur += 1
        for e in E[v]:
            if visited[e]:
                continue
            Q.append(e)

bfs(0)
print(sum(C[1:]))
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
N = int(input())
G = [[] for i in range(N)]
deg = [0] * N
E = []
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)
    E.append((a, b))
    deg[a] += 1
    deg[b] += 1

C = list(map(int, input().split()))
C = sorted(C)
que = deque()
for i in range(N):
    if deg[i] == 1:
        que.append(i)

D = [-1] * N
used = [0] * N
i = 0
while i < N:
    k = que.popleft()
    D[k] = C[i]
    i += 1
    for w in G[k]:
        deg[w] -= 1
        if deg[w] == 1:
            que.append(w)

ans = 0
for i in range(len(E)):
    ans += min(D[E[i][0]], D[E[i][1]])

print(ans)
print(*D)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
s = [set() for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    s[a - 1].add(b - 1)
    s[b - 1].add(a - 1)
c = list(map(int, input().split()))
c.sort(reverse=True)
ans = [0] * N
ans[0] = c[0]
cp = 1
i = 0
pre = -1
dq = deque()
while True:
    for x in s[i]:
        if x != pre:
            ans[x] = c[cp]
            cp += 1
            dq.appendleft((x, i))
    if dq:
        i, pre = dq.pop()
    else:
        break

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

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    n = get_int()
    a, b = get_data(n-1, [int, int])
    c = get_li()
    c.sort()
    node2children = defaultdict(set)
    for ai, bi in zip(a, b):
        node2children[ai].add(bi)
        node2children[bi].add(ai)
    leaves = deque()
    for node, children in node2children.items():
        if len(children) == 1:
            leaves.append(node)
    sequence = []
    score = 0
    i = 0
    while len(leaves) > 0:
        node = leaves.popleft()
        sequence.append(node)
        if len(node2children[node]) == 0:
            break
        score += c[i]
        i += 1
        parent = node2children[node].pop()
        node2children[parent].discard(node)
        if len(node2children[parent]) == 1:
            leaves.append(parent)
    print(score)
    print(" ".join(
        map(
            lambda x: str(x[1]),
            sorted(
                enumerate(c),
                key=lambda x: sequence[x[0]]
            )
        )
    ))
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


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


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
edge=[list(map(int,input().split())) for i in range(N-1)]
C=list(map(int, input().split()))
from heapq import heapify,heappop
for i in range(N):
    C[i]=-C[i]
heapify(C)
c=[[] for i in range(N)]
for i,j in edge:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
d=[-1]*N
d[0]=-heappop(C)
v=[0]*N
v[0]=1
SUM=d[0]
import sys
sys.setrecursionlimit(10**5)
def dfs(p,v,d):
    global SUM
    for n in c[p]:
        if v[n]==0:
            d[n]=-heappop(C)
            SUM+=d[n]
            v[n]=1
            dfs(n,v,d)
dfs(0,v,d)
print(SUM-d[0])
for i in range(N-1):
    print(d[i],end=' ')
print(d[N-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from operator import itemgetter
from heapq import heappop, heappush
def solve(): 
    N = int(input())
    E = [[] for i in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        E[a].append(b)
        E[b].append(a)
    C = list(map(int, input().split()))
    C.sort(reverse=True)
    D = ['' for i in range(N+1)]
    j = 1
    hq = [(0,1)]
    checked = []
    while hq:
        _j ,n = heappop(hq)
        checked.append(n)
        D[n] = str(C[_j])
        for m in E[n]:
            if not m in checked:
                heappush(hq, (j, m))
                j += 1
    res = str(sum(C[1:])) + '\n' +' '.join(D[1:])
    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
import numpy as np
from collections import defaultdict
from functools import reduce
import queue

# s = input()
n = int(input())

edges = defaultdict(set)

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

q = queue.Queue()

for node, li in edges.items():
    if len(li) == 1:
        q.put(node)

C = sorted(list(map(int, input().split())))
c_idx = 0

res = np.zeros(n, dtype=int)

while not q.empty():
    node = q.get()
    if res[node] != 0:
        continue
    res[node] = C[c_idx]
    c_idx += 1

    if len(edges[node]) > 0:
        n2 = edges[node].pop()
        edges[n2].remove(node)
        if len(edges[n2]) == 1:
            q.put(n2)

print(sum(C[:n-1]))
print(*res)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!


from collections import deque
 
N = int(input())
 
edges = [[] for _ in range(N)]
 
for i in range(N-1):
    u, v = map(int, input().rstrip().split(' '))
    u = u - 1
    v = v - 1
    
    edges[u].append(v)
    edges[v].append(u)
    
X = sorted(list(map(int, input().rstrip().split(' '))), key=lambda x: -x)

temp = deque([0])
 
vertices = [-1] * N
count_vertices = 0
value = 0
while len(temp) > 0:
    a = temp.popleft()
    vertices[a] = X[count_vertices]
    count_vertices += 1
    
    for edge in edges[a]:
        if vertices[edge] == -1:
            temp.append(edge)
 
print(sum(X[1:]))
print(' '.join(list(map(str, vertices))))

Submission status: Accepted

Solution code:
N=int(input())
from collections import defaultdict,deque
B=[tuple(map(int,input().split())) for i in range(N-1)]
branch=defaultdict(set)
for a,b in B:
    branch[a-1]|={b-1}
    branch[b-1]|={a-1}
C=list(map(int,input().split()))
cnt=[len(branch[i]) for i in range(N)]
M=0
start=-1
for i in range(N):
    if M<len(branch[i]):
        M=len(branch[i])
        start=i
C.sort(reverse=True)
idx=0
ans=[0]*N
check=deque([start])
while len(check)>0:
    now=check.popleft()
    ans[now]=C[idx]
    idx+=1
    nex=[(i,len(branch[i])) for i in branch[now] if ans[i]==0]
    nex.sort(key=lambda x:x[1],reverse=True)
    check+=deque([i[0] for i in nex])
res=0
for a,b in B:
    res+=min(ans[a-1],ans[b-1])
print(res)
print(" ".join(list(map(str,ans))))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
#from queue import Queue


def solve(N: int, a: "List[int]", b: "List[int]", C: "List[int]"):
    conn = [[] for _ in range(N)]
    for i in range(N - 1):
        conn[a[i] - 1].append(b[i] - 1)
        conn[b[i] - 1].append(a[i] - 1)
    #counts = [Queue() for _ in range(N)]
    counts = [[] for _ in range(N)]
    for i in range(N):
        l = len(conn[i])
        #counts[l].put([i, conn[i]])
        counts[i] = [len(conn[i]), conn[i], 0, i]
    #counts.sort(key=lambda x: x[0])

    ret = 0
    #print(counts)
    C.sort()
    idx = 0
    while idx < N:
        for cnt in counts:
            if cnt[2] == 0 and cnt[0] <= 1:
                cnt[2] = C[idx]
                idx += 1
                for node in cnt[1]:
                    counts[node][0] -= 1
            ##ret += C[i] * cnt[0]
    vals = [0] * N
    for cnt in counts:
        vals[cnt[3]] = cnt[2]
    for i in range(N - 1):
        ret += min(vals[a[i] - 1], vals[b[i] - 1])
    print(ret)
    print(' '.join([str(v) for v in vals]))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]" 
    b = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    c = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, a, b, c)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
A=[0 for i in range(N-1)]
B=[0 for i in range(N-1)]
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    A[i],B[i]=a,b
    G[a].append(b)
    G[b].append(a)
j=0
for i in range(N):
    if len(G[i])>len(G[j]):
        j=i
c=sorted([int(i) for i in input().split()])
d=[-1 for i in range(N)]
q=deque([j])
while(len(q)>0):
    r=q.popleft()
    d[r]=c.pop()
    for p in G[r]:
        if d[p]==-1:
            q.append(p)
M=0
for i in range(N-1):
    M+=min(d[A[i]],d[B[i]])
print(M)
print(" ".join([str(i) for i in d]))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


n = ni()
edges = [tuple(li_()) for _ in range(n-1)]
c = list(li())
c.sort()

visited = [False]*n

graph = [[] for _ in range(n)]
for l, r in edges:
    graph[l].append(r)
    graph[r].append(l)

cnt = 0
num = [0]*n

def dfs(node, graph):
    global cnt
    visited[node] = True
    for nei in graph[node]:
        if not visited[nei]:
            dfs(nei, graph)

    num[node] = c[cnt]
    cnt += 1

dfs(0, graph)

ans = 0
for l, r in edges:
    ans += min(num[l], num[r])

print(ans)
print(*num)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify, heappop

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

start = None
for i in range(n):
    if len(edge[i]) == 1:
        start = i
        break

visited = [0]*n
q = deque()
q.append((start))
while q:
    now = q.pop()
    if visited[now]:
        continue
    a = heappop(cc)
    visited[now] = -a
    for i in edge[now]:
        if not visited[i]:
            q.append(i)
print(sum(c) - max(c))
print(*visited)