神仙题！
我们考虑一条边被所有路径经过，那么以这条边的一个端点为根，所有路径都恰有一个端点落在另一个端点为根的子树中。
这个过程我们用哈希随机一个数值维护异或和就可以了。
然后就是标准的子树信息LCT啦。
我个睿智忘了写push...以为写错了，然后看标程改改改以为过不了第二个样例，实际上是太长了没显示出来...
把最开始的代码加了个push也过了...哭（
//Love and Freedom. #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define ll long long #define inf 20021225 #define N 300010 #define ls(x) t[x].son[0] #define rs(x) t[x].son[1] #define fa(x) t[x].fa #define nrt(x) (ls(fa(x))==x||rs(fa(x))==x) using namespace std; int read() { int s=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return f*s; } struct node{int fa,son[2],cnt,sum; bool tag;}t[N]; int a[N]; void pushup(int x){t[x].sum=a[x]^t[x].cnt^t[ls(x)].sum^t[rs(x)].sum;} void rotate(int x) { if(!nrt(x)||!x) return; int f=fa(x),gf=fa(f); int k=rs(f)==x,p=k^1; if(nrt(f)) t[gf].son[rs(gf)==f]=x; if(t[x].son[p]) t[t[x].son[p]].fa=f; t[f].son[k]=t[x].son[p]; t[x].son[p]=f; t[x].fa=gf; t[f].fa=x; pushup(f); pushup(x); } void pushdown(int x) { if(t[x].tag) { swap(ls(x),rs(x)); if(ls(x)) t[ls(x)].tag^=1; if(rs(x)) t[rs(x)].tag^=1; t[x].tag=0; } } void push(int x) { if(nrt(x)) push(fa(x)); pushdown(x); } void splay(int x) { push(x); while(nrt(x)) { int f=fa(x),gf=fa(f); if(nrt(gf)) rotate((rs(gf)==f)^(rs(f)==x)?x:f); rotate(x); } } void access(int x) { int y=0; do { splay(x); t[x].cnt^=t[y].sum^t[rs(x)].sum; t[x].son[1]=y; pushup(x); y=x; x=fa(x); }while(x); } void makeroot(int x) { access(x); splay(x); t[x].tag=1; } int findroot(int x) { access(x); splay(x); while(ls(x)) x=ls(x); return x; } void split(int x,int y) { makeroot(x); access(y); splay(y); } void cut(int x,int y) { split(x,y); t[y].son[0]=t[x].fa=0; pushup(y); pushup(x); } void link(int x,int y) { split(x,y); if(findroot(y)==x) return; t[y].cnt^=t[x].sum; t[x].fa=y; } int my_rand() { return rand()<<15|rand(); } int val,V[N],tot,X[N],Y[N]; int main() { int id=read(); srand(20021225); int n=read(),m=read(); for(int i=1;i<n;i++) { int x=read(),y=read(); link(x,y); } while(m--) { int opt=read(); if(opt==1) { int x=read(),y=read(),u=read(),v=read(); cut(x,y); link(u,v); } else if(opt==2) { int x=read(),y=read(); int v=my_rand(); V[++tot]=v; X[tot]=x; Y[tot]=y; access(x); splay(x); a[x]^=v; pushup(x); access(y); splay(y); a[y]^=v; pushup(y); val^=v; } else if(opt==3) { int p=read(),v=V[p],x=X[p],y=Y[p]; access(x); splay(x); a[x]^=v; pushup(x); access(y); splay(y); a[y]^=v; pushup(y); val^=v; } else if(opt==4) { int x=read(),y=read(); split(x,y); puts(t[x].sum==val?"YES":"NO"); } } return 0; }