E - Black Cats Deployment Editorial by kobae964
辺の楽しさを降順ソートしたものを \(e_1 > e_2 > \cdots > e_{N-1}\) とし、\(e_0 = \infty, e_N = 0\) とします。 頂点 \(v\) から楽しさ \(x\) 以上で到達できる範囲を \(r(v, x)\) と呼ぶことにします。頂点 \(v\) における楽しさの合計は、
\[\sum_{i=1}^N e_i (|r(v, e_i)| - |r(v, e_{i-1})|) \\ = e_1 (|r(v, e_1)| - |r(v, e_0)|) + e_2 (|r(v, e_2)| - |r(v, e_1)|) + \\ \cdots + e_{N-1} (|r(v, e_{N-1})| - |r(v, e_{N-2})|)\]
です。(直感的な意味: 楽しさがちょうど \(e_i\) であるような頂点は \(|r(v, e_i)| - |r(v, e_{i-1})|\) 個ある。) これを式変形すると、
\[ \sum_{i=1}^{N-1} (e_{i+1} - e_i) (|r(v, e_i)| - 1) \]
です。(直感的な意味: 楽しさを下げていったときに、連結成分が増える直前に連結している自分以外の頂点それぞれについて、楽しさが下がる分を計上する。最終的に楽しさ 0 になったときに、すべての量が計上される。)
これを高速に計算したいです。ここで、楽しさの大きい辺から UnionFind や QuickFind といったデータ構造を使って、頂点をつなげることにします。実現したい操作は、各頂点が値 ans[i]
を持っているとしたとき、
- 連結成分の大きさを求める
- 連結成分のすべての頂点
v
に対して、ans[v] += x
を行う - 連結成分をマージする
です。例えば QuickFind を使用する場合、これは遅延評価用の配列 lazy[]
を用意することで実現できます。x
と y
をマージするとき、x
を含む連結成分の方が y
を含む連結成分よりも大きいと仮定してよく、
x
側はlazy
に加えるy
側はlazy
にあった分をすべて解決しans
に加える。そのとき今後x
の連結成分になるので、lazy[x]
に入るであろう値をすべての頂点のans
から引く
ということをすればよいです。
提出: https://atcoder.jp/contests/cf17-tournament-round3-open/submissions/22928265 (Rust)
posted:
last update: