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:
# -*- Coding: utf-8 -*-

n = int(input())
A = []
A = [list(map(int,input().split())) for i in range(n-1)]
C = list(map(int,input().split()))

C2 = []
for i in range(n):
    C2.append([C[i],i])

C2.sort()

ans = sum(C)-C2[-1][0]

T = [[] for i in range(n)]
for i in range(len(A)):
    T[A[i][0]-1].append(A[i][1]-1)
    T[A[i][1]-1].append(A[i][0]-1)
#print(T)


E = [[0,i] for i in range(n)]
E[0][0]=1
# co = 0
# while co < n-1:
#     #print(co)
#     t = 0
#     while t < n+1 :
#         if len(T[t]) == 1:
#             E.append(t)
#             if co == n-2 :
#                 E.append(T[t][0])
#             T[T[t][0]].remove(t)
#             T[t] = []
#             co += 1
#         t += 1

holist=[0]
hot = 0

def ho(u):
    p = E[u][0]
    for j in range(len(T[u])):
        if E[T[u][j]][0] == 0:
            E[T[u][j]][0] = p+1
            holist.append(T[u][j])

while hot < len(holist):
    ho(holist[hot])
    hot += 1
#print(E)
E.sort(reverse=1)


#print(E)

D = [0 for i in range(n)]
for i in range(n):
    D[E[i][1]] = C2[i][0]

print(ans)
s = ""
for i in range(n):
    s += str(D[i])
    s += " "

print(s)

Submission status: Accepted

Solution code:
n = int(input())

edge = [[] for i in range(n)]

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

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

c = sorted(cost, reverse=True)

w = [0] * n

w[0] = c.pop(0)

chk = [i for i in edge[0]]

while chk != []:
    node = chk.pop(0)
    if w[node] == 0:
        w[node] = c.pop(0)
        chk.extend(edge[node])

print(sum(cost) - max(cost))

print(' '.join(map(str, w)))

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque

n = input()
g = [[] for i in xrange(n + 1)]
inp = stdin.readlines()

idx = 0
c = []
for line in inp:
    if idx < n - 1:
        u, v = map(int, line.strip().split())
        g[u].append([v, idx])
        g[v].append([u, idx])
        idx += 1
    else:
        c = map(int, line.strip().split())

num = [0] * (n + 1)
ans = [0] * (n - 1)
c.sort(reverse = True)

vis = [0] * (n + 1)
def bfs(root):
    global vis
    
    vis[root] = 1
    q = deque([root])
    ctr = 0
    num[root] = c[ctr]
    ctr += 1
    while q:
        u = q.popleft()
        for v, idx in g[u]:
            if not vis[v]:
                vis[v] = 1
                q.append(v)
                num[v] = c[ctr]
                ans[idx] = c[ctr]
                ctr += 1

bfs(1)
print sum(c) - c[0]
print ' '.join(map(str, num[1:]))

Submission status: Accepted

Solution code:
INF=-10**10
N=int(input())
v=[0]*N
dic=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    dic[a-1].append(b-1)
    dic[b-1].append(a-1)
    v[a-1]+=1
    v[b-1]+=1

a=[[] for i in range(N)]
for i in range(N):
    a[v[i]].append(i)

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

ans=[-1]*N

answer=0
tmp=0
while tmp<N:

    if a[tmp]==[]:
        tmp+=1
        continue
    j=a[tmp][0]
    ans[j]=c.pop(0)
    itiji=INF
    for k in dic[j]:
        if v[k]>0:
            answer+=ans[j]
            a[v[k]].remove(k)
            a[v[k]-1].append(k)
            v[k]-=1
            if v[k]<tmp: itiji=tmp-1
    a[tmp].pop(0)
    v[j]=-1
    if itiji>INF: tmp-=1
    elif a[tmp]==[]: tmp+=1
      
print(answer)
for i in range(N):
    print(ans[i],end=" ")

Submission status: Accepted

Solution code:
n = int(input())

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

for i in range(n-1):
    aa,ba = map(int,input().split())
    adj[aa-1].append(ba-1)
    adj[ba-1].append(aa-1)

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

sh = []

def delete(edges):
    sh.append(edges)

    for i in range(len(edges)):
        la = adj[edges[i]][0]
        adj[la].remove(edges[i])
        if len(adj[la]) == 0:
            sh.append([la])
        adj[edges[i]] = []
    return

def search(adj):
    k = []
    for i in range(len(adj)):
        if len(adj[i]) == 1:
            k.append(i)
    return k

