\(G\) のサイクルの色を、それに含まれるすべての辺の色の総 \(\mathrm{XOR}\) として定義します。

まず、\(G\) の最小全域木 \(T\) が既に与えられたときに、クエリに答えることを考えます。 \(T\) に対して、各頂点対 \((A_i, B_i)\) 間に色 \(0\) の辺を追加したグラフを \(T'\) とします。 このとき、\(T\) における \(A_i, B_i\) 間のパスに辺 \((A_i, B_i)\) を追加して得られる \(K\) 個の \(T'\) のサイクルは、\(T'\) のサイクル基底をなします。 また、\(P_i\) の値はこれらのサイクルの色に一致します。 サイクル基底を取り換えても、それが張る \(\mathbb{F}_2\) ベクトル空間は変わらないので、\(T'\) の適当なサイクル基底に対する各サイクルの色の \(\mathrm{XOR}\) 基底を管理することができればよいです。 したがって、以下のアルゴリズムによってクエリに答えることができます。

• \(\mathrm{XOR}\) 基底を管理する配列を用意する。
• \(\mathrm{XOR}\) 重み付き Union-Find を用意し、\(i = 1, \ldots, K\) について、\(A_i, B_i\) を重み \(0\) でマージする。
• \(T\) の各辺 \((u,v)\) について順番にマージする。このとき、既に \(u, v\) が同じ連結成分に含まれているときは、既存の重みとの \(\mathrm{XOR}\) をとってサイクルの色を求め、 \(\mathrm{XOR}\) 基底で Gauss の消去法をしたのち、\(0\) でなければ基底に追加する。
• 最終的な \(\mathrm{XOR}\) 基底を用いて、クエリに答える。

この方法の良いところは、重み付き Union-Find を undo 可能にすることで、辺の追加と直前のクエリの削除ができることです。

この解法を用いて、元の問題をクエリの分割統治で解くことを考えます。 最小全域木 \(T\) を管理する undo 可能 Union-Find \(D\) および、クエリに答えるための undo 可能重み付き Union-Find \(D'\) 、\(\mathrm{XOR}\) 基底を管理する配列を用意して、\(T\) に追加されうる辺集合の候補 \(S\) があるとき、区間 \([L, R)\) のクエリを再帰的に処理することを考えます。 クエリで追加される辺の重みはまだわかりませんが、クエリで追加される辺で結ばれない部分に関しては、\(S\) の辺を使う必要があります。 また、\(S\) に含まれる辺の中にサイクルがあるときは、重み最大の辺を取り除いて構いません。 したがって、\(G\) の辺集合の候補 \(S\) があるとき区間 \([L, R)\) のクエリを処理する関数 \(\operatorname{solve}(L,R,S)\) を以下のように定めることができます。

1. \(S\) に含まれる辺を重みの昇順（重みが等しい場合はインデックスの昇順）でソートする。
2. 区間 \([L, R)\) のクエリに含まれる辺をすべて \(D\) に追加する。
3. \(S\) の辺を順に \(D\) に追加する。このとき、異なる連結成分を結んだ \(S\) の辺の集合を \(T\) とする。
4. \(D\) を最初の状態に rollback する。
5. \(T\) に含まれる辺を \(D\) に追加し、同時に \(D'\) にも追加しながら \(\mathrm{XOR}\) 基底を更新する。
6. \(S \setminus T\) の辺を順に \(D\) に追加する。このとき、異なる連結成分を結んだ辺の集合を \(S'\) とする。その後、\(D\) を 5. の直後の状態までrollback する。
7. \(M = \lfloor \frac{L+R}{2} \rfloor\) とし、\(\operatorname{solve}(L,M,S')\) を呼び出す。
8. 区間 \([L, M)\) のクエリで追加された辺を \(S'\) に追加し、\(\operatorname{solve}(M,R,S')\) を呼び出す。
9. \(D, D'\) および \(\mathrm{XOR}\) 基底を最初の状態に rollback する。

最初 \(S\) に初期の \(M\) 本の辺を追加して \(\operatorname{solve}(0,Q+1,S)\) を呼び出し、\(R-L=1\) まで到達したらクエリを処理すればよいです。

計算量

undo 可能 Union-Find はクエリ \(O(\log N)\) であり、\(\mathrm{XOR}\) 基底への追加や最大値の取得は \(O(\log \max C)\) でできることに注意すると、\(\operatorname{solve}(L,R,S)\) の再帰部分以外の計算量は

\[O(|S|(\log |S| + \log N + \log \max C)+ (R-L) \log N )\]

です。 \(\operatorname{solve}(L,R,S)\) において、\(T\) に含まれる辺を追加した時点で、\(D\) の連結成分の個数は高々 \(R-L+1\) 個です。 これは、この時点の \(D\) に区間 \([L, R)\) のクエリに含まれる辺をすべて追加すると、連結成分が \(1\) 個になることから従います。 したがって、\(S'\) に含まれる辺の個数は高々 \(R-L\) 本です。 よって、再帰の各深さにおける \(|S|\) の合計は \(O(Q)\) (ただし一番上の階層だけは \(O(M)\)) であり、深さの上限は \(O(\log Q)\) なので、全体の計算量は

\[O(M (\log M + \log \max C) + K \log N + Q \log Q (\log \max C + \log N + \log Q))\]

となります。