この問題は次のようなアルゴリズムにより、クエリ先読みなしでも解くことができます。

• 元のグラフの最小全域木 \(T\) を構築する
• クエリ \((u,v,w)\) に対する答えは、\(T\) の \(u-v\) パスに含まれる辺の最大重みが \(w\) より大きいとき Yes、小さいとき No

ここで、\(u-v\) パスに含まれる辺の重みの最大値は、適当な頂点を根とすることで、ダブリングにより LCA を求めるアルゴリズムと同様にして、前計算 \(O(N\log N)\) ・クエリ \(O(\log N)\) で求められます。

以上によりこの問題は \(O((M+Q)\log N)\) で解けました。

この解法の正当性には、次の命題から従います：
連結なグラフ \(G\) の辺 \(e\) について、\(G\) の最小全域木で辺 \(e\) を含まないものが存在するための必要十分条件は、辺 \(e\) が重み最大であるような閉路が存在すること

命題の正当性はクラスカル法を考えれば明らかです。

この命題やそれに類する考え方を使う問題の例

• 第2回PAST O問題『可変全域木』
• キーエンス プログラミング コンテスト 2019 E問題『Connecting Cities』