主客転倒(ABC214 D - Sum of Maximum Weights)

[tipstar0125]

https://atcoder.jp/contests/abc214/tasks/abc214_d

[tipstar0125]

解説：https://blog.hamayanhamayan.com/entry/2021/08/15/034729 主客転倒：https://physics0523.hatenablog.com/entry/2020/01/12/052513

[tipstar0125]

愚直に求める場合、各頂点の組み合わせのf(i, j)の総和を求めることになる。 これだと、O(N^2)なのでTLE。

f(i, j)のパターンは、辺の重みのパターンだけしかないから、これを全探索することを考える。

主客転倒：f(i, j)になる組み合わせの数を数えて、総和をとる

[tipstar0125]

f(i, j)となるには、それぞれの頂点につながる辺の重みが、i-j間の辺の重みより小さいときの、各頂点につながっている頂点の数同士をかけた数となる。

辺の重みで昇順に並べて、辺が小さい方からUnionFindでuniteしていく。 既にuniteしている辺の重みが、今からuniteする辺の重みよりも小さい状態を保ちつつ、uniteする前の各頂点につながる頂点の数を数えてあげればよい。