#207. 共价大爷游长沙

链接：http://uoj.ac/problem/207

题意：给一棵树，要求支持加边、删边、询问一条边是否被所有路径覆盖。同时路径端点集合有加入与删除操作。

想法：

考虑一个点与其父亲边是否被一条路径经过。
就是该路径的一端在其子树中，另一端不在。
就是其子树中一条路径的端点出现次数为奇数。随机给一条路径两端一个权值（错误概率为$\frac{n^2}{2^w}$），然后如果一个节点子树xor值等于当前路径xor值，其到父亲边就是可行的边。

然后便是LCT维护加边，删边，子树xor值。

Code $O(n \log n)$

#include < cstdio >#include < cstdlib >#include < ctime >#define gec     getchar#define FILE(F) freopen(F".in","r",stdin),freopen(F".out","w",stdout)#define DEBUG   fprintf(stderr,"Passing [%s] in Line (%d)\n",__FUNCTION__,__LINE__)typedef long long ll;typedef unsigned long long ull;template < typename T >inline void read(T &x){	x=0;bool f=0; char c=gec();	for(;c<‘0‘||c>‘9‘;c=gec())f=(c==‘-‘);	for(;c>=‘0‘&&c<=‘9‘;c=gec())x=x*10+c-‘0‘;	x=f?-x:x;}const int MAXN(100010),MAXM(300010);int n,m,u,v,x,y,X[MAXM],Y[MAXM],tp;ull QSQ,T[MAXM];ull Random(){	return rand()*1ull<<30|rand();;}namespace Link_Cut_Tree{	struct LCT	{		int nx[2],fa,rev;		ull val,sum,light;		//val:该节点xor值; sum:其子树xor值，light：其轻儿子xor值	}tr[MAXN];		void look(int x)	{		fprintf(stderr,"x%d\n",x);		fprintf(stderr,"nx[0]%d nx[1]%d fa%d\n",tr[x].nx[0],tr[x].nx[1],tr[x].fa);	}		void swap(int &x,int &y){int t(x);x=y;y=t;}	int which(int x){if(tr[tr[x].fa].nx[0]==x)return 0;if(tr[tr[x].fa].nx[1]==x)return 1;return -1;}		void update(int x)	{			tr[x].sum=tr[x].val^tr[x].light;		if(tr[x].nx[0])tr[x].sum^=tr[tr[x].nx[0]].sum;		if(tr[x].nx[1])tr[x].sum^=tr[tr[x].nx[1]].sum;	}		void push(int x)	{		if(!tr[x].rev)return ;		swap(tr[x].nx[0],tr[x].nx[1]);		tr[tr[x].nx[0]].rev^=1;		tr[tr[x].nx[1]].rev^=1;		tr[x].rev=0;	}		void rotate(int x)	{		int fa=tr[x].fa,fafa=tr[fa].fa,xd=which(x),fd=which(fa);		tr[tr[x].nx[xd^1]].fa=fa;		tr[fa].nx[xd]=tr[x].nx[xd^1];		tr[x].nx[xd^1]=fa;tr[fa].fa=x;		tr[x].fa=fafa;if(~fd)tr[fafa].nx[fd]=x;		update(fa);	}		int st[MAXN],top;	void splay(int x)	{		st[top=1]=x;		for(int t=x;~which(t);t=tr[t].fa)st[++top]=tr[t].fa;		while(top)push(st[top--]);		while(~which(x))		{			int fa=tr[x].fa;			if(~which(fa)) rotate( which(x)^which(fa)? fa : x );			rotate(x);		}		update(x);	}		void access(int x)	{		for(int t=0;x;t=x,x=tr[x].fa)		{			splay(x);			int Now=tr[x].nx[1];			if(Now)tr[x].light^=tr[Now].sum;			if(t  )tr[x].light^=tr[t  ].sum;			tr[x].nx[1]=t; update(x);		}	}		void make_root(int x)	{		access(x); splay(x); tr[x].rev^=1;	}		void link(int u,int v)	{		make_root(u); access(v); splay(v);		tr[u].fa=v; tr[v].light^=tr[u].sum; update(v);	}		void cut(int u,int v)	{		make_root(u); access(v); splay(u);		tr[u].nx[1]=0; tr[v].fa=0; update(u);	}		void Change(int x,ull D)	{		access(x); splay(x); 		tr[x].val^=D; update(x);	}		bool Que(int u,int v)	{		make_root(u); access(v); splay(u);		return tr[v].sum==QSQ;	}	}using namespace Link_Cut_Tree;int main(){#ifndef ONLINE_JUDGE	FILE("C");#endif 	int id;read(id); srand(19260817);	read(n);read(m);	for(int i=1;i<n;i++)	{		read(u);read(v);		link(u,v);	}	for(int ty,i=1;i<=m;i++)	{		read(ty);		if(ty==1)		{			read(x);read(y); cut(x,y);			read(u);read(v); link(u,v);		}else		if(ty==2)		{			++tp;			read(X[tp]);read(Y[tp]);			T[tp]=Random();QSQ^=T[tp];			Change(X[tp],T[tp]); Change(Y[tp],T[tp]);		}else		if(ty==3)		{			read(x);QSQ^=T[x];			Change(X[x],T[x]); Change(Y[x],T[x]);		}else		{			read(x);read(y);			printf(Que(x,y)?"YES\n":"NO\n");		}	}	return 0;}	

UOJ #207. 共价大爷游长沙