ed = search(adj)

while len(ed):
    delete(ed)
    ed = search(adj)
    if len(ed) == 1:
        sh.append(ed)
        break
    if len(ed) == 2:
        if adj[ed[0]] and adj[ed[0]][0] == ed[1]:
            sh.append(ed)
            break

sug = []
for i in range(len(sh)):
    for m in sh[i]:
        sug.append(m)


for i in range(len(sug)):
    ans[sug[i]] = c[i]



for i in range(n-1):
    anum += c[i]
print(anum)

las = ""
for num in ans:
    las += str(num)+ " "
print(las)

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:
import sys

sys.setrecursionlimit(10000000)

N = int(input())
M = [[] for _ in range(N)]
P = [0] * N
V = [0] * N
for _ in range(N - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    M[a].append(b)
    M[b].append(a)
C = sorted(map(int, input().split()), reverse=True)

def dfs(n, cur):
    if V[n] == 1:
        return cur
    P[n] = C[cur]
    V[n] = 1
    cur += 1
    for c in M[n]:
        cur = dfs(c, cur)
    return cur

dfs(0, 0)
print(sum(C[1:]))
print(' '.join(map(str, P)))

Submission status: Accepted

Solution code:
import copy
import heapq


class Node:
    def __init__(self):
        self.value = -1

    def __repr__(self):
        return "<v: {}>".format(self.value)


N = int(input())

adjs = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = [int(i) for i in input().split()]
    adjs[a-1].append(b-1)
    adjs[b-1].append(a-1)
adjs_copy = [copy.copy(adj) for adj in adjs]

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

cq = []
for c in C:
    heapq.heappush(cq, c)


nodes = [Node() for _ in range(N)]
changed = True
while changed:
    changed = False
    for i in range(N):
        if len(adjs[i]) == 1:
            nodes[i].value = heapq.heappop(cq)

            neighbor = adjs[i][0]
            adjs[i] = []
            adjs[neighbor].remove(i)

            changed = True
for node in nodes:
    if node.value == -1:
        node.value = heapq.heappop(cq)
        break


score = 0
for i in range(N):
    adj = adjs_copy[i]
    for ad in adj:
        score += min(nodes[i].value, nodes[ad].value)
score = score // 2

print(score)
print(*[str(node.value) for node in nodes])

Submission status: Accepted

Solution code:
from sys import stdin

def main():
    n = int(stdin.readline())
    e = [tuple(map(int,stdin.readline().split())) for x in range(n-1)]
    c = [int(x) for x in stdin.readline().split()]    

    c.sort(reverse=True)

    edge = {(i+1):[] for i in range(n)}
    for a,b in e:
        edge[a].append(b)
        edge[b].append(a)

    node = [0]*n
    root = 1

    node[0] = c[0]
    yet = edge[1]
    consume = 1

    while consume < n:
        x = yet[consume-1]
        node[x-1] = c[consume]
        consume += 1
        for y in edge[x]:
            if node[y-1] == 0:
                yet.append(y)

    print(sum(c[1:]))
    print(*node)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
graph=[]
ans=[0]*n
zisuu={}
for i in range(n):
    graph.append([])
for i in range(n-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
from collections import deque
zisuu_1=deque([])
for i in range(n):
    zisuu[i]=len(graph[i])
    if len(graph[i])==1:
        zisuu_1.append(i)
c=list(map(int,input().split()))
c.sort()
if n==1:
    ans[0]=c[0]
else:
    for i in range(n):
        x=zisuu_1.popleft()
        ans[x]=c[i]
        for j in graph[x]:
            zisuu[j]=zisuu[j]-1
            if zisuu[j]==1:
                zisuu_1.append(j)
print(sum(c[:n-1]))
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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)
c = list(map(int, input().split()))
c.sort(reverse=True)

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

for i in range(n):
    if len(edge[i]) > 1:
        continue
    else:
        dp = [0] * n
        point(i, -1)
        break

ans = sum(c) - max(c)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
ab = list()
for _ in range(n - 1):
    ab.append(list(map(int, input().split())))

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

tree = [[] for i in range(n)]
for a, b in ab:
    tree[a - 1].append(b - 1)
    tree[b - 1].append(a - 1)

c.sort(reverse=True)

ans = [-1 for _ in range(n)]

ans[0] = c[0]
c.pop(0)
q = list()
q.append(0)

while(len(q) != 0):
    v = q[0]
    q.pop(0)
    for u in tree[v]:
        if ans[u] != -1:
            continue
        ans[u] = c[0]
        c.pop(0)
        q.append(u)

print(sum(ans[1:]))
print(" ".join([str(a) for a in ans]))

Submission status: Accepted

Solution code:
import random
import sys
sys.setrecursionlimit(10**5 + 10)


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)

    cc = map(int, raw_input().split())
    cc.sort(reverse=True)
    ans = [0] * n

    def dfs(node, visited):
        for nex in children[node]:
            if nex in visited:
                continue
            visited.add(nex)
            dfs(nex, visited)
        ans[node] = cc.pop()

    while True:
        start = random.randrange(n)
        if len(children[start]) > 1:
            break
    dfs(start, {start})

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

