公式解説にあるとおり、Kruskal法で最小全域森を構築する手法で有効な建物間の移動を列挙することができます。

有効な建物間の移動を列挙したあと、各クエリに答えることを考えます。

部分永続Union-Find

Union-Find の変形として 部分永続Union-Find と呼ばれるデータ構造があります。

全体のサイズを\(N\)として「\(t\) 番目の連結を行ったあとに \(a, b\) が連結であるかどうか」を \(O(log N)\) で求められます。

クエリの計算

部分永続Union-Find に対して、有効な建物間の移動を距離が短い順に連結を行います。

すると、長さ \(n\) 以下の移動を部分永続Union-Find に適用したあとに、建物\(s,t\)が連結であるかは\(O(log P)\)で求めることができます。

長さ \(n\) はたかだか\(P\)通りなので、\(n\)について二分探索すると、各クエリについて \(O((log P)^2)\) で\(s,t\)間の移動で必要な水筒の大きさを計算できます。

よって、前処理を除くとすべてのクエリについて \(O(Q (log P)^2)\) で解くことができます。