公式解説中の最小全域木を計算する部分は、より高速かつ簡潔なアルゴリズム (時間計算量 \(O(E \log (E))\)) が存在することが知られています。 詳しくはこちらの記事を参照してください。

https://tokoharuland.hateblo.jp/entry/2018/04/01/155743

本問題の場合ボロノイ図で隣接する領域を繋ぐ辺をリストアップした時点で、実際に最小全域木を求めなくてもそれらの辺のみを用いてクエリの処理を行うことができます。