考え方 回答例 考え方「辺を切る問題」は，逆順に考えて「辺をつなぐ問題」に読み替える事を考えると，UnionFind（UnionFind木 - 競プロはじめました）が使える．UnionFindの初期化では， すべての発電所をつなぐ イベントで切られない辺をつなぐ とすればよ…

考え方 回答例 参考 考え方分割の過程を二分木だと思って逆順に見ると，各葉に起因するコストは(葉の長さ)×(葉の深さ)となる．よって，もし二分木の形が決まっているのなら，長さが小さいものが最も深くなるように配置すれば良い． 以上をもとに，テキトーに…

【関連記事】 UnionFind木 - 競プロはじめました 考え方 回答例 考え方逆から考えてUnionFind木でつないでいくだけ．連結成分の数は， 頂点を加えたら+1 つながっていないグループを新たにつないだら-1 とすればよい．グラフの辺は小さい頂点から大きい頂点…

C++ ではこんなに簡単にかけるのに．．． Editorial - AtCoder Beginner Contest 217【追記（C++ の回答）】(C++) ABC217D - Cutting Woods - 競プロはじめました一般的な話は次が役立ちそう： std::setを使わない代替テクニック [いかたこのたこつぼ] 【Pyt…