競技プログラミング用知識集積所

ABC434E - Distribute Bunnies

最終更新：2025年12月03日 10:49

sport_programming

- view

管理者のみ編集可

問題

B以下レベルの内容は省略

ウサギを頂点とし、行先のかぶりが発生するウサギ同士を辺で結ぶUnionFind木※を考える。
そして、連結成分ごとに問題を解いて、その合計を答えればよい。
なぜなら、連結していない部分同士は、どのように選んでもお互いの選び方に影響しないからである。

各連結成分について、今度は所属するウサギの誰かが行ける場所を頂点とし、ウサギを自分が行ける2地点を結ぶ辺として考える。
これは明らかに連結なグラフになるが、実は辺の数と頂点数のうち小さい方がこの連結成分の答えである。
というのは、

辺の数が頂点数より少ない場合、グラフが木なので、根付き木とみなしてウサギが全員葉側に飛ぶことを考えれば、それ（辺の数）が明らかに最大値
辺の数が頂点数以上の場合、ループが少なくとも1ヶ所ある。ループのうちの1つの辺をA-Bとしたとき、その辺以外で適当に全域木を作り、Aを根にして上と同様のことをしたあとで、A-B辺担当のウサギをAにジャンプさせれば、それ（頂点数）が明らかに最大値

であるから。

ということで、UnionFind木※で連結するときに、その連結成分に行先が何個所属しているかを管理していけば、各連結成分ごとの答えを出すのは簡単である。