AtCoder M-SOLUTIONS プロコンオープン参加メモ

A100、B200、C500
こんなん無理やんけ参加しよ

結果

A,BはAC。
f:id:trsing:20190603143721p:plain

Dは解説読んでわかったのでメモ

D - Maximum Sum of Minimum

正の整数をソートして $c_{1}\geq c_{2} \geq \dots \geq c_{N}$ とする。

各辺に、2 つの端点に書き込まれた整数のうち小さい方を書き込む。

なので総和は最大でも $\sum_{i=2}^{N} c_{i}$ となることがわかります。じゃあどのように書き込めば最大になるのということですが、親の値 $\geq$ 子の値となるように書き込めば最大になります。子の値の総和になりますので。どっか適当に根を決めて辿る順*1に値を書き込んでいけばよいです。