[UOJ207]共价大爷游长沙

UOJ

sol

这题真是太神啦！

对于S集合中的每个点对，给他们随机附上一个相同权值。

两个点在边(x,y)的两侧当且仅当一个点在x的子树中，另一个点不在x的子树中（假设x是y的儿子）

维护一下子树点权异或和，若x子树的异或和等于所有点对权值的异或和就说明(x,y)是一条必经边

splay终于使用正常方法写 祭

这种算法是可以卡的吧...

code

#include<cstdio>

#include<algorithm>

#include<ctime>

using namespace std;

const int N = 100005;

int gi()

{

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

int n,m,fa[N],ch[2][N],rev[N],val[N],sz[N],sum[N],Stack[N],top,tot,all;

bool son(int x){return ch[1][fa[x]]==x;}

bool isroot(int x){return ch[0][fa[x]]!=x&&ch[1][fa[x]]!=x;}

void pushup(int x){sum[x]=sum[ch[0][x]]^sum[ch[1][x]]^sz[x]^val[x];}

void reverse(int x){if(!x)return;swap(ch[0][x],ch[1][x]);rev[x]^=1;}

void pushdown(int x){if(!rev[x])return;reverse(ch[0][x]);reverse(ch[1][x]);rev[x]=0;}

void rotate(int x)

{

	int y=fa[x],z=fa[y],c=son(x);

	ch[c][y]=ch[c^1][x];if (ch[c][y]) fa[ch[c][y]]=y;

	fa[x]=z;if (!isroot(y)) ch[son(y)][z]=x;

	ch[c^1][x]=y;fa[y]=x;pushup(y);

}

void splay(int x)

{

	Stack[top=1]=x;

	for (int y=x;!isroot(y);y=fa[y]) Stack[++top]=fa[y];

	while (top) pushdown(Stack[top--]);

	for (int y=fa[x];!isroot(x);rotate(x),y=fa[x])

		if (!isroot(y)) son(x)^son(y)?rotate(x):rotate(y);

	pushup(x);

}

void access(int x)

{

	for (int y=0;x;y=x,x=fa[x])

	{

		splay(x);

		sz[x]^=sum[y]^sum[ch[1][x]];

		ch[1][x]=y;

		pushup(x);

	}

}

void makeroot(int x){access(x);splay(x);reverse(x);}

void split(int x,int y){makeroot(x);access(y);splay(y);}

void link(int x,int y){makeroot(x);makeroot(y);fa[x]=y;sz[y]^=sum[x];pushup(y);}

void cut(int x,int y){split(x,y);ch[0][y]=fa[x]=0;}

void modify(int u,int v){makeroot(u);val[u]^=v;pushup(u);}

struct node{int x,y,v;}S[N<<2];

int main()

{

	srand(141905&141936);

	gi();n=gi();m=gi();

	for (int i=1,u,v;i<n;i++)

		u=gi(),v=gi(),link(u,v);

	while (m--)

	{

		int opt=gi();

		if (opt==1)

		{

			int x=gi(),y=gi(),u=gi(),v=gi();

			cut(x,y);link(u,v);

		}

		if (opt==2)

		{

			int x=gi(),y=gi(),v=rand()%(1<<30);

			S[++tot]=(node){x,y,v};all^=v;

			modify(x,v);modify(y,v);

		}

		if (opt==3)

		{

			int x=gi();all^=S[x].v;

			modify(S[x].x,S[x].v);modify(S[x].y,S[x].v);

		}

		if (opt==4)

		{

			int x=gi(),y=gi();

			split(x,y);puts(sum[x]==all?"YES":"NO");

		}

	}

	return 0;

}