辺の楽しさを降順ソートしたものを \(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)