著名游戏设计师vfleaking，最近迷上了Nim。普通的Nim游戏为：两个人进行游戏，N堆石子，每回合可以取其中某一堆的任意多个，可以取完，但不可以不取。谁不能取谁输。这个游戏是有必胜策略的。于是vfleaking决定写一个玩Nim游戏的平台来坑玩家。
为了设计漂亮一点的初始局面，vfleaking用以下方式来找灵感：拿出很多石子，把它们聚成一堆一堆的，对每一堆编号1,2,3,4,...n,在堆与堆间连边，没有自环与重边，从任意堆到任意堆都只有唯一一条路径可到达。然后他不停地进行如下操作：
1.随机选两个堆v,u，询问若在v到u间的路径上的石子堆中玩Nim游戏，是否有必胜策略，如果有，vfleaking将会考虑将这些石子堆作为初始局面之一，用来坑玩家。
2.把堆v中的石子数变为k。
由于vfleaking太懒了，他懒得自己动手了。请写个程序帮帮他吧。
题意：给定一棵树，每个节点上有个数值，现在Q个操作：
一种操作是给定u，v，然后需要回答u到v的最短路径上的这些数的Nim博弈结果。
一种操作是给定x，val，然后需要把x节点上的数值改为val。
思路：1，树剖，就不多说了。
2，dfs序可以得到u到根root的节点信息，所以sum(u,v)=sum(u,LCA)^sum(v,son[LCA])=sum(1,u)^sum(1,fa[v])。
具体的得到根到节点信息，可以参考这道题：https://blog.csdn.net/clove_unique/article/details/70213935
虽然第二种简单很多，这里树剖练习，先不管它：
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=500010; int a[maxn],sum[maxn<<2],top[maxn],sz[maxn],son[maxn]; int Laxt[maxn],Next[maxn<<1],To[maxn<<1],cnt,N,Q; int fa[maxn],dep[maxn],times,tid[maxn],Rank[maxn]; void add(int u,int v) { Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; } void dfs1(int u,int pre) { sz[u]=1; fa[u]=pre; dep[u]=dep[pre]+1; for(int i=Laxt[u];i;i=Next[i]){ int v=To[i]; if(v==pre) continue; dfs1(v,u); sz[u]+=sz[v]; if(sz[v]>sz[son[u]]) son[u]=v; } } void dfs2(int u,int Top) { tid[u]=++times; Rank[times]=u; top[u]=Top; if(son[u]) dfs2(son[u],Top); for(int i=Laxt[u];i;i=Next[i]){ int v=To[i]; if(v==fa[u]||v==son[u]) continue; dfs2(v,v); } } void update(int Now) { sum[Now]=sum[Now<<1]^sum[Now<<1|1]; } void build(int Now,int L,int R) { if(L==R){ sum[Now]=a[Rank[L]]; return ; } int Mid=(L+R)>>1; build(Now<<1,L,Mid); build(Now<<1|1,Mid+1,R); update(Now); } int getsum(int Now,int L,int R,int l,int r) { if(l<=L&&r>=R) return sum[Now]; int Mid=(L+R)>>1,res=0; if(l<=Mid) res^=getsum(Now<<1,L,Mid,l,r); if(r>Mid) res^=getsum(Now<<1|1,Mid+1,R,l,r); return res; } int query(int u,int v) { int res=0; while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]]) swap(u,v); res^=getsum(1,1,N,tid[top[u]],tid[u]); u=fa[top[u]]; } if(dep[u]>dep[v]) swap(u,v); res^=getsum(1,1,N,tid[u],tid[v]); return res; } void change(int Now,int L,int R,int pos,int val) { if(L==R){ sum[Now]=val; return ; } int Mid=(L+R)>>1; if(pos<=Mid) change(Now<<1,L,Mid,pos,val); else change(Now<<1|1,Mid+1,R,pos,val); update(Now); } int main() { int u,v,i; char opt[3]; scanf("%d",&N); for(i=1;i<=N;i++) scanf("%d",&a[i]); for(i=1;i<N;i++){ scanf("%d%d",&u,&v); add(u,v); add(v,u); } dfs1(1,0); dfs2(1,1); build(1,1,N); scanf("%d",&Q); while(Q--){ scanf("%s%d%d",opt,&u,&v); if(opt[0]=='Q'){ if(query(u,v)) printf("Yes "); else puts("No"); } else change(1,1,N,tid[u],v); } return 0; }