E. Spanning Tree Queries - Educational Codeforces Round 122 (Rated for Div. 2)

f:id:baitop:20220201170315p:plain

問題

N頂点M辺の連結無向グラフが与えられ、各辺にはwiの重みがある。

f(x) := sigma(wi - x)が最小になるように取った全域木のコスト

とした時に、10^7個のxが与えられる。

全てのxについてf(x)を計算し、それらのxorを求めろ

制約

N<=50

M<=300

解説

クエリの数が多すぎるため上手く扱う必要がある。

近いxについて全域木の形は変わらない事から、区間で扱いたくなる。

全域木の形が変わり得る条件は、クラスカル法の仕組みから

ある二つの辺のコストの大小関係が入れ替わる時である

よって全ての(wi+wj)/2の点を列挙すればいいように思える。O(M^2)

そのうえでwiの点も全て列挙すれば、点をソートしたうえで隣接する2点からなる各区間の間、答えは線形に変化する(なぜなら各区間について自分の左右にある採用した辺の数が変わらないため)

よってこれらを全て列挙したうえでクラスカル法を適用すればいい。

バイトの競プロメモ