题目让我们维护一个连通无向图，边有边权，支持加边删边和询问从\(x\)到\(y\)的异或最短路。
考虑到有删边这样的撤销操作，那么用线段树分治来实现，用线段树来维护询问的时间轴。
将每一条边的出现时间段标记到线段树上，表示在这一段询问中这条边存在。
异或最短路的处理方法与最大XOR和路径类似，给线段树上每个节点开一个线性基，找出当前所有的环，插入该节点的线性基，查询时任意找出一条从\(x\)到\(y\)的路径，到线性基中查询，即为答案。
具体实现时用可撤销并查集，采用按秩合并来优化，因为路径压缩会破坏树的结构。
具体实现细节看代码吧。
\(code:\)
#include<bits/stdc++.h>
#define maxn 400010
using namespace std;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n,m,q,num,tree_cnt,edge_cnt,root,top;
int ls[maxn],rs[maxn],pre[maxn],nxt[maxn],ans[maxn];
map<pair<int,int>,int> mp;
struct Edge
{
int x,y,v;
}e[maxn];
struct node
{
int x,y,deep;
}st[maxn];
struct query
{
int x,y;
}qu[maxn];
void build(int l,int r,int &cur)
{
if(!cur) cur=++tree_cnt;
if(l==r) return;
int mid=(l+r)>>1;
build(l,mid,ls[cur]);
build(mid+1,r,rs[cur]);
}
vector<int> v[maxn];
void insert(int L,int R,int l,int r,int id,int cur)
{
if(L<=l&&R>=r)
{
v[cur].push_back(id);
return;
}
int mid=(l+r)>>1;
if(L<=mid) insert(L,R,l,mid,id,ls[cur]);
if(R>mid) insert(L,R,mid+1,r,id,rs[cur]);
}
int a[maxn][40];
void ins(int x,int cur)
{
for(int i=30;i>=0;--i)
{
if(x&(1<<i))
{
if(!a[cur][i])
{
a[cur][i]=x;
break;
}
else x^=a[cur][i];
}
}
}
int get(int x,int cur)
{
for(int i=30;i>=0;--i)
if((x^a[cur][i])<x)
x^=a[cur][i];
return x;
}
int fa[maxn],de[maxn],dis[maxn];
int find(int x)
{
return fa[x]==x?x:find(fa[x]);
}
int xor_dis(int x)
{
return fa[x]==x?dis[x]:dis[x]^xor_dis(fa[x]);
}
void merge(int x,int y,int v)
{
if(de[x]<de[y]) swap(x,y);
st[++top]=(node){x,y,de[x]};
fa[y]=x,dis[y]=v,de[x]=max(de[x],de[y]+1);
}
void del(int id)
{
int x=st[id].x,y=st[id].y;
fa[y]=y,dis[y]=0,de[x]=st[id].deep;
}
void copy(int x,int y)
{
for(int i=0;i<=30;++i) a[y][i]=a[x][i];
}
void dfs(int l,int r,int cur)
{
int now=top,size=v[cur].size();
for(int i=0;i<size;++i)
{
int id=v[cur][i],x=e[id].x,y=e[id].y,v=e[id].v;
v^=xor_dis(x)^xor_dis(y),x=find(x),y=find(y);
if(x==y) ins(v,cur);
else merge(x,y,v);
}
if(l==r)
{
int x=qu[l].x,y=qu[l].y;
ans[l]=get(xor_dis(x)^xor_dis(y),cur);
}
else
{
int mid=(l+r)>>1;
copy(cur,ls[cur]),dfs(l,mid,ls[cur]);
copy(cur,rs[cur]),dfs(mid+1,r,rs[cur]);
}
while(top>now) del(top--);
}
int main()
{
read(n),read(m),edge_cnt=m;
for(int i=1;i<=n;++i) fa[i]=i;
for(int i=1;i<=m;++i)
{
read(e[i].x),read(e[i].y),read(e[i].v);
mp[make_pair(e[i].x,e[i].y)]=i,pre[i]=1,nxt[i]=-1;
}
read(q);
while(q--)
{
int opt,x,y,v;
read(opt);
if(opt==1)
{
read(x),read(y),read(v);
e[++edge_cnt]=(Edge){x,y,v};
mp[make_pair(x,y)]=edge_cnt;
pre[edge_cnt]=num+1,nxt[edge_cnt]=-1;
}
if(opt==2)
{
read(x),read(y);
nxt[mp[make_pair(x,y)]]=num;
}
if(opt==3)
{
read(x),read(y);
qu[++num]=(query){x,y};
}
}
build(1,num,root);
for(int i=1;i<=edge_cnt;++i)
{
if(nxt[i]<0) nxt[i]=num;
if(pre[i]<=nxt[i]) insert(pre[i],nxt[i],1,num,i,root);
}
dfs(1,num,root);
for(int i=1;i<=num;++i)
printf("%d\n",ans[i]);
return 0;
}