给你一张无向连通图，支持三种操作：
- 插入一条边 \((u, v, w)\)。
- 删除一条边。
- 求 \((u, v)\) 之间的异或最短路。
\(n, m, 1 < 2^{30}\)。
先考虑异或最短路怎么求，这部分和 最大XOR和路径 是一样的。就是把图上的环都扔到一个线性基里，每次查询就是线性基上查询异或最小值。
再考虑加上加边操作。就是维护一棵图的生成树，要是加入的这一条边没有形成环就把它加到生成树中，形成了环就是把环长扔到线性基里，环长可以通过生成树上到根的路径的异或和来算。这部分用并查集维护即可。
加上删边就是套一个线段树分治，再把并查集改成可撤销并查集。
时间复杂度 \(O(n \log^2 n)\)。
constexpr int MAXN = 2e5 + 9, MAXM = MAXN << 1;
int n, m, q, st[MAXM], ed[MAXM];
map<pii, int> idx;
pair<int, int> qry[MAXN];
array<int, 3> E[MAXM];
struct Base_Line {
static constexpr int N = 31;
int a[N];
void Insert(int x) {
for (int i = 30; ~i; i --) if (x >> i & 1) {
if (a[i]) x ^= a[i];
else { a[i] = x; break; }
}
return;
}
int Query(int x) {
for (int i = 30; i >= 0; i --)
if (x >> i & 1) x ^= a[i];
return x;
}
} ds;
struct Disjoint {
int fa[MAXN], sz[MAXN], dis[MAXN];
vector<pair<int, int> > stk;
void Init(int n) {
for (int i = 1; i <= n; i ++)
fa[i] = i, dis[i] = 0, sz[i] = 1;
return;
}
int Find(int u) {
return fa[u] == u ? u : Find(fa[u]);
}
int Get_Dis(int u) {
return fa[u] == u ? 0 : dis[u] ^ Get_Dis(fa[u]);
}
bool Merge(int u, int v, int w) {
w ^= Get_Dis(u) ^ Get_Dis(v);
u = Find(u), v = Find(v);
if (u == v) return false;
if (sz[u] > sz[v]) swap(u, v);
stk.emplace_back(u, v);
fa[u] = v, dis[u] ^= w, sz[v] += sz[u];
return true;
}
void Reset() {
auto [u, v] = stk.back(); stk.pop_back();
fa[u] = u, sz[v] -= sz[u], dis[u] = 0; return;
}
} D;
namespace Segment_Tree {
vector<int> upd[MAXN << 2];
void Update(int l, int r, int id, int L = 1, int R = q, int p = 1) {
if (l <= L && R <= r) return upd[p].emplace_back(id), void();
int Mid = L + R >> 1;
if (l <= Mid) Update(l, r, id, L, Mid, p << 1);
if (Mid < r) Update(l, r, id, Mid + 1, R, p << 1 | 1);
return;
}
void Solve(int L = 1, int R = q, int p = 1) {
int tp = D.stk.size();
Base_Line ret = ds;
auto Get_Dis = [&](int u, int v) { return D.Get_Dis(u) ^ D.Get_Dis(v); };
for (auto i : upd[p]) {
auto [u, v, w] = E[i];
if (D.Find(u) == D.Find(v)) ds.Insert(Get_Dis(u, v) ^ w);
else D.Merge(u, v, w);
}
int Mid = L + R >> 1;
if (L == R) {
auto [u, v] = qry[L];
if (u) Write(ds.Query(Get_Dis(u, v)), '\n');
}
else Solve(L, Mid, p << 1), Solve(Mid + 1, R, p << 1 | 1);
while (D.stk.size() ^ tp) D.Reset(); ds = ret;
return;
}
}
void slv() {
n = Read<int>(), m = Read<int>();
for (int i = 1; i <= m; i ++) {
int u = Read<int>(), v = Read<int>(), w = Read<int>();
E[i] = {u, v, w}, idx[make_pair(u, v)] = i, st[i] = 1, ed[i] = -1;
}
q = Read<int>();
for (int i = 1; i <= q; i ++) {
int opt = Read<int>();
if (opt == 1) {
int u = Read<int>(), v = Read<int>(), w = Read<int>();
E[++ m] = {u, v, w}, idx[make_pair(u, v)] = m, st[m] = i, ed[m] = -1;
} else if (opt == 2) {
int u = Read<int>(), v = Read<int>();
ed[idx[make_pair(u, v)]] = i - 1;
} else {
int u = Read<int>(), v = Read<int>();
qry[i] = {u, v};
}
}
for (int i = 1; i <= m; i ++) {
if (ed[i] == -1) ed[i] = q;
if (st[i] <= ed[i])Segment_Tree::Update(st[i], ed[i], i);
}
D.Init(n); Segment_Tree::Solve();
return;
}