这题……咋说捏，其实是一道披着博弈论外衣的树上操作问题……
随便用dfs序或者树链剖分转成序列，然后查询路径上的所有点的NIM和（异或和）就行了，毕竟除了是在树上以外，就是裸的NIM问题。
树链剖分：一开始把线段树写跪了，然后输出“Yes”和“No”的时候全部大写了，再然后发现线段树空间开小了……
代码如下：
//BZOJ 2819
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
const int N=;
#define debug
int n,a[N],t[N<<],fa[N],top[N],dep[N],son[N],size[N],tid[N],cnt=;
vector<int>G[N];
bool vis[N]; #define mid (l+r>>1)
#define L (o<<1)
#define R (o<<1|1)
void updata(int o,int l,int r,int pos,int v){
if (l==r) t[o]=v;
else{
if (pos<=mid) updata(L,l,mid,pos,v);
else updata(R,mid+,r,pos,v);
t[o]=t[L]^t[R];
}
} int ql,qr,ans=;
void query_it(int o,int l,int r){
if (ql<=l && qr>=r) ans^=t[o];
else{
if (ql<=mid) query_it(L,l,mid);
if (qr>mid) query_it(R,mid+,r);
}
}
//segment tree end void dfs(int x,int f,int deep){
int y,maxsize=;
vis[x]=; fa[x]=f; dep[x]=deep; size[x]=; son[x]=;
rep(i,G[x].size()){
y=G[x][i];
if (vis[y]) continue;
dfs(y,x,deep+);
size[x]+=size[y];
if (size[y]>maxsize) maxsize=size[y],son[x]=y;
}
} void connect(int x,int f){
tid[x]=++cnt;
top[x]=f; vis[x]=;
if (son[x]) connect(son[x],f);
rep(i,G[x].size()){
int y=G[x][i];
if (!vis[y]) connect(y,y);
}
} void query(int x,int y){
while(top[x]!=top[y]){
if (dep[top[x]]<dep[top[y]]) swap(x,y);
ql=tid[top[x]]; qr=tid[x];
query_it(,,n);
x=fa[top[x]];
}
if (dep[x]>dep[y]) swap(x,y);
ql=tid[x]; qr=tid[y];
query_it(,,n);
} int main(){
// freopen("file.in","r",stdin);
scanf("%d",&n);
F(i,,n) scanf("%d",&a[i]);
int x,y;
F(i,,n){
scanf("%d%d",&x,&y);
G[x].pb(y);
G[y].pb(x);
}
dfs(,,);
memset(vis,,sizeof vis);
connect(,);
F(i,,n) updata(,,n,tid[i],a[i]);
int q;
scanf("%d",&q);
char cmd[];
F(i,,q){
scanf("%s%d%d",cmd,&x,&y);
if (cmd[]=='Q'){
ans=;
query(x,y);
printf(ans ? "Yes\n" : "No\n");
}
else updata(,,n,tid[x],y);
}
return ;
}
dfs序版：
维护从根到x的异或和sum(x)，则query(x,y)=sum(x)^sum(y)^a[lca(x,y)]
自己画个图一眼就看出来了……公共部分两次异或互相抵消，但是LCA是在x-->y这条路径上的，所以要再加上
/**************************************************************
Problem: 2819
User: Tunix
Language: C++
Result: Accepted
Time:15004 ms
Memory:65740 kb
****************************************************************/ //BZOJ 2819
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
void read(int &v){
v=; int sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
v*=sign;
}
/******************tamplate*********************/
const int N=;
int head[N],to[N<<],next[N<<],cnt,fa[N];
void add(int x,int y){
to[++cnt]=y; next[cnt]=head[x]; head[x]=cnt;
to[++cnt]=x; next[cnt]=head[y]; head[y]=cnt;
}
/*******************edge***********************/
int n,m,dfs_clock,l[N],r[N],t[N<<],a[N],deep[N];
int st[N],top;
void dfs(){
st[++top]=; fa[]=;deep[]=;
while(top){
int x=st[top];
if (!l[x]){
l[x]=++dfs_clock;
for(int i=head[x];i;i=next[i])
if (to[i]!=fa[x]){
st[++top]=to[i];
fa[to[i]]=x;
deep[to[i]]=deep[x]+;
}
}
else{
r[x]=++dfs_clock;
top--;
}
}
}
int p[N][];
void ST(){
memset(p,-,sizeof p);
F(i,,n) p[i][]=fa[i];
for(int j=;(<<j)<=n;++j)
F(i,,n)
if (p[i][j-]!=-) p[i][j]=p[p[i][j-]][j-];
}
int lca(int x,int y){
if (deep[x]<deep[y]) swap(x,y);
int k=log(deep[x])/log();
D(i,k,)
if (deep[x]-(<<i)>=deep[y]) x=p[x][i];
if (x==y) return y;
D(i,k,)
if (p[x][i]!=- && p[x][i]!=p[y][i]){
x=p[x][i]; y=p[y][i];
}
return p[x][];
}
/*****************dfs&LCA***********************/
inline int lowbit(int x){return x&(-x);}
void update(int x,int val){
for(x;x<=n*;x+=lowbit(x)) t[x]^=val;
}
int sum(int x){
int temp=;
for(x;x;x-=lowbit(x)) temp^=t[x];
return temp;
}
/*********************fenwick*******************/
int main(){
read(n);
F(i,,n) read(a[i]);
int x,y;
F(i,,n){
read(x); read(y);
add(x,y);
}
dfs();
ST();
F(i,,n) update(l[i],a[i]),update(r[i],a[i]);
read(m);
char cmd[];
F(i,,m){
scanf("%s",cmd);
read(x); read(y);
if (cmd[]=='Q') printf( sum(l[y])^sum(l[x])^a[lca(x,y)] ? "Yes\n" : "No\n");
else{
update(l[x],a[x]); update(r[x],a[x]);
update(l[x],y); update(r[x],y);
a[x]=y;
}
}
return ;
}