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
Soluiton
因为输入字符的锅搞了几乎一上午。
题目很简单。
Nim游戏，先手必胜，Ai异或值不为0，否则必败。
就是一个路径上的异或和。
数据范围大，不能树剖。
发现单点修改。所以可以维护到根节点的异或和。再算上LCA即可。
树状数组维护dfs序，开始单点修改dfn[i],dfn2[i]+1为a[i]子树外异或两次直接消掉。
前缀异或值就是到根节点异或值。
每次单点修改同理。
然后套个LCA就可以。
注意，字符输入不要什么ch=getchar()两次，换行符可能很多，还可能有空格。。。。。数据不靠谱。
直接ch[2] scanf(“%s”,ch) 然后ch[0]==Q多好。直接过滤空格换行符。
（爆栈？其实不存在的。）
Code
#include<bits/stdc++.h> using namespace std; const int N=500000+5; struct node{ int nxt,to; }e[2*N]; int hd[N],cnt; void add(int x,int y){ e[++cnt].nxt=hd[x]; e[cnt].to=y; hd[x]=cnt; } int n,q; int f[2*N]; void xo(int x,int c){ for(;x<=n;x+=x&(-x)) f[x]^=c; } int query(int x){ int ret=0; for(;x;x-=x&(-x)) ret^=f[x]; return ret; } int dfn[N],df,fdfn[2*N]; int dfn2[N]; int a[N]; int d[N]; bool fl; int fa[N][30]; int dep[N]; void dfs(int x,int d){ dfn[x]=++df; fdfn[df]=x; dep[x]=d; for(int i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa[x][0]) continue; fa[y][0]=x; dfs(y,d+1); } dfn2[x]=df; } int lca(int x,int y){ if(dep[x]<dep[y]) swap(x,y); for(int j=25;j>=0;j--){ if(dep[fa[x][j]]>=dep[y]) x=fa[x][j]; } if(x==y) return x; for(int j=25;j>=0;j--){ if(fa[x][j]!=fa[y][j]){ x=fa[x][j],y=fa[y][j]; } } return fa[x][0]; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int x,y; for(int i=1;i<=n-1;i++){ scanf("%d%d",&x,&y); add(x,y);add(y,x); d[x]++,d[y]++; } scanf("%d",&q); dfs(1,1); dep[0]=-1; for(int j=1;j<=25;j++){ for(int i=1;i<=n;i++){ fa[i][j]=fa[fa[i][j-1]][j-1]; } } for(int i=1;i<=n;i++){ xo(dfn[i],a[i]);xo(dfn2[i]+1,a[i]); } while(q--){ char ch[2]; scanf("%s",ch); //cout<<"ch"<<ch<<"|"<<endl; scanf("%d %d",&x,&y); if(ch[0]=='Q'){ int anc=lca(x,y); int lp=query(dfn[x])^query(dfn[y])^a[anc]; if(lp==0){ printf("No "); } else printf("Yes "); } else { xo(dfn[x],a[x]); xo(dfn2[x]+1,a[x]); a[x]=y; xo(dfn[x],y); xo(dfn2[x]+1,y); } } return 0; }