题目传送门(BZOJ)
>原文链接<

题解 :

假的爆栈

首先 NIM 游戏有必胜策略的条件是异或和不是零,所以我们维护路径异或和就可以。

树剖序上加一棵线段树维护区间异或和,单点修改,区间查询。

你看,因为不爆栈,这题就直接水过去了。(并没有自觉的非递归)

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define ls p << 1#define rs p << 1|1#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)using namespace std;char buf[100000], *p1, *p2;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc(); return x;}inline char gc() { char c = nc(); while(isspace(c)) c = nc(); return c;}const int N = 500001;struct Edge { int to; Edge *next;}*h[N],e[N<<1];int son[N], dep[N], top[N], fa[N], siz[N];int idx[N], t[N<<2], a[N];int n = rd();inline void Add_Edge(int u, int v) { static int _ = 0; Edge *tmp = &e[++_]; tmp->to = v; tmp->next = h[u]; h[u] = tmp;}void change(int l, int r, int p, int x, int c) { if(l == r) return t[p] = c, void(); int mid = (l+r) >> 1; if(x <= mid) change(l, mid, ls, x, c); else change(mid+1, r, rs, x, c); t[p] = t[ls]^t[rs];}void dfs(int p) { dep[p] = dep[fa[p]] + 1; siz[p] = 1; rev(i, p) if(i->to != fa[p]) { fa[i->to] = p; dfs(i->to); siz[p] += siz[i->to]; if(siz[i->to] > siz[son[p]]) son[p] = i->to; }}void dfs(int p, int t) { top[p] = t; idx[p] = ++*idx; if(son[p]) dfs(son[p], t); rev(i, p) if(i->to != fa[p] && i->to != son[p]) dfs(i->to, i->to);}int query(int l, int r, int p, int x, int y) { if(x <= l && y >= r) return t[p]; int mid = (l+r) >> 1; int ret = 0; if(x <= mid) ret ^= query(l, mid, ls, x, y); if(y > mid) ret ^= query(mid+1, r, rs, x, y); return ret;}int inq(int x, int y) { int ret = 0; while(top[x] != top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x, y); ret ^= query(1, n, 1, idx[top[x]], idx[x]); x = fa[top[x]]; } if(dep[x] < dep[y]) swap(x, y); ret ^= query(1, n, 1, idx[y], idx[x]); return ret;}int main() { for(int i = 1; i <= n; i ++ ) a[i] = rd(); for(int i = 2; i <= n; i ++ ) { int u = rd(), v = rd(); Add_Edge(u, v); Add_Edge(v, u); } dfs(1); dfs(1, 1); for(int i = 1; i <= n; i ++ ) change(1, n, 1, idx[i], a[i]); int Q = rd(); while(Q -- ) { char opt = gc(); if(opt == 'C') { int x = rd(), v = rd(); change(1, n, 1, idx[x], v); } else { int x = rd(), y = rd(); puts(inq(x, y)?"Yes":"No"); } }}