题目：单点修改、树链查询。
可以直接用树链剖分做。。
修改是O(QlogN)，查询是O(QlogNlogN)，Q=N=500000；
听说会超时。。
这题也可以用DFS序来做。
先不看修改，单单查询：可以求出每个点到根的xor值，那么对任意两点的查询就等于xor(u)^xor(v)^val(lca(u,v))；
如果有修改：修改仅仅是单个点，而维护的只是点到根的路径，因此修改仅仅会影响到以这个点为根的子树的所有结点到根的信息。
所以用DFS序把子树们化为连续区间用线段树维护，修改本质上是个线段树的区间修改，查询是个单点查询。
每次修改和查询都是O(logN)。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 550000
struct Edge{
int v,nxt;
}edge[MAXN<<];
int NE,head[MAXN];
void addEdge(int u,int v){
edge[NE].v=v; edge[NE].nxt=head[u]; head[u]=NE++;
}
int n,stone[MAXN];
int odr,stack[MAXN],l[MAXN],r[MAXN],dep[MAXN],fa[][MAXN],val[MAXN];
void dfs(){
int top=;
stack[++top]=;
val[]=stone[];
while(top){
int u=stack[top];
if(l[u]){
r[u]=odr; --top;
continue;
}
l[u]=++odr;
for(int i=head[u]; i!=-; i=edge[i].nxt){
int v=edge[i].v;
if(fa[][u]==v) continue;
fa[][v]=u; dep[v]=dep[u]+; val[v]=val[u]^stone[v]; stack[++top]=v;
}
}
} int tree[MAXN<<],N,x,y,z;
void update(int i,int j,int k){
if(x<=i && j<=y){
tree[k]^=z;
return;
}
if(tree[k]){
tree[k<<]^=tree[k]; tree[k<<|]^=tree[k];
tree[k]=;
}
int mid=i+j>>;
if(x<=mid) update(i,mid,k<<);
if(y>mid) update(mid+,j,k<<|);
}
int query(int i,int j,int k){
if(i==j) return tree[k];
if(tree[k]){
tree[k<<]^=tree[k]; tree[k<<|]^=tree[k];
tree[k]=;
}
int mid=i+j>>;
if(x<=mid) return query(i,mid,k<<);
return query(mid+,j,k<<|);
} int lca(int u,int v){
if(dep[u]>dep[v]) swap(u,v);
for(int k=; k<; ++k){
if((dep[v]-dep[u])>>k&){
v=fa[k][v];
}
}
if(v==u) return u;
for(int k=; k>=; --k){
if(fa[k][u]!=fa[k][v]){
u=fa[k][u];
v=fa[k][v];
}
}
return fa[][u];
}
void init(){
dfs();
for(int i=; i<; ++i){
for(int j=; j<=n; ++j){
int t=fa[i-][j];
if(t) fa[i][j]=fa[i-][t];
}
}
for(N=; N<odr; N<<=);
for(int i=; i<=n; ++i){
x=l[i]; y=l[i]; z=val[i];
update(,N,);
}
}
int main(){
int q,a,b;
char op[];
memset(head,-,sizeof(head));
scanf("%d",&n);
for(int i=; i<=n; ++i){
scanf("%d",stone+i);
}
for(int i=; i<n; ++i){
scanf("%d%d",&a,&b);
addEdge(a,b);
addEdge(b,a);
}
init();
scanf("%d",&q);
while(q--){
scanf("%s%d%d",op,&a,&b);
if(op[]=='Q'){
int res;
x=l[a]; res=query(,N,);
x=l[b]; res^=query(,N,);
res^=stone[lca(a,b)];
if(res) puts("Yes");
else puts("No");
}else{
x=l[a]; y=r[a]; z=b^stone[a];
update(,N,);
stone[a]=b;
}
}
return ;
}