Atcoder M-SOLUTIONS プロコン D- Maximum sum of Minimum

概要

Atcoderで開催されてた、M-SOLUTIONS　プロコンオープン D問題(500点)の解説記事です。
python でときました。

問題

入力

• 頂点数Nの木が与えられる。
• N個の自然数

内容

• 木の頂点に与えられた数字を当てはめていく。
• edge(a,b)があった時に、そのスコアをmin(頂点aの数字、頂点bの数字)とする。
• スコアの最大値と、それを満たす数字の当てはめ方を求める。

出力

• 最大スコア
• 各頂点への数字の当てはめ方

考察したこと

1. 与えられた自然数のうち、最大のもの(複数ある場合はそのうちの一つ)はscoreとして現れない。 (score= min(頂点aの数字、頂点bの数字)なので、最大の整数はscoreにならない)

2. 二番目に大きい数をscoreとして出したいときに、その頂点と繋がってるの頂点の中に、自分より大きい数字がないといけない。(三番目以降も同様)

-> maximum scoreは、整数のリストから最大の整数を一つの除いて、残りの数字の和となりそう。 -> 数字は、大きい順に当てはめる

atcoder.jp

方針

• scoreは　sum(与えられた整数) - 最大の整数　で良さそう。
• 当てはめ方は、 木の葉 のうちどれか一つからスタートしてbfsで訪問していき、訪問順に大きい数字から当てはめていく。

ポイント

• 「大きい数字から一つずつ取り出す」-> heapq 　を使う。
• 「大きい数字から」なので、heapqの要素には、 マイナスをかける 。(heapqは数字の小さい順にしか取り出せないから)

submittion

import heapq
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


N = int(input())
adj = [[] for _ in range(N)]

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

# heapqで大きい順に取り出したいから、マイナスにしておく。
L = list(map(lambda x: -int(x), input().split()))
heapq.heapify(L)
# Maxは一番大きい数字以外の和.(全体の和-最大の整数)でも止める。
# Lはマイナスがかけてあるので、min(L)で最大の和が求まる
score = -sum(L)+min(L)


# nodeに書く数字
node = [-1]*N

# leafを探す,leafからbfsして訪問順に大きい数字を入れていく
leaf = -1
for i, a in enumerate(adj):
    if len(a) == 1:
        leaf = i
        break

# bfs
Q = [leaf]
while Q:
    cur = Q.pop()
    for a in adj[cur]:
        if node[a] == -1:  # まだたどり着いてないとこには、数字を入れる。
            node[a] = - heapq.heappop(L)
            Q.append(a)
print(score)
print("\n".join(map(str, node)))