Description
给你一颗n个节点，带有点权的树。给出m次操作：1.Q x,y表示询问在x-y的路径上所有点权作为石子堆数量进行Nim游戏是否有先手必赢的策略。2.C x,y表示x点的点权改为y 其中n<=500000,m<=500000并且善意的提醒你dfs会爆栈。
Nim游戏规则：有若干堆石子，两个人轮流取石子，每次可以取其中某一堆的任意多个，可以取完，但不可以不取。谁最先不能取谁输
一道让我学会了一些前置技能的题目。
先考虑Nim游戏必胜策略：
假设有两堆同样的石子堆，先手一定必输。因为后手可以采取每次在另一个堆里和先手取相同数量的石子的策略。
考虑扩大范围：如果所有石子堆的数量亦或值为0。那么考虑，假设先手取了x个石子，相当于在二进制的一些位上去掉一些1。先手取石子后的序列就变成了一个亦或值不为0的序列。
考虑策略，后手可以找到二进制位上有奇数个1的最大的那一位所在的堆，设为k，将该位置删除1，再将后面所有二进制位上含有奇数个1的构造成偶数。方法为：如果k堆该二进制位为1，那么直接删除，如果不是，由于高位已经删除了一个，所以可以在后面的位置上均一个1。使得所有堆数量亦或值仍然为0。
然后，在先手渐渐僵硬的过程中，总有那么一天只剩下了两个堆，然后你还将其变成相同数量的，他拿几个，你拿几个。嘿嘿嘿。先手必输。
那么假设所有数亦或值不为0.先手可以学习后手，用同样的方法将其构造成亦或值为0的。然后呢???先手必输。不过这次先走的变成了后者。嘿嘿嘿，先手必赢。
博弈结束，开始数据结构：
那么我们只需要维护路径上所有点权的亦或值就好了（树剖啊2333，但是其实可以少一个log）。
亦或性质：a^b^b=a。直接在dfs入栈出栈序上维护一个点权亦或值，那么点的入栈时间戳的前缀亦或值就为该点到根节点路径上所有点权亦或值。那么两点路径亦或值就直接将这个东西^，再^上lca的权值，就是答案啦。修改的时候发现树状数组直接搞就可以了。
树状数组还可以搞前缀亦或值？？？嘿嘿嘿。
然后，没有然后了。
对对对！！！dfs爆栈啊。
我们直接写个stack，将下一步想dfs的点直接往栈里压，每次从栈顶拿点，进行搜索，并标记（不弹出）。当我们发现栈顶元素被标记的时候，那么好了，它的后来人已经关荣退役了，我们再将他弹栈。
说的好一点：bfs求dfs序
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 501000
int n,m,w[N],z[N],fa[N][20],deep[N];
int sum[N<<1],f[N<<1],in[N],out[N],tot;
int head[N],to[N<<1],nxt[N<<1],cnt;
char st[20];
bool v[N];
inline void add(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
inline int read()
{
char ch=getchar(); int re=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re;
}
void dfs()
{
int x,top=1; z[1]=1; deep[1]=1;
while(top)
{
x=z[top];
if(!v[x])
{
v[x]=1; sum[tot+1]=sum[tot]^w[x]; in[x]=++tot;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=fa[x][0])
{
z[++top]=to[i];
fa[to[i]][0]=x;
deep[to[i]]=deep[x]+1;
}
}
else
{
sum[tot+1]=sum[tot]^w[x]; out[x]=++tot;
top--;
}
}
}
int lca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);
for(int i=19;i>=0;i--)
if(deep[fa[x][i]]>=deep[y]) x=fa[x][i];
if(x==y) return x;
for(int i=19;i>=0;i--)
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int query(int x)
{
int re=0;
while(x>0){re^=f[x]; x-=-x&x;}
return re;
}
void fix(int x,int y)
{
while(x<=tot){f[x]^=y; x+=-x&x;}
}
void Query()
{
int x,y; x=read(); y=read();
if(query(in[x])^query(in[y])^sum[in[x]]^sum[in[y]]^w[lca(x,y)]) puts("Yes");
else puts("No");
}
void Fix()
{
int x,y; x=read(); y=read();
fix(in[x],w[x]^y); fix(out[x],w[x]^y);
w[x]=y;
}
int main()
{
scanf("%d",&n);
int x,y,i,j;
for(i=1;i<=n;i++) w[i]=read();
for(i=1;i<n;i++)
{
x=read();y=read();
add(x,y); add(y,x);
}
dfs();
for(i=1;i<=19;i++)
for(j=1;j<=n;j++)
fa[j][i]=fa[fa[j][i-1]][i-1];
scanf("%d",&m);
while(m--)
{
scanf("%s",st);
if(st[0]=='Q') Query();
else Fix();
}
return 0;
}