#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. 共价大爷游长沙

#207. 共价大爷游长沙

最新文章

热门文章