Solution code:
import sys
sys.setrecursionlimit(10**8)
N = int(input())
num_edges = N-1
edges = [list(map(int, input().split())) for i in range(num_edges)]

adj = [[] for i in range(N+1)]
for ed in edges:
    adj[ed[0]] += [[ed[1]] ]
    adj[ed[1]] += [[ed[0]] ]
c_list = list(map(int, input().split()))
c_list = sorted(c_list)
d_list = [-1 for i in range(N+1)]

def recfun(vi, ind, M):
    d_list[vi] = 0 #数を更新
    for ed in adj[vi]: #隣接する頂点をみる
        if d_list[ed[0]] == -1: #更新していない場合
            ind, M = recfun(ed[0], ind, M) #その先をみる
    d_list[vi] = c_list[ind] #数を更新
    M += c_list[ind]
    ind += 1
    return  ind, M
        
_, M  = recfun(1, 0, 0)
print(M-c_list[-1])
print(" ".join(map(str, d_list[1:])))

Submission status: Accepted

Solution code:
import heapq as hq

N = int(input())
adj = [set() for _ in range(N)]
assignment = [None]*N

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

C = sorted(map(int,input().split()))
score = sum(C[:-1])
stack = [0]
assignment = [None]*N

while stack:
    v = stack.pop()
    if assignment[v] is not None:
        continue

    assignment[v] = C.pop()

    for u in adj[v]:
        stack.append(u)

print(score)
print(*assignment)

Submission status: Accepted

Solution code:
n=int(input())
edge=[]
for i in range(n-1):
    a,b=map(int,input().split())
    edge.append([a,b])
c=list(map(int,input().split()))
c.sort(reverse=True)
node=[0]*n
weight=[-1]*n
edges=[[] for _ in range(n)]
for a,b in edge:
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    node[a-1]=node[a-1]+1
    node[b-1]=node[b-1]+1
s=node.index(max(node))
#print(edges,node)
#print(edges,node)
stack=[]
stack.append(s)
weight[s]=c.pop(0)
while stack:
    #print(stack)
    buf=stack.pop(-1)
    for e in edges[buf]:
        if weight[e]==-1:
            weight[e]=c.pop(0)
            stack.append(e)
w=0
for a,b in edge:
    if(weight[a-1]>weight[b-1]):
        w+=weight[b-1]
    else:
        w+=weight[a-1]
print(w)
for i in range(n):
    print(weight[i])

Submission status: Accepted

Solution code:
# 再帰関数の呼び出し回数が多くなる時はこれが必要！！無いとruntime errorになる。
import sys
sys.setrecursionlimit(100000+10)

# 木の深さ優先探索
def add_edge(u, v):
	G[u].append(v)
	G[v].append(u)

def dfs(vertex):
	global values
	global now_index

	values[vertex] = values_to_give[now_index]
	now_index -= 1

	for info in G[vertex]:
		v = info
		if values[v] >= 0: 
			#探索済み
			pass
		else:
			dfs(v)

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

G = [[] for _ in range(n)] #グラフの隣接リスト表現
for edge in edges:
	add_edge(edge[0]-1, edge[1]-1)

values = [-1] * n
# values[0] = values_to_give[n-1]
now_index = n-1

dfs(0)

mmm = list(map(str, values))
print(sum(values_to_give) - max(values_to_give))
print(" ".join(mmm))

Submission status: Accepted

Solution code:
import collections
N = int(input())
tree = [[] for i in range(N+1)]
hen = []
tyouten = [0 for i in range(N+1)]
zisuu = []
for i in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
    hen.append([a,b])
c = list(map(int, input().split()))
c.sort(reverse = True)

for i in range(1,N+1):
    zisuu.append([len(tree[i]),i])

zisuu.sort(reverse = True)

