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
from collections import deque
sys.setrecursionlimit(10**9)

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

score = sum(C) - max(C)
C.sort(reverse=True)
C = deque(C)
con = [[] for _ in range(N + 1)]
ans = [0 for i in range(N + 1)]

for ab in AB:
    a, b = ab
    con[a].append(b)
    con[b].append(a)


def dfs(x):
    if len(C) == 0:
        return
    if ans[x] == 0:
        ans[x] = C[0]
        C.popleft()
        for c in con[x]:
            dfs(c)


dfs(1)
ans = list(map(str, ans))
print(score)
print(' '.join(ans[1:]))

Submission status: Accepted

Solution code:
*D, = open(0)
n = int(D[0])

edge = [[] for _ in range(n+1)]
v_val = [0 for _ in range(n+1)]

dist = {}

for i in range(1, n):
    a, b = map(int, D[i].split())
    edge[a].append(b)
    edge[b].append(a)
c = list(map(int, D[n].split()))
c = sorted(c, reverse=True)

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

        
import sys
sys.setrecursionlimit(10**7)


def visit(edge, start, visited, order):
    visited[start] = True
    order.append(start)
    
    for node in edge[start]:
        if not visited[node]:
            visit(edge, node, visited, order)
    
    return 

visited = [False for _ in range(len(edge))]
order = []
visit(edge, start, visited, order)

# calculate cost
v_val = [0 for _ in range(len(c)+1)]
for i, it in enumerate(order):
    v_val[it] = c[i]
    
print(sum(c[1:]))
print(' '.join(map(str, v_val[1:])))

Submission status: Accepted

Solution code:
*D, = open(0)
n = int(D[0])
 
edge = [[] for _ in range(n+1)]
v_val = [0 for _ in range(n+1)]
 
dist = {}
 
for i in range(1, n):
    a, b = map(int, D[i].split())
    edge[a].append(b)
    edge[b].append(a)
c = list(map(int, D[n].split()))
 
c = sorted(c, reverse=True)
 
# 木の端を求める
def findLeaf(edge, start=1):
    visited = [False for _ in range(len(edge))]
    next_v = edge[start]
    visited[start] = True
    count = 0
    
    while len(next_v) > 0:
        new_v = []
        for it in next_v:
    #         print(it)
            leaf = it
            for v in edge[it]:
                if not visited[v]:
                    new_v.append(v)
            visited[it] = True
        next_v = new_v
        count += 1
 
    return leaf, count
 
 
# 木の直径を求める
def findD(edge):
    leaf, _ = findLeaf(edge, 1)
    leaf, count = findLeaf(edge, leaf)
    return count
 
# 木の中心を求める
def findCenter(edge):
    leaf, _ = findLeaf(edge, 1)
    leaf, d = findLeaf(edge, leaf)
    r = d//2
 
    visited = [False for _ in range(len(edge))]
    start = leaf
    next_v = edge[start]
    # print(next_v, leaf)
    visited[start] = True
    count = 0
 
    while not r == count+1:
        new_v = []
        for it in next_v:
    #         print(it)
            leaf = it
            for v in edge[it]:
                if not visited[v]:
                    new_v.append(v)
            visited[it] = True
        next_v = new_v
        count += 1
        
    center = []
    for it in next_v:
        if len(edge[it]) > 1:
            center.append(it)
    return center
 
 
def calcCost(D, v_val):
    total = 0
    
    n = int(D[0])
    for i in range(1, n):
        a, b = map(int, D[i].split())
        total += min(v_val[a], v_val[b])
        
    return total
 
 
max_val = 0
max_v = 0
l, _ = findLeaf(edge)
for center in [l]:
    order = []
    start = center
    visited = [False for _ in range(len(edge))]
    next_v = edge[start]
    visited[start] = True
    order.append(center)
 
    # Get order from center
    while len(next_v) > 0:
        new_v = []
        for it in next_v:
    #         print(it)
            leaf = it
            for v in edge[it]:
                if not visited[v]:
                    new_v.append(v)
            visited[it] = True
            order.append(it)
        next_v = new_v
        
    # calculate cost
    v_val = [0 for _ in range(len(c)+1)]
    for i, it in enumerate(order):
        v_val[it] = c[i]
 
    val = calcCost(D, v_val)
    if val > max_val:
        max_val = val
        max_v = v_val
 
        
