JOI '15 春合宿 4:1 - 遺産相続
問題
https://www.ioi-jp.org/camp/2015/2015-sp-tasks/2015-sp-d4.pdf
解法
K 人それぞれに Union Find 木を構成し,辺のコストが高い順に辺を見ていく.辺ごとにどの人に辺を割り振るかを考える.この時,ある人を境に辺を含めることが可能になるので,その人を二分探索で探す.辺を含めることが可能になるかどうかの判定はそれぞれの人の Union Find 木で辺の両端が追加されているかどうかで出来る.O(MlogM).
解答
二分探索の判定部で,どの人も辺を含めることが出来ない場合の処理を書いていなく,WA を連発してしまった.二分探索を単体で使うだけではない解法で使う方法を知った.