分治的题目，或者说分治的思想，是非常灵活多变的。
所以对我这种智商低的选手特别不友好
脑子不好使怎么办？多做题吧……
前置知识
线性基是你必须会的，不然这题不可做。
推荐再去看看洛谷P4151。
思路
看到异或最短路，显然线性基。
做题多一些的同学想必已经想到了“洛谷P4151 [WC2011]最大XOR和路径”了。
先考虑没有加边删边的做法：
- 做出原图的任意一棵生成树；
- 把每个非树边和树边形成的环丢进线性基里；
- 询问时把两点在树上的路径异或和丢进线性基里求最小异或和。
为什么要这样？见洛谷P4151题解。
有加边呢？
其实差不了多少……加一条边就往线性基里丢个环就好了。
还有删边呢？
我们按时间分治，用线段树存储每一段新加了哪些边。
每到一个点，把边都连上，然后分治左右。退出时撤销即可。
然而此时图可能不连通，连边可能连了两棵不同的树，此时需要用可撤销并查集存储树的结构和每一个点到根的异或和。由于异或有着很好的性质，我们可以把两点连边改为两棵树的根连边，而答案不变。
具体是这样的：
设要在\(x,y\)之间连权值为\(w\)的边，它们所在的树的根是\(fx,fy\)，则连一条\(fx-fy\)，权值为$w\oplus getdis(x)\oplus getdis(y) $的边。
为什么对呢？你画画图推推式子就出来了。
然后就做完了~
代码
#include<bits/stdc++.h>
namespace my_std{
using namespace std;
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,x,y) for (int i=(x);i>=(y);i--)
#define go(x) for (int i=head[x];i;i=edge[i].nxt)
#define sz 202020
typedef long long ll;
template<typename T>
inline void read(T& t)
{
t=0;char f=0,ch=getchar();
double d=0.1;
while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
if(ch=='.')
{
ch=getchar();
while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();
}
t=(f?-t:t);
}
template<typename T,typename... Args>
inline void read(T& t,Args&... args){read(t); read(args...);}
void file()
{
#ifndef ONLINE_JUDGE
freopen("a.txt","r",stdin);
#endif
}
// inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;
int n,m,Q;
map<pii,int>M;
struct hh{int f,t,w;hh(int ff=0,int tt=0,int ww=0){f=ff,t=tt,w=ww;}}edge[sz<<1];
int bg[sz<<1],ed[sz<<1];
struct HH
{
int w[34];
void ins(int x)
{
drep(i,30,0) if (x&(1<<i))
{
if (!w[i]) return (void)(w[i]=x);
x^=w[i];
}
}
int query(int x){ drep(i,30,0) if ((x^w[i])<x) x^=w[i]; return x; }
}_;
vector<hh>v[sz<<2];
#define ls k<<1
#define rs k<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
void insert(int k,int l,int r,int x,int y,hh e)
{
if (x<=l&&r<=y) return (void)v[k].push_back(e);
int mid=(l+r)>>1;
if (x<=mid) insert(lson,x,y,e);
if (y>mid) insert(rson,x,y,e);
}
int qx[sz],qy[sz];
int fa[sz],f[sz],dep[sz];
int getfa(int x){return x==fa[x]?x:getfa(fa[x]);}
int getdis(int x){return x==fa[x]?0:f[x]^getdis(fa[x]);}
struct hhh{int x,y;bool s;};
void solve(int k,int l,int r,HH G)
{
stack<hhh>S;
rep(i,0,(int)v[k].size()-1)
{
int x=v[k][i].f,y=v[k][i].t,w=v[k][i].w;
int fx=getfa(x),fy=getfa(y);
w^=getdis(x)^getdis(y);
if (fx==fy) G.ins(w);
else
{
if (dep[fx]>dep[fy]) swap(fx,fy),swap(x,y);
hhh cur=(hhh){fx,fy,0};
fa[fx]=fy;f[fx]=w;
if (dep[fx]==dep[fy]) ++dep[fy],cur.s=1;
S.push(cur);
}
}
if (l==r) printf("%d\n",G.query(getdis(qx[l])^getdis(qy[l])));
else
{
int mid=(l+r)>>1;
solve(lson,G);solve(rson,G);
}
while (!S.empty()) f[fa[S.top().x]=S.top().x]=0,dep[S.top().y]-=S.top().s,S.pop();
}
int main()
{
file();
int x,y,z;
read(n,m);
rep(i,1,n) fa[i]=i;
int c=m,tim=1;
rep(i,1,m) read(x,y,z),M[MP(x,y)]=i,bg[i]=1,ed[i]=-1,edge[i]=hh(x,y,z);
read(Q);
rep(i,1,Q)
{
read(z,x,y);
if (z==1)
{
read(z);
M[MP(x,y)]=++c;bg[c]=tim;ed[c]=-1;
edge[c]=hh(x,y,z);
}
else if (z==2) ed[M[MP(x,y)]]=tim-1;
else qx[tim]=x,qy[tim]=y,++tim;
}
--tim;
rep(i,1,c) if (ed[i]==-1) ed[i]=tim;
rep(i,1,c) if (bg[i]<=ed[i]) insert(1,1,tim,bg[i],ed[i],edge[i]);
solve(1,1,tim,_);
return 0;
}