print(max_val)
print(' '.join(map(str, max_v[1:])))

Submission status: Accepted

Solution code:
*D, = open(0)
n = int(D[0])

edge = [[] for _ in range(n+1)]
v_val = [0 for _ in range(n+1)]

dist = {}

for i in range(1, n):
    a, b = map(int, D[i].split())
    edge[a].append(b)
    edge[b].append(a)
c = list(map(int, D[n].split()))
c = sorted(c, reverse=True)

from collections import deque
visited = [False for _ in range(len(edge))]
start = 1
que = deque()
que.append(start)
order = []
order.append(start)
visited[start] = True

while que:
    node = que.popleft()
    for it in edge[node]:
        if not visited[it]:
            order.append(it)
            visited[it] = True
            que.append(it)
# calculate cost
v_val = [0 for _ in range(len(c)+1)]
for i, it in enumerate(order):
    v_val[it] = c[i]

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

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

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

c_list = list(map(int, input().split()))
c_list.sort()
c_que = deque(c_list)

cnt = defaultdict(int)
outs = defaultdict(list)
for a, b in ab:
    cnt[a - 1] += 1
    cnt[b - 1] += 1
    outs[a - 1].append(b - 1)
    outs[b - 1].append(a - 1)

top = 0
tar = defaultdict(lambda: 0)

import sys

sys.setrecursionlimit(10 ** 9)
visit = [False] * N


def dfs(start):
    tmp = []
    visit[start] = True
    for v2 in outs[start]:
        if visit[v2]:
            continue
        q = c_que.pop()
        tar[v2] = q
        tmp.append(v2)
    for v2 in tmp:
        if visit[v2]:
            continue
        dfs(v2)


tar[top] = c_que.pop()
dfs(top)
ans = 0
for a, b in ab:
    a -= 1
    b -= 1
    ans += min(tar[a], tar[b])
print(ans)
for i in range(N):
    print(tar[i], end=" ")

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

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

c_list = list(map(int, input().split()))
c_list.sort()
c_que = deque(c_list)

cnt = defaultdict(int)
outs = defaultdict(list)
for a, b in ab:
    cnt[a - 1] += 1
    cnt[b - 1] += 1
    outs[a - 1].append(b - 1)
    outs[b - 1].append(a - 1)

cnt = sorted(cnt.items(), key=lambda x: x[1])
top = cnt[0][0]
tar = defaultdict(lambda: 0)

import sys

sys.setrecursionlimit(10 ** 9)
visit = [False] * N


def dfs(start):
    tmp = []
    visit[start] = True
    for v2 in outs[start]:
        if visit[v2]:
            continue
        q = c_que.pop()
        tar[v2] = q
        tmp.append(v2)
    for v2 in tmp:
        if visit[v2]:
            continue
        dfs(v2)


tar[top] = c_que.pop()
dfs(top)
ans = 0
for a, b in ab:
    a -= 1
    b -= 1
    ans += min(tar[a], tar[b])
print(ans)
for i in range(N):
    print(tar[i], end=" ")

Submission status: Accepted

Solution code:
n = int(input())
route = [[] for i in range(n)] #どの木と隣接か
for i in range(n-1):
	a,b = (x-1 for x in map(int,input().split()))
	route[a]+=[b]
	route[b]+=[a]
c = list(map(int,input().split()))
c.sort(reverse=1)

check = [False]*n #check済みか否か
ans = [0]*n #cを入れてく
cnt = 0 #何個目を見てるか、cに使う
q = [0]
# print(route)
while q:
	cur = q[0] #今どこの木を見てるか
	q = q[1:]
	check[cur] = True
	ans[cur] = c[cnt]
	cnt += 1
	for r in route[cur]:
		if check[r]:
			continue
		q.append(r)
