都市 \(u\) から都市 \(v\) へ移動する際に通る辺の数の最小値を \(\mathrm{dist}(u, v)\) とします。また、初期状態でのパス \(u - v\) 上の辺の重みの和を \(\mathrm{weight}(u, v)\) とします。これは、適切な前計算により、 \(1\) 回あたり \(\Theta(1)\) 時間や \(\Theta(\log N)\) 時間などで計算することができます。

都市 \(x\) から都市 \(y\) に移動するときは、どのような場合であってもパス \(x - y\) をまっすぐ通るのが最善です。

都市 \(x_0\) から始めて都市 \(x_1, x_2, \ldots, x_r\) をこの順に訪れ最後に都市 \(x_0\) に戻ってくるときのコストを考えましょう。全ての辺は偶数回通ることになり、 ある辺を \(2\) 回通るとコストが \(1\) 増えることから、コストの最小値は \((\mathrm{dist}(x_0, x_1) + \mathrm{dist}(x_1, x_2) + \ldots + \mathrm{dist}(x_{r - 1}, x_r) + \mathrm{dist}(x_r, x_0)) / 2\) です。

実際にはパス \(x_r - x_0\) 上の辺はは通らないので、それを引く必要があります。都市 \(x_r\) に到着した瞬間、パス \(x_r - x_0\) 上の辺はそれぞれ奇数回通られているので、都市 \(x_r\) から都市 \(x_0\) に移動する際のコストは、 \(\mathrm{dist}(x_r, x_0) - \mathrm{weight}(x_r, x_0)\) です。よって、タイプ 2 のクエリの答えは \((\mathrm{dist}(x_0, x_1) + \mathrm{dist}(x_1, x_2) + \ldots + \mathrm{dist}(x_{r - 1}, x_r) + \mathrm{dist}(x_r, x_0)) / 2 - \mathrm{dist}(x_r, x_0) + \mathrm{weight}(x_r, x_0)\) です。

タイプ 2 のクエリを処理する際には、最初に述べた通り \(\mathrm{dist}(x_r, x_0)\) と \(\mathrm{weight}(x_r, x_0)\) は高速に計算できるので、 \(\sum_{i=0}^{r-1} \mathrm{dist}(x_i, x_{i+1})\) がわかれば良いです。よって、 \(d_i = \mathrm{dist}(x_i, x_{i+1})\) として、 \(d\) をセグメント木を用いて管理することで、各クエリを \(O(\log N)\) 時間で処理することができます。