ABC214 D Sum of Maximum Weights

各辺について, その辺のコストの答えへの寄与分を考える. 具体的には, ある辺についてそれを通る2頂点間の最短パスのうち今見ている辺のコストが最大となる場合の数を求める. ここで, 木において(辺i-jを利用する回数) = (jの部分木サイズ) * (N - (jの部分木サイズ))を一般のグラフにも適用することを考えてみる. すると, 次のようにすることで同様の考え方によりこの問題を解くことができる.

まず, 各辺をコストの昇順にソートしておく. ある辺$ i = 0, 1, 2, ..., N - 2について, 答えに$ w_i \cdot (u_iの連結成分のサイズ) \cdot (v_iの連結成分のサイズ)を加算し, 頂点$ u_iと$ v_iをつなぐ.

このように, ある段階でのグラフを考えることで, 連結成分のサイズをUnion-Findで求めると$ O(N\alpha(N))でこの問題を解くことができた.

実装例: https://atcoder.jp/contests/abc214/submissions/25070780