解説

頂点 $s$ から頂点 $t$ までの経路を考えます。このとき $s$ から頂点番号を +1 することで $t$ までたどり着く最短経路で通る $s,t$ 以外の頂点を $L$ とします。

このとき、 $s \rightarrow L \rightarrow t$ という walk が考えられます。 この walk に含まれる頂点の重みのビット単位 $XOR$ はそれぞれ、$s,L,t$ に含まれる頂点を全て $XOR$ したものです。以後、この値を $f(s,L,t)$ のように表します。

さて、別の walk についても考えてみましょう。 $t$ から頂点番号を +1 することで $s$ までたどり着く最短経路で通る $s,t$ 以外の頂点を $R$ とします。このとき、一度 $t$ に着いてから一周する、 $s \rightarrow L \rightarrow t \rightarrow R \rightarrow s \rightarrow L \rightarrow t$ も walk です。 この walk に含まれる頂点の重みのビット単位 $XOR$ は $f(s,L,t,R,s,L,t)$ です。 ここで、 $a XOR a = 0$ より、この値は $f(R)$ に等しくなります。

さらに $t$ から一周したとき、walk に $R,s,L,t$ が追加されるので、 walk に含まれる頂点の重みのビット単位 $XOR$ は $f(R,R,s,L,t)$ 、 つまり最短経路の walk に含まれる頂点の重みのビット単位 $XOR$ $f(s,L,t)$ に一致します。 よって、walk に含まれる頂点の重みのビット単位 $XOR$ は $t$ から一周するたびに $f(s,L,t)$ と$f(R)$　を繰り返します。

よって、求める答えは $max(f(s,L,t),f(R))$ です。

$f(s,L,t) = W_s \oplus W_{s+1} \oplus ... \oplus W_{t}$ 、

$f(R) = W_{t+1} \oplus W_{t+2} \oplus ... \oplus W_{s-1}$

なので、累積 $XOR$ を前計算することによって 答えを各クエリ当たり $O(1)$ で計算することができます。

ただし、$s > t$ の場合は $... W_{N-1},W_{N},W_{1},...$ と続くことに注意してください。