题目大意：
给一颗动态树，给出一些路径并动态修改，每次询问一条边是否被所有路径覆盖。
题解：
先%一发myy。
开始感觉不是很可做的样子，发现子树信息无论维护什么都不太对……
然后打开题目标签……随机化……
emmmm，突然想到[bzoj 3569]DZY loves Chinese II……
随机大法好…
给每条路径随机一个权值，然后用异或来统计子树权值和，并与全集的异或和做下比较，然后就是LCT大板子……
板子写挂……wa了两遍……迷。
代码：
#include "bits/stdc++.h"
inline int read(){
int s=,k=;char ch=getchar();
while (ch<''|ch>'') ch=='-'?k=-:,ch=getchar();
while (ch>&ch<='') s=s*+(ch^),ch=getchar();
return s*k;
}
using namespace std;
const int N=2e5+;
namespace LCT{
#define rev(t) (t?t->rev^=1:0)
#define is_root(t) (!t->fa||(t->fa->son[0]!=t&&t->fa->son[1]!=t))
#define son(t) (t->fa->son[1]==t)
#define size(t) (t?t->size:0)
struct node{
node *fa,*son[];
int rev,size,empty;
node () {fa=son[]=son[]=NULL,empty=rev=size=;}
inline void update(){
size=size(son[])^size(son[])^empty;
}
inline void pushdown(){
if (!rev) return ;
rev(son[]),rev(son[]);
swap(son[],son[]);rev=;
}
}tree[N/],*tmp[N/];
inline void rotate(node *p){
int a=son(p)^;node *f=p->fa;
f->son[a^]=p->son[a];
if (p->son[a]) p->son[a]->fa=f;
p->fa=f->fa;
if (!is_root(f)) f->fa->son[son(f)]=p;
f->fa=p,p->son[a]=f,f->update(),p->update();
}
inline void update(node *p){
if (!is_root(p)) update(p->fa);
p->pushdown();
}
inline void splay(node *p){
register int pos=;
for(node *t=p;;t=t->fa){
tmp[++pos]=t;
if(is_root(t)) break;
}
for(;pos;--pos) tmp[pos]->pushdown();
for(;!is_root(p);rotate(p))
if(!is_root(p->fa)) rotate(son(p)==son(p->fa)?p->fa:p);
}
inline void access(node *p){
for(node *pre=NULL;p;pre=p,p=p->fa)
splay(p),p->empty^=size(p->son[])^size(pre),p->son[]=pre,p->update();
}
inline void make_root(node *x) {
access(x),splay(x),x->rev^=;
}
inline void link(node *x,node *y) {
make_root(x);access(y),splay(y),x->fa=y;
y->empty^=size(x),y->update();
}
inline void cut(node *x,node *y){
make_root(x),access(y),splay(y);
x->fa=y->son[]=NULL;y->update();
}
inline int query(node *x,node *y) {
make_root(x);access(y),splay(y);
return size(x);
}
}
int n,m;
int a[N],b[N],c[N],cnt,tot;
int main (int argc, char const* argv[]){
//freopen("207.in","r",stdin);
read();
srand();
n=read(),m=read();
register int i;
using namespace LCT;
for (i=;i<n;++i) {
int x=read(),y=read();
link(tree+x,tree+y);
}
int type,x,y,u,v;
while (m--) {
type=read();
switch (type) {
case : x=read(),y=read(),u=read(),v=read(),cut(tree+x,tree+y),link(tree+u,tree+v);
break;
case : x=read(),y=read(),u=rand();
make_root(&tree[x]),tree[x].empty^=u,tree[x].update(),
make_root(&tree[y]),tree[y].empty^=u,tree[y].update();
++cnt,a[cnt]=x,b[cnt]=y,c[cnt]=u,tot^=u;
break;
case : x=read();u=c[x],y=b[x],x=a[x];
make_root(&tree[x]),tree[x].empty^=u,tree[x].update(),
make_root(&tree[y]),tree[y].empty^=u,tree[y].update();
tot^=u;
break;
case : x=read(),y=read();
printf("%s\n",tot==query(tree+x,tree+y)?"YES":"NO");
break;
}
}
}