【UOJ207】共价大爷游长沙(Link-Cut Tree,随机化)
【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; }
相关推荐
melissahexiu 2010-07-09
优主张 2018-01-09
OccamsRazor 2017-12-09
青梅煮史各种视角下的历史学 2017-12-09
OccamsRazor 2017-12-08
玲珑 2017-12-07
灰猫奇异事务所 2017-12-06
扑克投资家 2017-12-04
高杉LEGAL 2017-12-02
世界说 2017-11-28
雅趣 2017-10-04
古诗词文化 2016-11-21
诗词名句 2016-11-09
诗词名句 2016-11-09