\(d(s,t)\) の定義は、次のように言うこともできます：「最小全域木における \(st\) パス上の辺重みの最大値」

クエリに答えるには、次ができればよいです。

• 1 つの辺の重みを変更する
• 変更後のグラフの最小全域木において、\(st\) パス上の辺重みの最大値を求める

なお本問では辺重みの変更は \(+1\) に限定されていますが、本解説では任意の辺重みの変更に対応します。

最初のグラフでの最小全域木をひとつとり、\(T\) とします。

\(T\) における辺重みの変更や、パス上の辺重みの最大値を求めることは、HLD を用いた基本的なパスクエリ処理で \(O(N\log^2N)\) 時間でできます。あとは、最小全域木が変化する場合に対応すれば十分です。

変更辺を \(e\) とします。

\(e\) が \(T\) 上にある場合

\(e\) を削除した場合の最小全域木の変化を考えましょう。\(e\) を削除すると、\(T\) は \(2\) つの連結成分 \(A, B\) に分かれます。\(AB\) 間を結ぶ辺があれば、そのうち最小重みのものを \(f\) として、最小全域木は \(T - e + f\) に変化します（より正確には、そのような形の最小全域木が少なくともひとつ存在します）。

各辺 \(e\) に対して \(T-e+f\) が木になるような \(f \notin T\) のうち、重み最小のものを求めておておくことが課題となります。逆に \(f\) に対して \(e\) がどのようなものかを考えると、このような \(e\) は \(f\) の両端点を結ぶ \(T\) 上のパス上の辺です。よって各 \(e\) に対して最適な \(f\) を計算することは、双対セグ木と HLD を用いたパスクエリなどによってできます。

\(e\) が \(T\) 上にない場合

この場合、\(T\) の変化としてありうるものは \(T+e-f\) の形ですが、やはり \(f\) は \(T\) におけるパス上で重さ最大の辺として計算できます。

なお、このような \(e\) を削除して最小全域木が変化するのは 辺重みが減少する場合だけなので、この議論は本問では不要です。