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: Wrong Answer

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
for center in findCenter(edge):
    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 i in order:
        v_val.append(c[i-1])

    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: Wrong Answer

Solution code:
n = int(input())

d = {}
br = []
sum = 0
res = ""

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

    try:
        d[a] += 1
    except:
        d[a] = 1

    try:
        d[b] += 1
    except:
        d[b] = 1

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

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

for ind,i in enumerate(c):
    d[ind] = (d[ind][0], i)

d = sorted(d)

# print(br)
# print(d)

for i,j in br:
    # print(i,j)
    if d[i-1][1] < d[j-1][1]:
        sum += d[i-1][1]
    else:
        sum += d[j-1][1]

for i,j in d:
    res += str(j) + " "

print(sum)
print(res)

Submission status: Wrong Answer

Solution code:
n = int(input())
lis = [list(map(int,input().split())) for x in range(n-1)]
clis = sorted(list(map(int,input().split())),reverse=True)
ch_lis = []
ans = 0
for x in lis:
    ans += min(clis[x[0]-1],clis[x[1]-1])

print(ans)
print(*clis)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())

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


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

x = collections.Counter(l)
m = x.most_common()
ans = [0 for i in range(n)]

for i in range(len(m)):
    ans[m[i][0]-1] = c[i]

score = 0
for i in range(int(len(l)/2)):
    score += min(ans[l[2*i]-1], ans[l[2*i+1]-1])

print(score)
for i in range(len(ans)):
    print(ans[i], end = " ")

Submission status: Wrong Answer

Solution code:
from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N = int(input())
d=[0]*(N)
vcost=[0]*(N)
degree =[]
edge = []
for i in range(N-1):
    a,b = map(int,input().split())
    edge.append((a-1,b-1))
    d[a-1]+=1
    d[b-1]+=1
for i in range(N):
    degree.append((d[i],i))
degree.sort()
c = list(map(int,input().split()))
c.sort(reverse=True)
deg = 1
bool = 0
for i in range(N):
    if degree[i][0]==deg:
        vcost[degree[i][1]]=c.pop()
    else:
        deg = degree[i][0]
        if bool == 0:
            c.sort()
            bool = 1
        else:
            c.sort(reverse=True)
        vcost[degree[i][1]]=c.pop()
ans = 0
for e in edge:
    ans +=min(vcost[e[0]],vcost[e[1]])
print(ans)
print(*vcost,sep=" ")

Submission status: Wrong Answer

Solution code:
a = int(input())
d = {}
e = [0]*(a-1)
g = [0]*(a-1)
p = 0
for i in range(a-1):
  b,c = map(int,input().split())
  e[i] = [b,c]
  for k in range(2):
    if not e[i][k] in d.keys():
      d[e[i][k]] = 1
    else:
      d[e[i][k]] += 1
d = sorted(d.items(), key=lambda x: x[1])
d = dict(d)
f = list(map(int,input().split()))
for j in d.keys():
  d[j] = f[p]
  p += 1
for t in range(a-1):
  g[t] = min(d[e[t][0]],d[e[t][1]])
print(sum(g))
d = sorted(d.items(), key=lambda x: x[0])
d = dict(d)
for l in d.values():
  print(l,end= ' ')

Submission status: Wrong Answer

Solution code:
n = int(input())
lis = [list(map(int,input().split())) for x in range(n-1)]
clis = sorted(list(map(int,input().split())),reverse=True)
ch_lis = []
ans = 0
print(clis)
for x in lis:
    ans += min(clis[x[0]-1],clis[x[1]-1])

print(ans)
print(*clis)

Submission status: Wrong Answer

Solution code:
import copy
N = int(input())
I = []
for j in range(N - 1):
    I.append(list(map(int, input().split())))
c = list(map(int, input().split()))
c.sort(reverse=True)
datalist = []
suudata = []
suudatalist = []
suudatalist2 = []

