基本方針

次のような無向グラフ \(G\) を考えます。

• 頂点は \(K\) 個で本問の家がある地点に対応
• 任意の \(i,j(1 \leq i \lt j \leq K)\) に対し、頂点 \(i,j\) 間には辺があり、そのコストは地点 \(i\) から地点 \(j\) までの距離である

元問題の答えは \(G\) 上での答えと一致するため、次のような解法は(出力が正しいという意味で)正当です。

• \(G\) の辺をコストの昇順にソートし、\(i\) 番目のクエリを処理する時はコスト \(t_i\) 以下の辺であってまだ追加されていないものをDSUに追加する。そして、頂点 \(x_i\) と \(y_i\) が同じ連結成分かどうかを判定する。

しかし、\(\mathrm{O}(K^2)\) 本の辺を扱うことは出来ないため改善が必要です。

辺の削減

\(G\) のある最小全域木を \(T\) とします。実は、\(T\) 上での答えは \(G\) 上での答えと一致します。

証明

上の命題の否定は次のように言えます。

• \(G\) における \(u\) から \(v\) へのコストが \(T\) における \(u\) から \(v\) へのコストより真に小さくなるような頂点 \(u,v\) が存在する。
  

これを仮定すると、\(T\) の \(u,v\) 間パスに \(G\) の \(u\) と \(v\) を結ぶ辺よりコストが大きな辺があることになります。しかし、そのような辺を削除して代わりに \(u,v\) を結ぶ辺を追加することでよりコストの小さな全域木を作れることになり、\(T\) が最小全域木であるという仮定に反します。
よって、\(T\) 上での答えは \(G\) 上での答えに一致すると言えます。

\(T\) の辺数は \(K-1\) なのでこれは十分な削減です。

最小全域木を求める

最小全域木を求めるアルゴリズムはいくつかありますが、クラスカル法は \(\mathrm{O}(K^2)\) 本の辺を求める必要があるため、プリム法は辺を追加するたびにダイクストラ法を行ってコスト最小の辺を探す必要があるため本問への適用は難しいでしょう。一方、ブルーフカ法は \(\mathrm{O}(M(\log K)^2)\) で動作させることが出来ます。
具体的には、以下の手順で最小全域木 \(T\) を求めます。

• \(T\) を \(K\) 頂点 \(0\) 辺として初期化

• \(T\) が全域木になるまで以下の処理を繰り返す

  • 連結成分ごとに、その成分と異なる連結成分を結ぶ辺であってコスト最小のものを求める 。そして、求められた辺の和集合を \(T\) に追加する。

連結成分ごとに異なる連結成分を結ぶ辺を求める部分はABC245-Gの解法と同様に \(\mathrm{O}(M\log K)\) で行えます。処理の繰り返し回数は(処理後の連結成分はいずれも処理前の連結成分を\(2\) つ以上含むことを考えると) \(\mathrm{O}(\log K)\) となるため、確かに \(\mathrm{O}(M(\log K)^2)\) となっています。

別解

Adminの方に教えていただいた別解を紹介します。
各地点 \(i\) から家がある地点までの距離の最小値を \(d_i\) とします。また、\(i\) 番目の道に対して \(c_i'=c_i+d_{a_i}+d_{b_i}\)とします。
ここで、次の事実が成り立ちます。

• クエリ \((x,y,t)\) の答えが Yes になるのは、 \(c_i' \leq t\) を満たす道のみを使って \(x\) から \(y\) へ移動できる時及びその時に限る
  

証明

まず、 \(c_i'\) はある家からある家への経路であって \(i\) 番目の道を通るようなものの長さの最小値を表すため、 \(c_i' \leq t\) を満たす道のみを使って移動できない場合は No となります。
一方、\(c_i' \leq t\) を満たす道のみを使って \(x\) から \(y\) へ移動できる時、次のような移動方法を考えます。

• ある \(x\) から \(y\) への経路を考え、通る地点を順に \(p_1,\ldots ,p_k\) とする。そして、\(p_1, (p_1 から最も近い家がある地点), p_1, p_2, (p_2 から最も近い家がある地点), p_2, \ldots, p_k \) と移動する。

\((p_i から最も近い家がある地点), p_i, p_{i+1}, (p_{i+1}から最も近い家がある地点) \) の経路長は \(p_i, p_{i+1}\) 間を結ぶ道の \(c'\) に等しいため、この移動方法によって家間の移動時間が \(t\) 以下となります。よって、この場合の答えは Yes となります。

ここからの処理は1つ目に紹介した解法と重なりますが、\(d_i\) の値は地点 \(1,\ldots, K\) を始点としてダイクストラ法を行うことで \(\mathrm{O}(M\log N)\) で求められます。また、クエリへの回答はあらかじめ \(c'\) の値をソートし、 \(t\) の増加に応じて \(c' \leq t\) を満たすような道をDSUに追加しつつ \(x,y\) の連結判定を行えば良いです。