問題概要
頂点のグラフ 
が与えられる. 
番目の頂点には数字 
が割り当てられており, 最初は辺が張られていない. このとき, に対して辺を張ることによって, 全域木を作成したい. このとき, 頂点 と 頂点 
を結ぶのにはコスト 
がかかる.
ただし, 
個の辺があたえられ, 
番目の辺は 
と 
を指定する. この辺については, の代わりにコスト 
で結ぶこともできる( で結んでもよい).
全域木を作るのに必要な最小コストはいくらか？
問題へのリンク
制約
解法
辺を張れる候補は 
だけあるため, そのまま MST をすると当然 TLE します. どのようにすればよいでしょうか？
よくある発想として, 必要な辺だけ候補に入れることで辺の本数を減らすことを考えます. たとえば, 
だとすれば, が最小の頂点を 
として, を中心としたウニグラフを構築するのが明らかに最小になります.
よって, この辺が追加されたとしても, MST を構築しうる辺は 個の辺たちと とつながっている辺のみです(これ以外の辺を用いることによってコストが下がることはありません). よって, これらの辺をまとめてソートしクラスカル法などで MST を構築すればいいです. このとき辺の本数は 
程度なので, 問題なく間に合います.
実装
Submission #146588618 - Codeforces