for i in I:
    datalist.append(i[0])
    datalist.append(i[1])
#print(datalist)
for i in range(N):
    j = i + 1
    suudata.append(j)
    suudata.append(datalist.count(j))
    suudata2 = copy.copy(suudata)
    suudatalist.append(suudata2)
    suudata.clear()
for i in range(N):
    suudatalist2.append(suudatalist[i][0])
#print(suudatalist)
suudatalist.sort(key=lambda x:-x[1])
#print(suudatalist)
class Node:
    def __init__(self):
        self.nodenum = 0
        self.nodedata = 0
class Eda:
    def __init__(self):
        self.edanum = 0
        self.min = 0
        self.leftnodenum = 0
        self.rightnodenum = 0
edalist = []
nodelist = []
for i in range(N):
    nodelist.append(Node())
    nodelist[i].nodenum = i + 1
    #nodelist[i].nodedata = c[i]
    nodelist[i].nodedata = c[suudatalist2.index(i + 1)]
    #print(nodelist[i].nodenum, nodelist[i].nodedata)

for i in range(N - 1):
    edalist.append(Eda())
    edalist[i].edanum = i + 1
    edalist[i].leftnodenum = I[i][0]
    edalist[i].rightnodenum = I[i][1]
    edalist[i].min = min(nodelist[edalist[i].leftnodenum-1].nodedata, nodelist[edalist[i].rightnodenum-1].nodedata)
    #print(edalist[i].edanum, edalist[i].leftnodenum, edalist[i].rightnodenum, edalist[i].min)

sum = 0
for i in range(N - 1):
    sum += edalist[i].min

#出力
print(sum)
for i in range(N):
    print(nodelist[i].nodedata, end=" ")
print("")

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import math

def main():
    n = int(raw_input())
    ab = []
    for i in range(n-1):
        a,b = map(int,raw_input().split())
        ab.append([a,b])
    c = map(int,raw_input().split())
    c.sort()
    cnt = {}
    for p in ab:
        if p[0] in cnt:
            cnt[p[0]] += 1
        else:
            cnt[p[0]] = 1
        if p[1] in cnt:
            cnt[p[1]] += 1
        else:
            cnt[p[1]] = 1
    score_sorted = sorted(cnt.items(), key=lambda x:x[1])
    j = 0
    k = {}
    for i in  score_sorted:
        k[i[0]] = c[j]
        j += 1
    total = 0
    for p in ab:
        a = p[0]
        b = p[1]
        total += min(k[a],k[b])
    print total
    print ' '.join(map(str, k.values()))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def m():
    N = int(input())
    g = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)
    C = list(map(int, input().split()))
    C.sort(reverse=True)
    nodes = {}
    for i in range(1, N+1):
        nodes[i] = len(g[i])
    l = list(nodes.items())
    l.sort(reverse=True, key=lambda x:x[1])
    ans = [0] * N
    for k,v in l:
        ans[k-1] = C[k-1]
    return ans

print(*m())

Submission status: Wrong Answer

Solution code:
# 2019/06/01
# M-SOLUTIONS プロコンオープン - D

from operator import itemgetter

# Input
n = int(input())
abl = list()

# Init Fushi no Kazu
fcnt = list()
for i in range(n+1):
    wfcnt = 0
    fcnt.append([wfcnt, i])

for i in range(n-1):
    ab = list(map(int,input().split()))
    abl.append(ab)

    # Count up Fushi no Kazu
    fcnt[ab[0]][0] += 1
    fcnt[ab[1]][0] += 1

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

del fcnt[0]

fcnt.sort(key=itemgetter(0), reverse=True)

scoresum = 0
for i in range(n):
    fcnt[i].append(c[i])
    scoresum += c[i]

scoresum -= max(c)
fcnt.sort(key=itemgetter(1))

ansstr = ""

for i in range(n - 1):
    ansstr +=  str(fcnt[i][2]) + " "

