BZOJ2819: Nim 树链剖分

著名游戏设计师vfleaking，最近迷上了Nim。普通的Nim游戏为：两个人进行游戏，N堆石子，每回合可以取其中某一堆的任意多个，可以取完，但不可以不取。谁不能取谁输。这个游戏是有必胜策略的。于是vfleaking决定写一个玩Nim游戏的平台来坑玩家。
为了设计漂亮一点的初始局面，vfleaking用以下方式来找灵感：拿出很多石子，把它们聚成一堆一堆的，对每一堆编号1,2,3,4,...n,在堆与堆间连边，没有自环与重边，从任意堆到任意堆都只有唯一一条路径可到达。然后他不停地进行如下操作：

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

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

第一行一个数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

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

#include <bits/stdc++.h>#define ll long long
#define inf 0x3f3f3f3f
#define il inlinenamespace io { #define in(a) a=read()
#define out(a) write(a)
#define outn(a) out(a),putchar('\n') #define I_int int
inline I_int read() {
I_int x = , f = ; char c = getchar() ;
while( c < '' || c > '' ) { if( c == '-' ) f = - ; c = getchar() ; }
while( c >= '' && c <= '' ) { x = x * + c - '' ; c = getchar() ; }
return x * f ;
}
char F[ ] ;
inline void write( I_int x ) {
if( x == ) { putchar( '' ) ; return ; }
I_int tmp = x > ? x : -x ;
if( x < ) putchar( '-' ) ;
int cnt = ;
while( tmp > ) {
F[ cnt ++ ] = tmp % + '' ;
tmp /= ;
}
while( cnt > ) putchar( F[ -- cnt ] ) ;
}
#undef I_int}
using namespace io ;using namespace std ;#define N 500010int dep[N] , top[N] , id[N] , siz[N] , fa[N] , w[N] ;
int n = read() , a[N] , tot = ;
int cnt , head[N] ;
struct edge {
int to , nxt ;
} e[N<<] ;void ins(int u , int v) {
e[ ++ cnt ] = (edge) {v , head[u]} ;
head[u] = cnt ;
}void dfs1(int u) {
siz[u] = ;
for(int i = head[u] ; i ; i = e[i].nxt) {
if(e[i].to == fa[u]) continue ;
fa[e[i].to] = u ;
dep[e[i].to] = dep[u] + ;
dfs1(e[i].to) ;
siz[u] += siz[e[i].to] ;
}
}void dfs2(int u , int topf) {
top[u] = topf ;
id[u] = ++ tot ;
w[tot] = a[u] ;
int k = ;
for(int i = head[u] ; i ; i = e[i].nxt) {
if(e[i].to == fa[u]) continue ;
if(siz[e[i].to] > siz[k]) k = e[i].to ;
}
if(!k) return ;
dfs2(k , topf) ;
for(int i = head[u] ; i ; i = e[i].nxt) {
if(e[i].to == fa[u] || k == e[i].to) continue ;
dfs2(e[i].to , e[i].to) ;
}
}// seg-tree
struct tree {
int l , r , sum ;
} t[N << ];#define lc (rt << 1)
#define rc (rt << 1 | 1)void pushup(int rt) { t[rt].sum = t[lc].sum ^ t[rc].sum ; }void build(int l , int r , int rt) {
t[rt].l = l ; t[rt].r = r ; int mid = (l + r) >> ;
if(l == r) { t[rt].sum = w[l] ; return ; }
build(l , mid , lc) ; build(mid + , r , rc) ; pushup(rt) ;
}#define l t[rt].l
#define r t[rt].r
#define mid ((l + r) >> 1)void upd(int L , int c , int rt) {
if(l == r) {t[rt].sum = c ; return ;}
if(L <= mid) upd(L , c , lc) ;
else upd(L , c , rc) ;
pushup(rt) ;
}int query(int L , int R , int rt) {
if(L <= l && r <= R) return t[rt].sum ; int ans = ;
if(L <= mid) ans ^= query(L , R , lc) ; if(R > mid) ans ^= query(L , R , rc) ;
return ans ;
}#undef lc
#undef rc
#undef l
#undef r
#undef mid
// seg-tree endvoid query(int x , int y) {
int ans = ;
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x , y) ;
ans ^= query(id[top[x]] , id[x] , ) ;
x = fa[top[x]] ;
}
if(dep[x] > dep[y]) swap(x , y) ;
ans ^= query(id[x] , id[y] , ) ;
if(ans) puts("Yes") ;
else puts("No") ;
}int main() {
for(int i = ; i <= n ; i ++) a[i] = read() ;
for(int i = ; i < n ; i ++) {
int u = read() , v = read() ;
ins(u , v) , ins(v , u) ;
}
dfs1() ; dfs2(,) ; build(,n,) ;
int m = read() ;
while(m--) {
char ch[] ; scanf("%s" , ch);
int x = read() , y = read() ;
if(ch[] == 'Q') query(x , y) ;
else upd(id[x] , y , ) ;
}
}