题意：给定一棵带点权的树,每次询问用一条路径上的点玩Nim游戏先手是否必胜，支持单点修改。
Nim游戏:所有堆的数目异或起来不为0时先手必胜,否则必败.
所以就是单点修改+路径异或和查询. 树剖一发,因为异或满足区间减法所以可以树剖套树状数组。（还有人说可以套zkw线段树？）
Dzy大爷说了一种dfs序+树状数组的方法:
http://dzy493941464.is-programmer.com/posts/40428.html
既然它只修改点的话，影响到的只是它这棵子树。那么很容易就想到了dfs序。这个子树就是连续一段。
先维护每个点dfs开始时和结束时的时间戳。修改的时候先在它自己的开始、结束位置上xor它自己变成零，然后再修改。
(x,y)路径上的xor值=query(x的开始) xor query(y的开始) xor lca(x,y)的点权。很好想通。LCA就倍增算一下好了。
没了。
“很好想通”,表示蒟蒻脑子有坑想了好久才明白QAQ。
首先，在求树上点对距离的时候我们是用节点到根的距离减去lca到根的距离，比如u到v的距离等于dis[u]+dis[v]-2*dis[lca(u,v)]
这里把点i到根节点路径上点的异或和记作sum[i],i的点权记作w[i],那么u,v路径上的异或和就是sum[u]^sum[v]^w[lca(u,v)]
这么做的原因在于lca(u,v)到根节点路径上的点权值在sum[u]和sum[v]中都出现,异或一下就没了.但是lca(u,v)的点权应当在答案中出现，却也被消掉了，所以还要单独异或上。
Lca可以倍增一发,那么问题还剩下动态维护每个点到根节点路径上的异或和.转换思路，分别考虑每个点能够影响其他哪些点的sum值，对于每个点i将它能影响的所有点的sum值进异或上w[i]。这个操作可以高效地完成，因为每个点只会影响它所在子树内的点的sum值。而一棵子树内的点在dfs序中是连续的一段,所以我们只需要一个数据结构支持区间修改单点查询，那么就可以树状数组了。查询sum[u]的时候直接查询u的DFS序在树状数组中对应的位置即可。
注意会卡爆栈，所以需要用BFS求DFS序。
#include<cstdio>
const int maxn=;
struct edge{
int to,next;
}lst[maxn<<];int len=;
int first[maxn];
void addedge(int a,int b){
lst[len].to=b;
lst[len].next=first[a];
first[a]=len++;
}
int w[maxn],pos[maxn],prt[maxn],depth[maxn],hvy[maxn],top[maxn],sz[maxn];
int q[maxn],head,tail;
int c[maxn];
inline int lowbit(int x){
return x&(-x);
}
void add(int x,int w){
for(;x<maxn;x+=lowbit(x)){
c[x]^=w;
}
}
int sum(int x){
int ans=;
for(;x;x-=lowbit(x))ans^=c[x];
return ans;
}
void bfs1(){
head=tail=;
q[tail++]=;depth[]=;
while(head!=tail){
int x=q[head++];
sz[x]=;
for(int pt=first[x];pt;pt=lst[pt].next){
if(lst[pt].to==prt[x])continue;
prt[lst[pt].to]=x;
depth[lst[pt].to]=depth[x]+;
q[tail++]=lst[pt].to;
}
}
for(int i=tail-;i>=;--i){
int x=q[i];
sz[prt[x]]+=sz[x];
if(sz[x]>sz[hvy[prt[x]]])hvy[prt[x]]=x;
}
}
void bfs2(){
top[]=;pos[]=;
for(int i=;i<tail;++i){
int x=q[i];
add(pos[x],w[x]);
if(hvy[x]){
top[hvy[x]]=top[x];
pos[hvy[x]]=pos[x]+;
int cntsz=sz[hvy[x]];
for(int pt=first[x];pt;pt=lst[pt].next){
if(lst[pt].to==prt[x]||lst[pt].to==hvy[x])continue;
top[lst[pt].to]=lst[pt].to;
pos[lst[pt].to]=pos[x]+cntsz+;
cntsz+=sz[lst[pt].to];
}
}
}
}
inline void swap(int &a,int &b){
int tmp=a;a=b;b=tmp;
}
int query(int u,int v){
int ans=;
int t1=top[u],t2=top[v];
while(t1!=t2){
if(depth[t1]<depth[t2])swap(t1,t2),swap(u,v);
ans^=sum(pos[t1]-);
ans^=sum(pos[u]);
u=prt[t1];t1=top[u];
}
if(depth[u]>depth[v])swap(u,v);
ans^=sum(pos[u]-);ans^=sum(pos[v]);
return ans;
}
int main(){
int n;scanf("%d",&n);
for(int i=;i<=n;++i)scanf("%d",w+i);
int a,b;
for(int i=;i<n;++i){
scanf("%d%d",&a,&b);
addedge(a,b);addedge(b,a);
}
bfs1();
bfs2();
int m;scanf("%d",&m);
char buf[];
while(m--){
scanf("%s%d%d",buf,&a,&b);
if(buf[]=='Q'){
if(query(a,b)==)printf("No\n");
else printf("Yes\n");
}else{
add(pos[a],w[a]);
w[a]=b;
add(pos[a],w[a]);
}
}
return ;
}
#include<cstdio>
const int maxn=;
struct edge{
int to,next;
}lst[maxn<<];int len=;
int first[maxn];
void addedge(int a,int b){
lst[len].to=b;
lst[len].next=first[a];
first[a]=len++;
}
int w[maxn];
int c[maxn];
inline int lowbit(int x){
return x&(-x);
}
void add(int x,int w){
for(;x<maxn;x+=lowbit(x))c[x]^=w;
}
int query(int x){
int ans=;
for(;x;x-=lowbit(x))ans^=c[x];
return ans;
}
int q[maxn];
int dfn[maxn],sz[maxn],depth[maxn];
int p[maxn][];
void bfs(){//求dfs序和倍增的预处理都在这里了
int head=,tail=,x,cntsz;
q[tail++]=;depth[]=;
while(head!=tail){
x=q[head++];
for(int pt=first[x];pt;pt=lst[pt].next){
if(lst[pt].to==p[x][])continue;
p[lst[pt].to][]=x;
depth[lst[pt].to]=depth[x]+;
q[tail++]=lst[pt].to;
}
for(int j=;p[x][j];++j)p[x][j+]=p[p[x][j]][j];
}
for(int i=tail-;i>=;--i){
x=q[i];
sz[x]++;
sz[p[x][]]+=sz[x];
}
dfn[]=;
for(int i=;i<tail;++i){
x=q[i];cntsz=;
for(int pt=first[x];pt;pt=lst[pt].next){
if(lst[pt].to==p[x][])continue;
dfn[lst[pt].to]=dfn[x]+cntsz+;
cntsz+=sz[lst[pt].to];
}
}
}
inline void swap(int &a,int &b){
int tmp=a;a=b;b=tmp;
}
int lca(int u,int v){
if(depth[u]<depth[v]){
swap(u,v);
}
for(int j=;j>=;--j){
if(depth[p[u][j]]>=depth[v])u=p[u][j];
}
if(u==v)return u;
for(int j=;j>=;--j){
if(p[u][j]!=p[v][j]){
u=p[u][j];v=p[v][j];
}
}
return p[u][];
} int main(){
int n;scanf("%d",&n);
for(int i=;i<=n;++i)scanf("%d",w+i);
int a,b;
for(int i=;i<n;++i){
scanf("%d%d",&a,&b);
addedge(a,b);addedge(b,a);
}
bfs();
for(int i=;i<=n;++i){
add(dfn[i],w[i]);add(dfn[i]+sz[i],w[i]);
}
int q;scanf("%d",&q);
char buf[];
int tmp;
while(q--){
scanf("%s%d%d",buf,&a,&b);
if(buf[]=='Q'){
tmp=query(dfn[a])^query(dfn[b])^w[lca(a,b)];
if(tmp){
printf("Yes\n");
}else{
printf("No\n");
}
}else{
add(dfn[a],w[a]);add(dfn[a]+sz[a],w[a]);
w[a]=b;
add(dfn[a],w[a]);add(dfn[a]+sz[a],w[a]);
}
}
return ;
}