print(sum(ans[1:]))
print(*ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as ite
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N = input()
E = [[] for i in range(N + 1)]

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

c = map(int, raw_input().split())
c.sort(reverse = True)
print sum(c[1:])

ans = [0] * (N + 1)
def func(pos, pre, id):
	ans[pos] = c[id]
	id += 1
	for to in E[pos]:
		if to != pre:
			id = func(to, pos, id)
	return id

func(1, -1, 0)
print " ".join(map(str, ans[1:]))

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())

tree = {i: set() for i in range(1, N+1)}
for i in range(N-1):
    a,b = map(int,input().split())
    tree[a].add(b)
    tree[b].add(a)

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

res = [0]*(N+1)
qu = deque([1])
res[1] = inl.pop()

while qu:
    i = qu.popleft()
    for j in tree[i]:
        if res[j] == 0:
            res[j] = inl.pop()
            qu.append(j)

print(sum(res[2:]))
for i in res[1:]:
    print(i, end=' ')
print('')

Submission status: Accepted

Solution code:

def input_from_console():
    n = int(input())
    a_list, b_list = [], []
    for i in range(n - 1):
        data = input()
        a, b = map(int, data.split())
        if b > a:
            a, b = b, a  # swap smaller one.
        a_list.append(a)
        b_list.append(b)
    c_list = list(map(int, input().split()))
    return n, a_list, b_list, c_list


def solve(n, a_list, b_list, c_list):
    edge = [[] for i in range(n)]  # 0 based list of list.
    for i in range(len(a_list)):
        a, b = a_list[i] - 1, b_list[i] - 1  # convert to 0 based index.
        edge[a].append(b)
        edge[b].append(a)
    c_list.sort(reverse=True)

    vertices = [None] * n
    vertices[0] = c_list.pop(0)

    graph_value = sum(c_list)  # edge should have the value except the maximum.

    search_path = []
    search_path.extend(edge[0])

    while search_path:
        node = search_path.pop(0)
        if vertices[node] is None:
            vertices[node] = c_list.pop(0)
            search_path.extend(edge[node])
    return "{:d}\n{}".format(graph_value, ' '.join(map(str, vertices)))


