バケット法のような解法を紹介します。問題は以下のように帰着できます。

$N$ 頂点 $M$ 辺のグラフがあり、辺にはそれぞれコストが定まっている。コストが大きい順に辺を追加していくとき、頂点 $s,t$ が初めて連結になるのはどのコストの辺まで追加した時点かというクエリが $Q$ 個飛んでくるので処理してください。

初めに、辺のコストが両端の頂点の最も近い祭りをやっている頂点への距離のうち小さいほうなので、答えとしてありうる値は $O(N)$ 通りです。その $O(N)$ 通りの答えの候補を降順にソートして、 $1$ ブロックに $S$ 個ずつ $O \left( \frac{N}{S} \right)$ ブロックに分けます。
その後、各クエリについて答えはどのブロックに存在するかを調べます。これは各クエリについて $O \left( \frac{N}{S} \right)$ 個の答えの候補についてそれ以上かそれ以下か確認すればよく、ここまでの一連の操作はdsuなどを使えば $O \left( (M+N) \log N + (M + \frac{NQ}{S} ) \alpha(N) \right)$ で可能です。

上の準備により、各クエリについて答えの範囲が分かりました。
次に辺を追加していきます。ここで、(コストが同じ辺については全て同時に)辺を追加した時に答えの範囲がそこに含まれるクエリについて答えがその値かを確認していきます。各クエリについて確認回数は $S$ 回なので合計で $O \left( QS \alpha(N) \right)$ です。

よって、 \(S= \sqrt{N}\) とすることでこの問題は \(O \left( (M+N) \log N + (M + N \sqrt{N}) \alpha(N) \right)\) で解くことができます。
実装方法によっても変化しますが実行時間が最短となる \(S\) は \(\sqrt{N}\) 前後の値を取るので色々と試してみるとよいです。例えば \(S=100,150,200,300,400\) で 442ms,406ms,439ms,541ms,608ms でした。