ansstr +=  str(fcnt[n-1][2])

# Output
print(scoresum)
print(ansstr)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import collections


class BellmanFord():
    def __init__(self):
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        次のBellmanFord_negative_boolまで考慮した時には、0-indexedであることに注意
        s =  始点
        return: d[i] 始点sから各点iまでの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_bool(self, numNodes, zero_indexed=False):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = collections.defaultdict(lambda: float('inf'))
        d[0] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if i == numNodes-1:
                        return True
        return False

n = ni()
g = BellmanFord()

for i in range(n-1):
  a,b = na()
  g.add(a,b,1)

c = na()
c = sorted(c)[::-1]

print(sum(c)-c[0])

a = g.BellmanFord_search(1)
ans = [c[a[i]] for i in range(1,n+1)]
print(' '.join([str(v) for v in ans]))

Submission status: Wrong Answer

Solution code:
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]
c = list(map(int,input().split()))
side_num = [[0,i] for i in range(N)]
ans = 0
for a,b in ab:
    side_num[a-1][0] +=1
    side_num[b-1][0] +=1

side_num.sort(reverse=True)
c.sort(reverse=True)
for i in range(N):
    side_num[i][0] = c[i]

for a,b in ab:
    ans += min(side_num[a-1][0], side_num[b-1][0])
print(ans)
#side_num.sort(key=lambda x:x[1])
for i in range(N):
    print(side_num[i][0],end=" ")

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
# N = 10000
G = np.zeros((N,N),dtype = np.bool)

pairs = []

for i in range(N-1):
    a,b = map(int,input().split())
    # a,b = 1,2
    pairs.append((a,b))
    G[a-1][b-1] = True
    G[b-1][a-1] = True

Cs = list(sorted(map(int,input().split())))
# Cs = [1 for i in range(N)]

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

for i in range(N):

    links[i] = G[i,:].sum()

nodeval = np.array([0 for i in range(N)])

# print(links)

disabled = [False for i in range(N)]

args = np.argsort(-np.array(links))

for i in range(N):
    mx = 0
    # for i,l in enumerate(links):
    #     if not disabled[i]:
    #         mx = max(l,mx)
    # # print("mx",mx, "da", disabled)
    # for i,l in enumerate(links):
    #     if not disabled[i] and l == mx:
    #         break
    # disabled[i] = True
    # max connected node
    # print(i)
    nodeval[args[i]] = Cs.pop(-1)

# print(nodeval)

sumval = 0
for p in pairs:
    sumval += min(nodeval[p[0]-1], nodeval[p[1]-1] )

print(sumval)
for i,l in enumerate(nodeval):
    print(l,end=" " if i!=N-1 else "\n")

Submission status: Wrong Answer

Solution code:
n=int(input())
i=1
x=[]
while i!=n:
    a,b=map(int,input().split())
    x.append(a)
    x.append(b)
    i=i+1
nbox=list(map(int,input().split()))
i=0
link=[]
mi=[]
while i!=n:
    i=i+1
    mi.append(x.count(i))
    mi.append(i)
    link.append(mi)
    mi=[]
nbox.sort(reverse=True)

link.sort(reverse=True)

i=1
nnt = [0]*n
while i!=n+1:
    mi=link[i-1]
    nnt[mi[1]-1]=nbox[i-1]
    i=i+1
i=1
ans=0
while i!=n:
    a=x[(2*i)-2]
    b=x[(2*i)-1]
    if nnt[a-1]>nnt[b-1]:
        ans=ans+nnt[b-1]
    else:
        ans=ans+nnt[a-1]
    i=i+1
print(ans)
print(' '.join(map(str, nnt)))

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())

neighbors = [[] for _ in range(N)]

for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    neighbors[a].append(b)
    neighbors[b].append(a)
c = list(map(int, input().split()))
sorted_c = sorted(c)
max_c = sorted_c[-1]
max_c_pos = c.index(max_c)


