最小全域木を取ります。 旅は、存在しないか最小全域木上の最短パスになっています。

実際、最小全域木上の最短パス以外のパスが危険度最小の旅となっていたとすると、最小全域木の最小性に矛盾します。

よって、この操作は最小全域木上の辺が取り除かれたときに分割される二つの部分木を結んでいる辺を再度取り除く、という操作であることがわかります。

再度取り除く際に最小全域木上の辺が取り除かれることがないことから、操作の繰り返しは起きないことがわかります。

実は、二つの部分木のうち小さい方を端点に持つ辺を全走査しても十分高速に動作することがわかります。以下それを示します。

小さい方を全走査するというのは weighted union heuristic(マージテクとも呼ばれています)の逆操作です。

よって、各頂点が走査される回数は高々 \(\mathcal{O}(log N)\) 回であることが示され、各辺が走査される回数も同様に \(\mathcal{O}(log N)\) 回であることがわかります。

分かれた二つの部分木のうち、どちらが小さい方かを判定する方法

両方の部分木に対して、dfs のステップを 1 つずつ交互に進めます。 片方が終わった段階で打ち切ればよいです。

計算量は全体で \(\mathcal{O}((N + M) log N + Q)\) です。