def main():
    n, a_list, b_list, c_list = input_from_console()
    print(solve(n, a_list, b_list, c_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

Submission status: Accepted

Solution code:
def input_from_console():
    n = int(input())
    a_list, b_list = [], []
    for i in range(n - 1):
        data = input()
        a, b = map(int, data.split())
        if b > a:
            a, b = b, a  # swap smaller one.
        a_list.append(a)
        b_list.append(b)
    c_list = list(map(int, input().split()))
    return n, a_list, b_list, c_list


def solve(n, a_list, b_list, c_list):
    edge = [[] for i in range(n)]  # 0 based list of list.
    for i in range(len(a_list)):
        a, b = a_list[i] - 1, b_list[i] - 1  # convert to 0 based index.
        edge[a].append(b)
        edge[b].append(a)
    c_list.sort(reverse=True)

    vertices = [None] * n
    vertices[0] = c_list.pop(0)

    graph_value = sum(c_list)  # edge should have the value except the maximum. 

    search_path = []
    search_path.extend(edge[0])

    while search_path:
        node = search_path.pop(0)
        if vertices[node] is None:
            vertices[node] = c_list.pop(0)
            search_path.extend(edge[node])
    return "{:d}\n{}".format(graph_value, ' '.join(map(str, vertices)))


def main():
    n, a_list, b_list, c_list = input_from_console()
    print(solve(n, a_list, b_list, c_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(20000000)
connection = defaultdict(lambda: [])

n = int(input())

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

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

ans = [0] * (n+1)
def dfs(num):
    ans[num] = c.pop()
    for next_num in connection[num]:
        if ans[next_num] == 0 :
            dfs(next_num)

dfs(1)

score = 0
for a, b in ab:
    score += min(ans[a], ans[b])

print(score)
print(" ".join(map(str, ans[1:])))

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(20000000)
connection = defaultdict(lambda: [])

n = int(input())

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

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

ans = [0] * (n+1)
checked_list = []
def dfs(num):
    checked_list.append(num)
    ans[num] = c.pop()
    for next_num in connection[num]:
        if next_num not in checked_list:
            dfs(next_num)

dfs(1)

score = 0

for a, b in ab:
    score += min(ans[a], ans[b])

print(score)
print(" ".join(map(str, ans[1:])))

Submission status: Accepted

Solution code:

def input_from_console():
    n = int(input())
    a_list, b_list = [], []
    for i in range(n - 1):
        data = input()
        a, b = map(int, data.split())
        if b > a:
            a, b = b, a  # swap smaller one.
        a_list.append(a)
        b_list.append(b)
    c_list = []
    c_list = list(map(int, input().split()))
    return n, a_list, b_list, c_list


def solve(n, a_list, b_list, c_list):
    edge = [[] for i in range(n)]
    for i in range(len(a_list)):
        a, b = a_list[i] - 1, b_list[i] - 1  # convert to 0 based index.
        edge[a].append(b)
        edge[b].append(a)
    c_list_new = sorted(c_list, reverse=True)

    value = sum(c_list_new[1:])

    vertices = [None] * n
    vertices[0] = c_list_new.pop(0)

    search_path = []
    search_path.extend(edge[0])

    while search_path:
        node = search_path.pop(0)
        if vertices[node] is None:
            vertices[node] = c_list_new.pop(0)
            search_path.extend(edge[node])
    return str(value) + '\n' + ' '.join(map(str, vertices))


def main():
    n, a_list, b_list, c_list = input_from_console()
    print(solve(n, a_list, b_list, c_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(20000000)
connection = defaultdict(lambda: [])

n = int(input())

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

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

ans = [0] * (n+1)

checked_list = []
def dfs(num):
    checked_list.append(num)
    ans[num] = c.pop()
    for next_num in connection[num]:
        if next_num not in checked_list:
            dfs(next_num)


l = []
for i in range(1, n+1):
    l.append([i, len(connection[i])])
l.sort(key=lambda x: x[1], reverse=True)
dfs(1)

score = 0

for a, b in ab:
    score += min(ans[a], ans[b])

print(score)
print(" ".join(map(str, ans[1:])))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())


def func(v):
    if ans[v] != -1:
        return
    ans[v] = c[index]
    global index
    index += 1
    for next_v in graph[v]:
        if v == next_v:
            continue
        func(next_v)


n = II()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = MI()
    graph[u-1].append(v-1)
    graph[v-1].append(u-1)
c = sorted(LI(), reverse=True)
ans = [-1] * n
index = 0
func(0)
print(sum(c[1::]))
for i in range(n):
    print(ans[i], end=' ')
print()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

N = int(input())
edges = [[] for i in range(N)]
for i in range(N-1):
    a, b = map(int,readline().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
C = list(map(int, readline().split()))
C.sort()
print(str(sum(C)-C[-1]))

queue = [0]
D = ["x" for i in range(N)]
while queue:
    op = queue.pop(0)
    if D[op] != "x":
        continue
    D[op] = str(C.pop(-1))
    numchild = len(edges[op])
    for i in range(numchild):
        queue.append(edges[op][i])
print((' '.join(D)))

Submission status: Accepted

Solution code:
from collections import deque
N = int( input())
E = [[] for _ in range(N)]
V = [0]*N
for _ in range(N-1):
    a, b = map( int, input().split())
    a, b = a-1, b-1
    E[a].append(b)
    E[b].append(a)
    V[a] += 1
    V[b] += 1
C = list(map( int, input().split()))
C.sort(reverse=True)
for i in range(N):
    if V[i] == 1:
        s = i
        break
q = deque([s])
V = [0]*N
l = 0
for l in range(N):
    t = q.popleft()
    V[t] = C[l]
    for v in E[t]:
        if V[v] == 0:
            q.append(v)
print( sum(C) - C[0])
print( " ".join( map( str, V)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
N = int(input())


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

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

    for i in neighbor[start]:
        
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            try:
                dfs(neighbor,i)
            except RuntimeError:
                flag = True
                return 0




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

dfs(neigh,nn)
"""
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
ans2 = ' '.join([str(ans[i]) for i in range(N)])


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

Submission status: Accepted

Solution code:
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
 
n = int(input())
g = [[]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()))
kyo = [float("inf")] * n
def dfs(x,y,z):
  kyo[x] = y
  for i in g[x]:
    if i == z:
            continue
    dfs(i,y+1,x)
dfs(0,0,-1)
kyo2 = []
for i in range(n):
        kyo2.append([kyo[i],i])
ans = [0]*n
kyo2.sort()
kyo2 = kyo2[::-1]
c.sort()
for i in range(n):
        ans[kyo2[i][1]] = c[i]
print(sum(c)-c[-1])
print(*ans)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

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

print(sum(C) - max(C))
    
Q = deque()
Q.append(N - 1)
order = []
visited = [False] * N
while len(Q) != 0:
    q = Q.popleft()
    visited[q] = True
    c = C.pop()
    order.append([q, c])
    for g in G[q]:
        if visited[g] == False:
            Q.append(g)

sorted_order = sorted(order)
ans2 = []
for i in range(N):
    ans2.append(sorted_order[i][1])
    
print(' '.join(map(str, ans2)))

Submission status: Accepted

Solution code:

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



#x = [1,2,3]
#while x:
#    if x : 
#        print(x)
#        x.pop()


n = int(input())

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

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


links = [set() for _ in range(n)]

for abi in abn:
    a, b = abi

    a -= 1; b-=1
    links[a].add(b)
    links[b].add(a)



# points of vertices
pv = [0]*n
ans = 0


#リンクを嘗めてsizeが1のもののindexだけ選ぶ
leaves = { i for i, l in enumerate(links) if len(l) == 1 }

# print(*abn)
# print(*cn)
# print(*leaves)
while leaves:
    
    index = leaves.pop()
    cmax = cn.pop()#popなので最小値から利用していく=>大きな値が残っていく
    
    pv[index] = cmax

    if not cn: # 最後のcmax (= 与えられた数列cnの最大値 )を加算する前に抜ける
        break

    ans += cmax
    for ci in links[index]:
        lu = links[ci]
        lu.remove(index)
        if len(lu) == 1:
            leaves.add(ci)

print(ans)
print(*pv)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
X = [[] for i in range(N)]
Y = [-1] * N
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

C = sorted([int(a) for a in input().split()])
print(sum(C)-max(C))

que = deque([0])
while que:
    i = deque.popleft(que)
    if Y[i] < 0:
        Y[i] = C.pop()
        for a in X[i]:
            deque.append(que, a)
print(*Y)

Submission status: Accepted

Solution code:
from queue import Queue

N = int(input())
node_array = [[] for i in range(N)]

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

c_array = sorted(map(int, input().split()), reverse=True)
ans = sum(c_array[1:])
ans_array = [-1] * N

edge = Queue()

edge.put(0)
ans_array[0] = 0

for i in range(N):
    item = edge.get()
    ans_array[item] = str(c_array[i])
    for j in node_array[item]:
        if ans_array[j] == -1:
            edge.put(j)
            ans_array[j] == 0

print(ans)
print(" ".join(ans_array))

Submission status: Accepted

Solution code:


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


from collections import deque, _heapq

n = int(input())

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

for _ in range(n-1):

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

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


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

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


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

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

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

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

        s.append( (cur,e) )

ans = ''
for i in range(1,n+1):
    ans += str( g[i]["num"] ) + " "



print( ans[:-1] )

Submission status: Accepted

Solution code:
n = int(input())
adj_path = [[] for _ in range(n)]
paths = []
for _ in range(n-1):
    a,b = map(int,input().split())
    paths.append([a,b])
    adj_path[a-1].append(b-1)
    adj_path[b-1].append(a-1)
c_list = sorted(list(map(int,input().split())),reverse=True)
out = [0 for i in range(n)]
que = [[0,adj_path[0]]]
visited = []
cnt = 0
while(que):
    node_num,children = que.pop(0)
    visited.append(node_num)
    out[node_num] = c_list[cnt]
    cnt += 1
    for child in children:
        if child not in visited:
            que.append([child,adj_path[child]])
score = 0
for path in paths:
    a,b = path
    score += min(out[a-1],out[b-1])
print(score)
print(" ".join(str(x) for x in out))

Submission status: Accepted

Solution code:
from scipy.sparse import*
n,*t=map(int,open(0).read().split())
c=sorted(t[-n:])[::-1]
f=find(c)[0]
f[csgraph.depth_first_order(csr_matrix((f[1:],(t[:-n:2],t[1:-n:2])),[n+1]*2),1,0,0)-1]=c
print(sum(c[1:]),*f)

Submission status: Accepted

Solution code:
import sys;sys.setrecursionlimit(10**6)
    #双方向に連結しろ！！！！！！！
from collections import *
    #双方向に連結しろ！！！！！！！
d=defaultdict(list)
    #双方向に連結しろ！！！！！！！
n=int(input())
    #双方向に連結しろ！！！！！！！
start=2
    #双方向に連結しろ！！！！！！！
for i in range(n-1):
    #双方向に連結しろ！！！！！！！
    a,b=map(int,input().split())
    #双方向に連結しろ！！！！！！！
    d[a].append(b)
    #双方向に連結しろ！！！！！！！
    d[b].append(a)
    #双方向に連結しろ！！！！！！！
    start=min(start,a)
    #双方向に連結しろ！！！！！！！
*p,=sorted(map(int,input().split()))
    #双方向に連結しろ！！！！！！！
ans=[0 for i in range(n)]
    #双方向に連結しろ！！！！！！！
def DFS_dict(point,TFlist):
    #双方向に連結しろ！！！！！！！
    if all(TFlist):
    #双方向に連結しろ！！！！！！！
        return 1
    #双方向に連結しろ！！！！！！！
    for i in d[point]:
    #双方向に連結しろ！！！！！！！
        if TFlist[i-1]:
    #双方向に連結しろ！！！！！！！
            continue
    #双方向に連結しろ！！！！！！！
        TFlist[i-1]=True
        ans[i-1]=p.pop()
    #双方向に連結しろ！！！！！！！
        DFS_dict(i,TFlist)
    #双方向に連結しろ！！！！！！！
        TFlist[i-1]=False
    #双方向に連結しろ！！！！！！！
    return ans
    #双方向に連結しろ！！！！！！！
TFlist=[False]*n
    #双方向に連結しろ！！！！！！！
TFlist[start-1]=True
    #双方向に連結しろ！！！！！！！
score=sum(p)-max(p)
    #双方向に連結しろ！！！！！！！
ans[start-1]=p.pop()
    #双方向に連結しろ！！！！！！！
ans=DFS_dict(start,TFlist)
    #双方向に連結しろ！！！！！！！
print(score)
    #双方向に連結しろ！！！！！！！
print(*ans)

Submission status: Accepted

Solution code:
import sys;sys.setrecursionlimit(10**6)
    #双方向に連結しろ！！！！！！！
from collections import *
    #双方向に連結しろ！！！！！！！
d=defaultdict(list)
    #双方向に連結しろ！！！！！！！
n=int(input())
    #双方向に連結しろ！！！！！！！
start=float("inf")
    #双方向に連結しろ！！！！！！！
for i in range(n-1):
    #双方向に連結しろ！！！！！！！
    a,b=map(int,input().split())
    #双方向に連結しろ！！！！！！！
    d[a].append(b)
    #双方向に連結しろ！！！！！！！
    d[b].append(a)
    #双方向に連結しろ！！！！！！！
    start=min(start,a)
    #双方向に連結しろ！！！！！！！
*p,=sorted(map(int,input().split()))
    #双方向に連結しろ！！！！！！！
ans=[0 for i in range(n)]
    #双方向に連結しろ！！！！！！！
def DFS_dict(point,TFlist):
    #双方向に連結しろ！！！！！！！
    if all(TFlist):
    #双方向に連結しろ！！！！！！！
        return 1
    #双方向に連結しろ！！！！！！！
    for i in d[point]:
    #双方向に連結しろ！！！！！！！
        if TFlist[i-1]:
    #双方向に連結しろ！！！！！！！
            continue
    #双方向に連結しろ！！！！！！！
        TFlist[i-1]=True
        ans[i-1]=p.pop()
    #双方向に連結しろ！！！！！！！
        DFS_dict(i,TFlist)
    #双方向に連結しろ！！！！！！！
        TFlist[i-1]=False
    #双方向に連結しろ！！！！！！！
    return ans
    #双方向に連結しろ！！！！！！！
TFlist=[False]*n
    #双方向に連結しろ！！！！！！！
TFlist[start-1]=True
    #双方向に連結しろ！！！！！！！
score=sum(p)-max(p)
    #双方向に連結しろ！！！！！！！
ans[start-1]=p.pop()
    #双方向に連結しろ！！！！！！！
ans=DFS_dict(start,TFlist)
    #双方向に連結しろ！！！！！！！
print(score)
    #双方向に連結しろ！！！！！！！
print(*ans)

Submission status: Accepted

Solution code:
N = int(input())
edges = [list(map(int, input().split())) for i in range(N-1)]
c = list(map(int, input().split()))
c.sort(reverse=True)
_c = c[::]

conn = [[] for i in range(N)]
for edge in edges:
    a = edge[0]-1
    b = edge[1]-1
    conn[a].append(b)
    conn[b].append(a)
ans = [0 for i in range(N)]
stack = []
stack.append(0)
checked = set()
while len(stack) > 0:
    current = stack.pop(0)
    checked.add(current)
    ans[current] = c[0]
    c.pop(0)
    for next in conn[current]:
        if next not in checked:
            stack.append(next)

print(sum(_c[1:]))
ans_str = ""
for i in range(N):
    ans_str += str(ans[i])
    if i < N-1:
        ans_str += " "
print(ans_str)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

N = int(input())

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

c = list(map(int,input().split()))
c.sort()
print(sum(c)-c[-1])
d = dijkstra(e,N,0)
d = [(d[i],i) for i in range(N)]
d.sort()
d = [(d[i][0],d[i][1],c[-i-1]) for i in range(N)]
d.sort(key=lambda x:x[1])
ans = [str(d[i][2]) for i in range(N)]
print(' '.join(ans))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
Edges=[[] for _ in range(n)]
Cnt=[0]*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()
print(sum(C)-C[-1])
Used=[False]*n
Ans=[0]*n
q=[0]
Used[0]=True
while q:
    v=q.pop()
    Ans[v]=C.pop()
    for u in Edges[v]:
        if not Used[u]:
            Used[u]=True
            q.append(u)
print(*Ans)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
n = int(input())
nodes = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    nodes[a].append(b)
    nodes[b].append(a)
# print(nodes)

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

count = 0
answer = [0 for _ in range(n)]
for i in range(n):
  end = True
  for j in range(n):
    if len(nodes[j]) == 1:
      end = False
      nodes[nodes[j][0]].remove(j)
      nodes[j].pop()
      answer[j] = c.pop()
      count += answer[j]
  if end:
    break
print(sum(answer))

answer[answer.index(0)] = c.pop()
print(' '.join(map(str, answer)))