BZOJ2819 Nim

原题链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2819

Nim

Description

著名游戏设计师vfleaking，最近迷上了Nim。普通的Nim游戏为：两个人进行游戏，N堆石子，每回合可以取其中某一堆的任意多个，可以取完，但不可以不取。谁不能取谁输。这个游戏是有必胜策略的。于是vfleaking决定写一个玩Nim游戏的平台来坑玩家。

为了设计漂亮一点的初始局面，vfleaking用以下方式来找灵感：拿出很多石子，把它们聚成一堆一堆的，对每一堆编号1,2,3,4,…n,在堆与堆间连边，没有自环与重边，从任意堆到任意堆都只有唯一一条路径可到达。然后他不停地进行如下操作：

1.随机选两个堆v,u，询问若在v到u间的路径上的石子堆中玩Nim游戏，是否有必胜策略，如果有，vfleaking将会考虑将这些石子堆作为初始局面之一，用来坑玩家。
2.把堆v中的石子数变为k。

由于vfleaking太懒了，他懒得自己动手了。请写个程序帮帮他吧。

Input

第一行一个数n，表示有多少堆石子。

接下来的一行，第i个数表示第i堆里有多少石子。

接下来n-1行，每行两个数v,u，代表v,u间有一条边直接相连。

接下来一个数q，代表操作的个数。

接下来q行，每行开始有一个字符：
如果是Q，那么后面有两个数v,u，询问若在v到u间的路径上的石子堆中玩Nim游戏，是否有必胜策略。
如果是C，那么后面有两个数v,k，代表把堆v中的石子数变为k。

对于100%的数据：
1≤N≤500000, 1≤Q≤500000, 0≤任何时候每堆石子的个数≤32767
其中有30%的数据：
石子堆组成了一条链，这3个点会导致你DFS时爆栈（也许你不用DFS？）。其它的数据DFS目测不会爆。

注意：石子数的范围是0到INT_MAX

Output

对于每个Q，输出一行Yes或No，代表对询问的回答。

Sample Input

5
1 3 5 2 5
1 5
3 5
2 5
1 4
6
Q 1 2
Q 3 5
C 3 7
Q 1 2
Q 2 4
Q 5 3

Sample Output

Yes
No
Yes
Yes
Yes

题解

如果每堆的石子数异或起来不为$0$，则有必胜策略。

我$\mathcal{L}\mathcal{C}\mathcal{T}$打板贼$6$。

代码

#prag\
ma GCC optimize(2)
#include<bits/stdc++.h>
#define ls son[v][0]
#define rs son[v][1]
using namespace std;
const int M=5e5+5;
int son[M][2],dad[M],sum[M],val[M],n,m;
bool rev[M];
char ch[5];
bool notroot(int v){return son[dad[v]][0]==v||son[dad[v]][1]==v;}
void up(int v){sum[v]=sum[ls]^val[v]^sum[rs];}
void turn(int v){swap(ls,rs),rev[v]^=1;}
void push(int v){if(!rev[v])return;if(ls)turn(ls);if(rs)turn(rs);rev[v]=0;}
void down(int v){if(notroot(v))down(dad[v]);push(v);}
void spin(int v)
{
	int f=dad[v],ff=dad[f],k=son[f][1]==v,w=son[v][!k];
	if(notroot(f))son[ff][son[ff][1]==f]=v;son[v][!k]=f,son[f][k]=w;
	if(w)dad[w]=f;dad[f]=v,dad[v]=ff;
	up(f);
}
void splay(int v)
{
	down(v);
	for(int f,ff;notroot(v);spin(v))
	{
		f=dad[v],ff=dad[f];
		if(notroot(f))spin((son[f][0]==v)^(son[ff][0]==f)?v:f);
	}
	up(v);
}
void access(int v){for(int f=0;v;v=dad[f=v])splay(v),rs=f,up(v);}
void beroot(int v){access(v),splay(v),turn(v);}
void split(int x,int y){beroot(x),access(y),splay(y);}
void link(int x,int y){beroot(x),dad[x]=y;}
void in()
{
	int a,b;scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",&val[i]);
	for(int i=1;i<n;++i)scanf("%d%d",&a,&b),link(a,b);
}
void ac()
{
	int a,b;scanf("%d",&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%s%d%d",ch,&a,&b);
		if(ch[0]=='Q'){split(a,b);sum[b]?puts("Yes"):puts("No");}
		else splay(a),val[a]=b,up(a);
	}
}
int main(){in();ac();}