queue = collections.deque()
queue.append(zisuu[0][1])
count = 1
tyouten[zisuu[0][1]] = c[0]
while len(queue) > 0:
    now = queue.popleft()
    for next in tree[now]:
        if tyouten[next] == 0:
            tyouten[next] = c[count]
            count += 1
            queue.append(next)



ans = 0
for i in range(N-1):
    ans += min(tyouten[hen[i][0]], tyouten[hen[i][1]])

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)

n = int(input())
edgeList0 = [list(map(int, input().split())) for i in range(n-1)]
cList = list(map(int,input().split()))
cList.sort(reverse=True)
print(sum(cList[1:]))
edgeList = []
for _ in range(n):
  edgeList.append([])
for i in edgeList0:
  edgeList[i[0]-1].append(i[1]-1)
  edgeList[i[1]-1].append(i[0]-1)

def edgefunc(j):
  numList.append((j,cList.pop(0)))
  if len(edgeList[j]) != 0:
    for k in edgeList[j]:
      edgeList[k].remove(j)
      edgefunc(k)

numList = []
edgefunc(0)
numList.sort()
answer2 = ""
for l in numList:
  answer2 += str(l[1]) + " "
print(answer2[:-1])

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()


N = n()
M = 0
ds = [None] * N

edges = defaultdict(set)
ranks = [0] * N
for i in range(N-1):
    a, b = nl()
    edges[a-1].add(b-1)
    edges[b-1].add(a-1)
    ranks[a-1] += 1
    ranks[b-1] += 1
cs = sorted(nl())
M = sum(cs[:-1])

h = []
for i in range(N):
    heapq.heappush(h, (ranks[i], i))

for i in range(N):
    rank, node = heapq.heappop(h)
    ds[node] = cs[i]
    for next_node in edges[node]:
        ranks[next_node] -= 1
        heapq.heappush(h, (ranks[next_node], next_node))
        edges[next_node].remove(node)

print(M)
print(' '.join([str(d) for d in ds]))

Submission status: Accepted

Solution code:

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

for i in range(N-1):
    a,b=list(map(int,input().split()))
    a=a-1
    b=b-1
    road_list[a].append(b)
    road_list[b].append(a)
c = list(map(int,input().split()))
from collections import deque
Q = deque([[0,0]])
ans = []
checked_list = [False for i in range(N)]
checked_list[0]=True
count_list = [10**9 for i in range(N)]
count_list[0] = 0

while len(Q)>0:
    v,count = Q.pop()
    count+=1
    for v1 in road_list[v]:        
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.append([v1,count])
            count_list[v1]=count

c.sort()

count_list = [[i,count_list[i]] for i in range(N)]
count_list = sorted(count_list, key=lambda x:x[1],reverse=True)
d = [[count_list[i][0],c[i]] for i in range(N)]
d = sorted(d, key=lambda x:x[0])
d = [d[i][1] for i in range(N)]
print(sum(c[:-1]))
print(*d)

Submission status: Accepted

Solution code:
N = int(input())

E = [[] for i in range(N + 1)]
ans = {}
First = 0
edges = 0
q = []
visited = [False] * (N + 1)


for i in range(N - 1):
    A, B = map(int, input().split())
    E[A].append(B)
    E[B].append(A)
    if len(E[A]) > edges:
        First = A
        edges = len(E[A])

    if len(E[B]) > edges:
        First = B
        edges = len(E[B])

C = list(map(int, input().split()))
C.sort()
max = sum(C) - C[-1]
q.append(First)

for i in range(1, N + 1):
    x = q.pop(0)
    visited[x] = True
    ans[x] = C[-i]
    for xx in E[x]:
        if not visited[xx]:
            q.append(xx)

print(max)

s = ""
for i in range(1, N + 1):
    s += str(ans[i])
    if i != N:
        s += " "

print(s)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

n = int(input())

nodes = defaultdict(list)
edges = []
edge_count = defaultdict(int)
node = defaultdict(int)
node_num = defaultdict(int)

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

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

q = deque()
q.append(1)
node[1] = 0

while q:
    current = q.popleft()
    depth = node[current]

    for next in nodes[current]:
        if next not in node:
            node[next] = depth + 1
            q.append(next)


depth_list = sorted(node.items(), key=lambda x:x[1])

for i, e in enumerate(depth_list):
    node_num[e[0]] = c[i]

ans = 0
for edge in edges:
    ans += min(node_num[edge[0]], node_num[edge[1]])

print(ans)

position = []