q = deque()
q.append(0)

closed = [0 for _ in range(N)]
order = []
while len(q) > 0:
    parent = q.pop()
    closed[parent] = 1
    order.append(parent)
    for neighbor in neighbors[parent]:
        if closed[neighbor] == 0:
            q.append(neighbor)

for i, i2 in zip(range(N), order):
    c[i] = sorted_c[i]

q.clear()
q.append(0)
M = 0
closed = [0 for _ in range(N)]
while len(q) > 0:
    parent = q.pop()
    closed[parent] = c[parent]
    for neighbor in neighbors[parent]:
        if closed[neighbor] == 0:
            c2 = c[parent]
            c1 = c[neighbor]
            w = c1 if c1 < c2 else c2
            M += w
            q.append(neighbor)
closed[parent] = c[parent]

print(M)
print(*c)

Submission status: Wrong Answer

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)

def point(x, prev, turn=0):
    if turn > n:
        return
    dp[x] = c[turn]
    turn += 1
    for i in edge[x]:
        if dp[i] != 0:
            continue
        if i == prev:
            continue
        else:
            point(i, x, turn)
    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: Wrong Answer

Solution code:
# 接続数のでかい節から順にでかい数を格納していくのが良い
N = int(input())
connects = [[i,0] for i in range(N)]
pairs = []

for _ in range(N-1):
    a,b = map(int,input().split())
    connects[a-1][1] += 1
    connects[b-1][1] += 1
    pairs.append([a,b])
    
connects = sorted(connects, key=lambda x:-x[1])

c_s = list(map(int,input().split()))
c_s = sorted(c_s, key=lambda x:-x)

for i,connect in enumerate(connects):
    connect[1] = c_s[i]

connects = sorted(connects, key=lambda x:x[0])

answer = 0

for i,pair in enumerate(pairs):
    answer += connects[pair[0]-1][1] if connects[pair[0]-1][1] < connects[pair[1]-1][1] else connects[pair[1]-1][1]

print(answer)
for i,connect in enumerate(connects):
    if i == len(connects)-1:
        print(connect[1])
        break
    print(connect[1], end=" ")

Submission status: Wrong Answer

Solution code:
import sys
import heapq
INPUT = sys.stdin.readline

def SINGLE_INT(): return int(INPUT())
def NULTIPLE_INT_LIST(): return list(map(int, INPUT().split()))
def NULTIPLE_INT_NAP(): return map(int, INPUT().split())
def SINGLE_STRING(): return INPUT()
def NULTIPLE_STRING(): return INPUT().split()

class Node():
    def __init__(self, a,b):
        self.id = a
        self.marked = False
        self.adjacent = [b]
        self.n_adjacent = 1

    def add_edge(self, n):
        self.adjacent.append(n)
        self.n_adjacent += 1

N = SINGLE_INT()
leaf = set(range(N))
node = {}
node_marking = [0] * N

for _ in range(N-1):
    a, b = NULTIPLE_INT_NAP()
    a -= 1
    b -= 1

    if a in node:
        node[a].add_edge(b)
        try:
            leaf.remove(a)
        except:
            pass
    else:
        node[a] = Node(a,b)

    if b in node:
        node[b].add_edge(a)
        try:
            leaf.remove()
        except:
            pass
    else:
        node[b] = Node(b,a)

figures = NULTIPLE_INT_LIST()
figures.sort(reverse=True)
max_of_min = sum(figures[1:])

q = [(1, n) for n in leaf]

while figures:
    _, id = heapq.heappop(q)
    #print('visiting', id)

    visiting = node[id]

    if visiting.marked:
        continue

    visiting.marked = True
    node_marking[visiting.id] = figures.pop()

    for n in visiting.adjacent:
        adj = node[n]
        adj.n_adjacent -= 1
        if not adj.marked:
            heapq.heappush(q, (adj.n_adjacent, n))
            #print('added (', adj.n_adjacent, n, ')')

