与えられた都市と運河を無向グラフとして捉えると、このグラフの辺は、 \(1\) つのサイクルと森に分解することができます。

頂点 \(x\) から頂点 \(y\) に運ぶ荷物を考えます。
サイクル上の頂点で \(x\) との距離が一番近いものを \(x'\) とします。また、同様に \(y'\) も定めます。

森の部分の辺

森の部分の辺はそれぞれ通行するかが以下のようにすぐに決まります。

• \(x' = y'\) のとき :
  頂点 \(x\) と頂点 \(y\) が共に属する森の連結成分上の最短パスで運ぶのが最適です。
  
• \(x' \neq y'\) のとき : サイクルの部分で \(2\) 通りの通り方がありますが、森の部分の辺に関しては \(x - x'\) 間及び \(y-y'\) 間の辺が使われます

実際にそれぞれの辺が使われるかを求めるのは、木の最小共通祖先 (LCA) を求めるアルゴリズムと木上の imos 法 (最後に葉から根方向に累積和を取ることで、\(1\) 点加算を根までの全ての辺への加算に変換する) を使うと \(O(N \log(N))\) で求めることができます。

サイクルの部分の辺

サイクル部分は全ての荷物がそれぞれ \(x'\) から \(y'\) まで通りますが、それぞれサイクルのどちら側を通るかで \(2\) 通りあります。
ここで、サイクル上で通行しない辺 \(s\) を \(1\) つ決めるとします。すると各荷物は \(x'\) から \(s\) がない側を通って \(y'\) に行くしかないので経路が \(1\) つに定まります。
この辺 \(s\) をサイクルに沿って \(1\) つずつずらし、サイクルを \(1\) 周させて、その過程で全ての \(s\) について使われる辺の重みの合計が求まれば最適解が求まります。
\(1\) 周する過程で、各荷物の経路が変わるのはそれぞれ \(2\) 回 (\(s\) が \(x'\) の前後を動くときと \(y'\) の前後を動くとき) しかありません。
よって、合計 \(O(N + M)\) 回の以下の形のクエリを処理できればよいです。 (サイクル上の辺に数が書かれているとします)

• サイクル上の辺の指定された連続するいくつかの辺に \(1\) を足す
• サイクル上の辺の指定された連続するいくつかの辺から \(1\) を引く
• サイクル上の辺で \(0\) でない数字が書かれている辺の重みの合計を求める

サイクルを適当な所で切り開いて \(1\) 次元の数列の問題にすることができます (切り開いたところを跨ぐクエリも \(2\) つに分割すればよいです) :

• 数列 \(a (0\) 初期化\()\) と \(b\) (重み) がある
• \(a\) に範囲 \(1\) 加算 / 減算 を \(O(M)\) 回
• \(a_i \neq 0\) なる \(i\) についての \(b_i\) の和を求めることを \(O(N)\) 回

これはセグメント木で解くことができます。
例えば各ノードに、配下の最小値 \(\min\) と、 \(a_i = \min\) であるような \(i\) についての \(b_i\) の和を保持し、区間加算に対応するような遅延伝播セグメント木を持てば、\(a_i = 0\) なる \(i\) についての \(b_i\) の和が求まるので十分です (常に \(a_i \ge 0\) であることに注意してください)

また、もっと単純なセグメント木で処理することもできます。
元のクエリの性質上 、ある区間に \(1\) 減算クエリが来るときには全く同じ区間に対応する過去の \(1\) 加算クエリがあるはずなので、遅延伝播せず素直に指定区間に対応するセグメント木のノードに加算しても各ノードに記録されている値は常に非負です。
よってノード \(\mathrm{node}\) について
\(\mathrm{res}_{\mathrm{node}} : \mathrm{node}\) に \(0\) でない値が記録されているならそのノード下の全重み和、\(0\) ならば子ノードを \(c_1, c_2\) として \(\mathrm{res}_{c_1} + \mathrm{res}_{c_2}\)
という値を保持すると、根ノードの \(\mathrm{res}\) の値はちょうど 「\(a_i = 0\) なる \(i\) についての \(b_i\) の和」と一致します。

ハッシュを使った解法

こちらの解法は上の解法と比べて実装が楽です。
まず最初に、各荷物 \(i\) についてランダムな非負整数 \(r_i\) を決めます。
森上の辺については、上の解法と同様のことをしますが、LCA のアルゴリズムを使わず、\(1\) 加算をする代わりに同様の木上の imos 法で \(r_i\) を \(x, y\) から根までの辺全てに \(\mathrm{xor}\) します。すると LCA より根側は勝手に \(2\) つの値が \(\mathrm{xor}\) で打ち消しあうためうまく \(x - y\) パスのみ残ります。
サイクル上は以下のように考えます。

• まずサイクル上の各辺に \(0\) を書く
• 各荷物 \(i\) についてサイクルのどちら側を通るかを適当に決め、使う辺全てに \(r_i\) を \(\mathrm{xor}\) する。
• 荷物 \(i\) についてサイクル上の通る側を反転するのは、サイクル上の全ての辺に \(r_i\) を \(\mathrm{xor}\) することに対応するので、同時に使わないことにできる辺は今の時点で同じ値が書かれているものである (ハッシュが衝突しないことを仮定)
  

森上の辺で、\(\mathrm{xor}\) が \(0\) だが空でない荷物集合が出現したり、サイクル上の辺で違う荷物集合にも関わらず同じ \(\mathrm{xor}\) 値を持つものが出現したりすると誤った答えが出ます。
しかし、最初の \(r_i\) の値域を例えば \([0, 2^{63})\) 程度取っておけばこのようなことが起こる確率は無視できるほど小さくなります。
\(r_i\) を \([0, 2^d)\) から一様ランダムに選ぶとすると、ある空でない荷物集合の \(\mathrm{xor}\) 値が \(0\) になったり、\(2\) つの異なる荷物集合の \(\mathrm{xor}\) 値が等しくなったりする確率は \(\frac{1}{2^d}\) となります。よって、

• 森上の辺 : 高々 \(N\) 個の荷物集合のうち少なくとも \(1\) つの \(\mathrm{xor}\) 値が \(0\) になる確率は多くとも \(N \frac{1}{2^d}\)
  
• サイクルの辺 : 高々 \(N\) 個の異なる荷物集合のうち少なくとも \(1\) 組の \(\mathrm{xor}\) 値が等しくなる確率は多くとも \(\frac{N(N - 1)}{2} \frac{1}{2^d}\)

というように、衝突確率の評価ができます。