for i in range(n):
    position.append(node_num[i + 1])

print(*position, sep=" ")

Submission status: Accepted

Solution code:
from collections import defaultdict
# import numpy as np

N = int(input())

ab = []

for _ in range(N - 1):
    ab.append(tuple(map(int, input().split())))

c = sorted(list(map(int, input().split())), reverse=True)
# argsort = np.argsort(c)[::-1]

nodes = defaultdict(set)
for a, b in ab:
    nodes[a].add(b)
    nodes[b].add(a)


d = {}
done = set()
stack = [1]
ci = 0
node = 1
while stack:
    node = stack.pop()
    d[node] = c[ci]
    stack += list(nodes[node] - done)
    done.add(node)
    ci += 1

print(sum(c[1:]))
for i in range(N):
    print(d[i + 1], end=' ')
print()

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))
def oon(x,n,nn):
	global c,ppp
	for i in range(len(x[n])):
		if x[n][i] != nn:
			kk[x[n][i]] = c[ppp]
			ppp += 1
			oon(x,x[n][i],n)

q = int(input())

k = [0 for i in range(q)]
kk = [0 for i in range(q)]
aa = [[]for i in range(q)]
for i in range(q-1):
	a,b  = m()
	k[a-1] += 1
	k[b-1] += 1
	aa[a-1].append(b-1)
	aa[b-1].append(a-1)
k.sort(reverse = True)
c = l()
c.sort(reverse = True)
kk[0] = c[0]
ppp = 1
oon(aa,0,0)
su = sum(c[1:])

print(su)
for i in range(q-1):
	print(kk[i],end = " ")
print(kk[-1])

Submission status: Accepted

Solution code:
import sys, math, collections, heapq, itertools
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    file = sys.stdin.readline #single: int(file()), line: map(int, file().split())
    INF = 10 ** 25
    mod = 7 + 10 ** 9

    N = int(file())
    edge = [[] for i in range(N)]
    for i in range(N-1):
        a, b = map(int, file().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    c = [int(i) for i in file().split()]
    c.sort(reverse = True)

    que = collections.deque()
    last = 0
    forward = [-1] * N
    que.append((0, 0))
    while que:
        now, dist = que.popleft()
        if forward[now] == -1:
            forward[now] = dist
            last = now
            for e in edge[now]:
                if forward[e] == -1: que.append((e, dist + 1))
    backward = [-1] * N
    que.append(last)
    count = 0
    while que:
        now = que.popleft()
        if backward[now] == -1:
            backward[now] = c[count]
            count += 1
            last = now
            for e in edge[now]:
                if backward[e] == -1: que.append(e)

    total = 0
    que.append((last, backward[last]))
    visited = [False] * N
    while que:
        now, weight = que.popleft()
        if visited[now] == False:
            visited[now] = True
            for e in edge[now]:
                if visited[e] == False:
                    total += min(weight, backward[e])
                    que.append((e, backward[e]))

    print(total)
    print(" ".join(map(str, backward)))

    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N = int(input())

que = []
edges = {i:[] for i in range(1,N+1)}
visited = {i:False for i in range(1,N+1)}
ans = {i:None for i in range(1,N+1)}

while True:
  s = list(map(int,input().split()))
  if len(s) > 2: 
    break
  edges[s[0]].append(s[1])
  edges[s[1]].append(s[0])
s = sorted(s)
ans1 = sum(s[:-1])

que.append(1)

while que:
  temp = que.pop(0)
  if visited[temp]:
    continue
  visited[temp] = True
  ans[temp] = s.pop()
  que += edges[temp]

s = ""
for key in ans:
  if key>1:
    s+= " "
  s += str(ans[key])
print(ans1)
print(s)

Submission status: Accepted

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

import queue

def readInt():
    return int(input())

def readList():
    return list(input().split())

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

def main():
    n = readInt()
    edges = {}
    edges2 = []
    links = {}
    leaf = queue.Queue()
    for _ in range(n-1):
        a, b = readListI()
        a -= 1
        b -= 1
        edges.setdefault(a, set())
        edges.setdefault(b, set())
        edges[a].add(b)
        edges[b].add(a)
        links.setdefault(a, 0)
        links.setdefault(b, 0)
        links[a] += 1
        links[b] += 1
        edges2.append((a, b))
    for e, l in links.items():
        if l == 1:
            leaf.put(e)
    lc = sorted(readListI())
    ret = {}
    for c in lc:
        e = leaf.get()
        ret[e] = c
        for e2 in edges[e]:
            if e2 in links:
                links[e2] -= 1
                if links[e2] == 1:
                    leaf.put(e2)
    ans = 0
    for a, b in edges2:
        ans += min(ret[a], ret[b])
    print(ans)
    print(" ".join(map(str, [v for e, v in sorted(ret.items())])))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N=input()

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

for _ in range(N-1):
	a,b=map(int, sys.stdin.readline().split())
	nl[a].append(b)
	nl[b].append(a)


C=map(int, sys.stdin.readline().split())
C.sort(reverse=True)
C=deque(C)


start=None
max_nl_cnt=0
for i in range(1,N+1):
	nl_cnt=len( nl[i] )
	if max_nl_cnt < nl_cnt:
		start=i
		max_nl_cnt=nl_cnt

Visit=[ None for i in range(N+1) ] 

q=deque()
q.append(start)
val=C.popleft()
Visit[start]=val

ans=0
while q:
	x=q.popleft()
	for to in nl[x]:
		if Visit[to] is None:
			val=C.popleft()
			Visit[to]=val
			ans+=val
			q.append(to)

print ans
for x in Visit[1:]:
	print x,

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200010)