print(max_of_min)
print(' '.join(map(str, node_marking)))

Submission status: Wrong Answer

Solution code:
# 問題D
# 方針:繋がっている辺が多い頂点には大きい数字を置く.
# 計算:ループさせる.
n = int(input())
connected_edge_count = {}
edge_list = []
node_list = [0]
for i in range(n-1):
    b, c = map(int, input().split())
    b=b-1
    c=c-1
    edge_list.append((b, c))
    node_list.append(0)
    if(b in connected_edge_count):
        connected_edge_count[b] += 1
    else:
        connected_edge_count[b] = 1
    if(c in connected_edge_count):
        connected_edge_count[c] += 1
    else:
        connected_edge_count[c] = 1
connected_edge_count = sorted(connected_edge_count.items(), key=lambda x:x[1], reverse=True)
num_list = sorted(list(map(int, input().split())), reverse = True)
counter = 0
for node in connected_edge_count:
    node_list[node[0]] = num_list[counter]
    counter += 1
score = 0
for edge in edge_list:
    score += min(node_list[edge[0]], node_list[edge[1]])
print(score)
print(" ".join(str(e) for e in node_list))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
R = []
def dfs(v, p):
    for next in link[v]:
        if next == p:
            continue
        res[next] = min(c[v], c[next])
        dfs(next, v)

