ABC 214 D | Notion

問題文

任意の $f(i,j)$ が何回使われたかが分かればこの問題が解けたも同然だということは分かっていた。

何回使われたかを知る方法を思いつけなかった。

任意の $f(i,j)$ について何回使われたかを知りたい

→ ある辺 $k$について考える。 $k$ の頂点を $u,v$ , 重みを $w$ とする。

$u$ 側で $w$ 以下の辺を持つ頂点の数 $\times$ $v$ 側で $w$ よ以下の辺を持つ頂点の数

これにより $k$ が何回使われたかを知ることができる。

$u$ 側で $w$ よりも大きい辺があったら $k$ の重みは足されないためそれ以上見なくてもよい。

($v$ 側でも同様)

全ての $k$ に対してどの頂点を含むのかを高速に求められれば答えも求められる。

これは重みを昇順にソートした後UnionFindを利用すればよい。

昇順にソートすることによって新しい辺を見つけたらその辺は必ず前の辺以上の重みを持っている。なのでUnionFindで頂点をマージするだけの操作でどの頂点を含むか調べることができる。(マージされた連結成分を削除する必要がなくなる。)

降順にソートはかなり難しいと思われる。(グラフ系統は削除する操作が苦手,ACLのUnionFindにも削除は実装されていない)

提出コード