N = int(input())
tree = [[] for _ in range(N + 1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
c = [int(s) for s in input().split()]
c.sort(reverse=True)

anst = [0] * (N + 1)
anss = 0


def visit(a, prev):
    global anst, anss
    ans = 0
    for b in tree[a]:
        if b != prev:
            ci = visit(b, a)
            anss += ci
    ci = c.pop()
    anst[a] = ci
    return ci


visit(1, 1)
print(anss)
print(" ".join((str(i) for i in anst[1:])))

Submission status: Accepted

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
  
#while leafs:
#  next_leafs = set()
#  for l in leafs:
#    for u in adjacent_dict[l]:
#      acjacents[u] -= 1
#      next_leafs.add(u)
  
  
while leafs:
  new_stack = []
  for v in leafs:
    for u in adjacent_dict[v]:
      adjacents[u] -= 1
      if visited[u]==0:
        visited[u]=1
        new_stack.append(u)
  leafs = [v for v in new_stack if adjacents[v]==1]
  nodes.extend(leafs)
  if not leafs:
    nodes.extend(new_stack) #最後に隣接0のノードが残ったとき
    break
  for u in [v for v in new_stack if adjacents[v]!=1]:
    visited[u] = 0
    
  
ans = [0]*(N)
for i in range(N):
  ans[nodes[i]-1] = C[i]
  
print(M)
print(*ans)

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(l[0][0])

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:
N = int(input())
E = [ [] for i in range(N)]
D = [0] * N
for i in range(N-1):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
c = list(map(int,input().split()))
x = max(c)
print(sum(c)-max(c))
start = 0
for i in range(N):
    if (len(E[i]) >= 2):
        start = i
        break
already = [0]*N
already[start] = 1
path = [start]
while(path):
    start = path[0]
    try:
        next = E[start][0]
    except:
        d = min(c)
        D[start] = d
        c.remove(d)
        path.remove(start)
        continue
    if already[next] == 1:
        E[start].remove(next)
        continue
    path.insert(0,next)
    already[next] = 1
for d in D:
    print(d,end = " ")

Submission status: Accepted

Solution code:
#

import itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

def main():
    N = int(input())
    d = [0] * N
    multi = [0] * N

    edges = defaultdict(list)
    edges_l = []
    for _ in range(N-1):
        a, b = map(int, input().split())
        d[a-1] += 1
        d[b-1] += 1
        multi[a-1] += 1
        multi[b-1] += 1

        edges_l.append((a-1, b-1))
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)

    for i in range(len(d)):
        d[i] = (d[i], i)
    d.sort(key=lambda v: v[0], reverse=True)

    C = list(map(int, input().split()))
    C.sort(reverse=True)
    # print(d)
    # print(C)
    used = [False] * N
    ans = [0] * N
    count = 0
    que = []
    que.append(d[0][1])
    while que:
        index = que.pop()
        if not used[index]:
            # print('i = {}, Ci = {}'.format(i, C[i]))
            ans[index] = C[count]
            used[index] = True
            count += 1

        # print(edges[i])
        for nei in edges[index]:
            if not used[nei]:
                que.append(nei)

    val = 0
    for a, b in edges_l:
        node_val = min(ans[a], ans[b])
        val += node_val

    print(val)
    print(' '.join(map(str, ans)))


if __name__ == '__main__':
    main()