N = int(input())
res = [0] * N
link = [[] * N for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    link[a-1].append(b-1)
    link[b-1].append(a-1)
c = list(map(int, input().split()))

dfs(0, -1)

print(sum(res))
c.sort()
print(*c)

Submission status: Wrong Answer

Solution code:
def intinput(): return map(int,input().split())

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

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

Submission status: Wrong Answer

Solution code:
# 問題D
# 方針:繋がっている辺が多い頂点には大きい数字を置く.
# 計算:ループさせる.
n = int(input())
connected_edge_count = {}
edge_list = []
node_list = [0]
for i in range(n-1):
    b, c = map(int, input().split())
    b=b-1
    c=c-1
    edge_list.append((b, c))
    node_list.append(0)
    if(b in connected_edge_count):
        connected_edge_count[b] += 1
    else:
        connected_edge_count[b] = 1
    if(c in connected_edge_count):
        connected_edge_count[c] += 1
    else:
        connected_edge_count[c] = 1
connected_edge_count = sorted(connected_edge_count.items(), key=lambda x:x[1], reverse=True)
num_list = sorted(list(map(int, input().split())), reverse = True)
counter = 0
for node in connected_edge_count:
    print(node, num_list[counter])
    node_list[node[0]] = num_list[counter]
    counter += 1
score = 0
for edge in edge_list:
    score += min(node_list[edge[0]], node_list[edge[1]])
print(score)
print(" ".join(str(e) for e in node_list))

Submission status: Wrong Answer

Solution code:
N = int(input())
sides = [list(map(int, input().split())) for _ in range(N - 1)]
c = list(map(int, input().split()))
c.sort()
print(sum(c[0:N - 1]))
c = map(str, c)
print((' ').join(c))

Submission status: Wrong Answer

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

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

count = 0
maxCount = 0
maxList = []

for c in itertools.permutations(cs):
    print(c)
    for node in nodes:
        if(c[node[0]-1] < c[node[1]-1]):
            count = count + c[node[0]-1]
        else:
            count = count + c[node[1]-1]
    if(count >= maxCount):
        maxCount = count
        maxList = c
    count = 0

print(maxCount)
print(' '.join(map(str, maxList)))

Submission status: Wrong Answer

Solution code:
import numpy as np
n=int(input())
d=[0]*n
p=[]
for i in range(n-1):
     a,b=map(int,input().split())
     a-=1
     b-=1
     d[a]-=1
     d[b]-=1
     p.append((a,b))
c=sorted(list(map(int,input().split())))
idxs=np.argsort(d)
for idx in idxs:
     x=c.pop()
     d[idx]=x
ans=0
for x in p:
     a,b=x
     ans+=min(d[a],d[b])
print(ans)
d=list(map(str,d))
print(' '.join(d))

Submission status: Wrong Answer

Solution code:
a = 1
for i in range(10000**2):
  a = a + 1

Submission status: Wrong Answer

Solution code:
n = int(input())
lis = [list(map(int,input().split())) for x in range(n-1)]
clis = sorted(list(map(int,input().split())),reverse=True)
ch_lis = []
ans_lis = []
num = 0
print(sum(clis)-max(clis))
print(*clis)

Submission status: Wrong Answer

Solution code:
import collections
import sys
input = sys.stdin.readline
from array import array
def solve():
  n = int(input())
  query2 = collections.deque([])
  ans = array('I', [ 0 for i in range(n)])
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query2.append(a)
    query2.append(b)
    
  c = list(int(i) for i in input().split())
  c = sorted(c,reverse =True)
  
  d = collections.Counter(query2)
  d2 = d.most_common()
  for i in range(n):
    ans[d2[i][0]-1] = c[i]
    
  print(sum(c) +(-1)*max(c))
  #dの処理
  print(*ans)
  
solve()

Submission status: Wrong Answer

Solution code:
# 2019/06/01
# M-SOLUTIONS プロコンオープン - D

from operator import itemgetter

# Input
n = int(input())
abl = list()

# Init Fushi no Kazu
fcnt = list()
for i in range(n+1):
    wfcnt = 0
    fcnt.append([wfcnt, i])

for i in range(n-1):
    ab = list(map(int,input().split()))
    abl.append(ab)

    # Count up Fushi no Kazu
    fcnt[ab[0]][0] += 1
    fcnt[ab[1]][0] += 1

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

del fcnt[0]

fcnt.sort(key=itemgetter(0), reverse=True)

scoresum = 0
for i in range(n):
    fcnt[i].append(c[i])
    scoresum += c[i]

scoresum -= max(c)
fcnt.sort(key=itemgetter(1))

ansstr = ""

for i in range(n):
    ansstr +=  str(fcnt[i][2]) + " "

# Output
print(scoresum)
print(ansstr)

Submission status: Wrong Answer

Solution code:
# 問題D
# 方針:繋がっている辺が多い頂点には大きい数字を置く.
# 計算:ループさせる.
n = int(input())
connected_edge_count = {}
edge_list = []
node_list = [0]
for i in range(n-1):
    b, c = map(int, input().split())
    b=b-1
    c=c-1
    edge_list.append((b, c))
    node_list.append(0)
    if(b in connected_edge_count):
        connected_edge_count[b] += 1
    else:
        connected_edge_count[b] = 1
    if(c in connected_edge_count):
        connected_edge_count[c] += 1
    else:
        connected_edge_count[c] = 1
connected_edge_count = sorted(connected_edge_count.items(), reverse=True)
num_list = sorted(list(map(int, input().split())))
counter = 0
for node in connected_edge_count:
    node_list[node[0]] = num_list[counter]
    counter += 1
score = 0
for edge in edge_list:
    score += min(node_list[edge[0]], node_list[edge[1]])
print(score)
print(" ".join(str(e) for e in node_list))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
class Node():
    def __init__(self, id):
        self.id = id
        self.children = []
        self.value = None

    def add_child(self, node):
        self.children.append(node)


def write(node, values):
    if len(values) == 0:
        return

    node.value = values.pop()
    for child in node.children:
        write(child, values)


n = int(input())

t = [Node(i) for i in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    parent = min(a, b)
    child = max(a, b)
    t[parent].add_child(t[child])

c = list(map(int, input().split()))
_c = sorted(c)
write(t[0], _c)

out = [node.value for node in t]

print(sum(c) - max(c))
print(" ".join(list(map(str, out))))

Submission status: Wrong Answer

Solution code:
from collections import*
n=int(input())
d=defaultdict(list)

start=float("inf")
for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    start=min(a,start)
p=sorted(map(int,input().split()))[::-1]

def DFS(point,TFlist):
    global ans
    global score
    if all(TFlist):
        return 1
    for i in d[point]:
        if TFlist[i-1]:
            continue
        TFlist[i-1]=True
        tmp=p.pop()
        ans[i-1]=tmp
        score.append(tmp)
        #print(score)
        DFS(i,TFlist)
        TFlist[i-1]=False
    return score,ans

TFlist=[False]*(n)
TFlist[start-1]=True
ans=[0 for i in range(n)]
score=[]
ans[start-1]=p.pop()
s,t=DFS(start,TFlist)
#print(d)
print(sum(s))
print(*t)

Submission status: Wrong Answer

Solution code:
n=int(input())
AB=[]
AB_=[]
for i in range(n-1):
    a,b=map(int,input().split())
    AB.append(sorted([a-1,b-1]))
    AB_.append(a-1)
    AB_.append(b-1)
c=sorted([int(i) for i in input().split()],reverse=True)
count=[]
for i in range(n):
    count.append([AB_.count(i),i])
count.sort(key=lambda x:x[0],reverse=True)
d=[0]*n
for i in range(n):
    d[count[i][1]]=c[i]
ans=0
for i in range(n-1):
    ans+=min(d[AB[i][0]],d[AB[i][1]])
print(ans)
for i in range(len(d)):
    d[i]=str(d[i])

print(' '.join(d))

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())
ab_ls = []
count = 0
while count < n-1:
    ab_ls.append(list(map(int, input().split())))
    count = count + 1
c_ls = list(map(int, input().split()))
hoge = []
for i in itertools.permutations(c_ls):
    min_sum = 0
    for ab in ab_ls:
        min_sum = min_sum + min(i[ab[0]-1],i[ab[1]-1])
    hoge.append([min_sum, i])
hoge.sort(key=lambda x: -x[0])
print(hoge[0][0])
print((str(hoge[0][1])).strip('()'))

Submission status: Wrong Answer

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(k[-1])

Submission status: Wrong Answer

Solution code:
n=int(input())
edge=[]
count = [[0, i] for i in range(n)]
ans=[0]*n
for _ in range(n-1):
  ai, bi = map(int, input().split())
  edge.append([ai-1, bi-1])
  count[ai-1][0]+=1
  count[bi-1][0]+=1
c = sorted(list(map(int, input().split())), reverse=True)

count.sort(key=lambda x: x[0], reverse=True)
for cnti, ci in zip(count, c):
  ans[cnti[1]]=ci
m=0
for e in edge:
  m+=min(ans[e[0]], ans[e[1]])
print(m)
res=""
for a in ans:
  res+=str(a) + " "
print(res)

Submission status: Wrong Answer

Solution code:
from collections import*
n=int(input())
d=defaultdict(list)

start=float("inf")
for i in range(n-1):
    a,b=map(int,input().split())
    d[a].append(b)
    start=min(a,start)
p=sorted(map(int,input().split()))

def DFS(point,TFlist):
    global ans
    global score
    if all(TFlist):
        return 1
    for i in d[point]:
        if TFlist[i-1]:
            continue
        TFlist[i-1]=True
        tmp=p.pop()
        ans[i-1]=tmp
        score.append(tmp)
        #print(score)
        DFS(i,TFlist)
        TFlist[i-1]=False
    return score,ans

TFlist=[False]*(n)
TFlist[start-1]=True
ans=[0 for i in range(n)]
score=[]
ans[start-1]=p.pop()
s,t=DFS(start,TFlist)
#print(d)
print(sum(s))
print(*t)