【UOJ207】共价大爷游长沙（Link-Cut Tree，随机化）
题面
UOJ
题解
这题太神了
\(\%\%\%myy\)
看到动态的维护边很容易的想到了\(LCT\)
然后能否堵住一条路
我们也不难想到，以这条路的一个端点为根的子数
是否恰好包含了集合中所有点对的中的恰好一个点
但是怎么算恰好包括了一个点。。。
不会呀。。。
\(\%\%\%myy\)神奇的随机算法
对于每个点对，
就给这两个点随便随机一个点权
维护子树异或和
这样就可以检查子树异或和是否恰好和所有权值的异或和相等
把随机数开大点，这样就很难出错（太神了）
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 120000
#define lson (t[x].ch[0])
#define rson (t[x].ch[1])
inline int read()
{RG int x=0,t=1;RG char ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')t=-1,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();return x*t;
}
int n,m;
struct Node
{int ch[2],ff;int rev;int v,sum,ss;
}t[MAX];
int S[MAX],top;
bool isroot(int x){return t[t[x].ff].ch[0]!=x&&t[t[x].ff].ch[1]!=x;}
void pushup(int x){t[x].sum=t[lson].sum^t[rson].sum^t[x].ss^t[x].v;}
void rotate(int x)
{int y=t[x].ff,z=t[y].ff;int k=t[y].ch[1]==x;if(!isroot(y))t[z].ch[t[z].ch[1]==y]=x;t[x].ff=z;t[y].ch[k]=t[x].ch[k^1];t[t[x].ch[k^1]].ff=y;t[x].ch[k^1]=y;t[y].ff=x;pushup(y);pushup(x);
}
void pushdown(int x)
{if(t[x].rev){swap(lson,rson);t[lson].rev^=1;t[rson].rev^=1;t[x].rev^=1;}
}
void Splay(int x)
{S[top=1]=x;for(int i=x;!isroot(i);i=t[i].ff)S[++top]=t[i].ff;while(top)pushdown(S[top--]);while(!isroot(x)){int y=t[x].ff,z=t[y].ff;if(!isroot(y))(t[z].ch[1]==y)^(t[y].ch[1]==x)?rotate(x):rotate(y);rotate(x);}
}
void access(int x)
{for(int y=0;x;y=x,x=t[x].ff){Splay(x);t[x].ss^=t[y].sum^t[rson].sum;t[x].ch[1]=y;pushup(x);}
}
void makeroot(int x){access(x);Splay(x);t[x].rev^=1;}
void split(int x,int y){makeroot(x);access(y);Splay(y);}
void cut(int x,int y){split(x,y);t[y].ch[0]=t[x].ff=0;pushup(y);}
void link(int x,int y){makeroot(x);makeroot(y);t[x].ff=y;t[y].ss^=t[x].sum;pushup(y);}
void Add(int x,int w){makeroot(x);t[x].v^=w;pushup(x);}
struct Pr{int x,y,v;}p[MAX<<2];
int tot,ss;
int main()
{srand(time(NULL));read();n=read();m=read();for(int i=1;i<n;++i)link(read(),read());int opt,x,y,u,v;while(m--){opt=read();if(opt==1){x=read(),y=read(),u=read(),v=read();cut(x,y);link(u,v);}else if(opt==2){x=read(),y=read(),v=rand()%19260817+1;ss^=v;p[++tot]=(Pr){x,y,v};Add(x,v);Add(y,v);}else if(opt==3){x=read();ss^=p[x].v;Add(p[x].x,p[x].v);Add(p[x].y,p[x].v);}else{x=read();y=read();split(x,y);(t[y].ss^t[y].v)==ss?puts("YES"):puts("NO");}}return 0;
}
