这题真没什么意思.
不过就是将普通的求Min,Max,求和等东西换成Xor,偏偏Xor还有很多性质.
算是刷道水题吧.
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<string>
#include<iomanip>
#include<algorithm>
#include<map>
using namespace std;
#define LL long long
#define FILE "dealing"
#define up(i,j,n) for(int i=j;i<=n;++i)
#define db double
#define uint unsigned int
#define eps 1e-12
#define pii pair<int,int>
int read(){
int x=0,f=1,ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f*x;
}
const int maxn=505000,maxm=5050*5050,limit=1e6,mod=(int)(7+1e9+0.1);
const db inf=(1e18);
template<class T>bool cmax(T& a,T b){return a<b?a=b,true:false;}
template<class T>bool cmin(T& a,T b){return a>b?a=b,true:false;}
template<class T>T min(T& a,T& b){return a<b?a:b;}
template<class T>T max(T& a,T& b){return a>b?a:b;}
int n,m;
struct node{
int y,next;
}e[maxn<<1];
int len=0,linkk[maxn],siz[maxn],top[maxn],son[maxn],dfs_clock,dep[maxn],fa[maxn],v[maxn],id[maxn],pre[maxn];
void insert(int x,int y){
e[++len].y=y;
e[len].next=linkk[x];
linkk[x]=len;
}
void dfs1(int x){
siz[x]=1;
for(int i=linkk[x];i;i=e[i].next){
if(e[i].y==fa[x])continue;
fa[e[i].y]=x;
dep[e[i].y]=dep[x]+1;
dfs1(e[i].y);
siz[x]+=siz[e[i].y];
if(siz[e[i].y]>siz[son[x]])son[x]=e[i].y;
}
}
void dfs2(int x){
pre[x]=++dfs_clock;
if(son[x]){
top[son[x]]=top[x];
dfs2(son[x]);
}
for(int i=linkk[x];i;i=e[i].next){
if(e[i].y==fa[x]||e[i].y==son[x])continue;
top[e[i].y]=e[i].y;
dfs2(e[i].y);
}
}
int c[maxn];
int lowbit(int x){return x&-x;}
void add(int x,int d){
while(x<=n)c[x]^=d,x+=lowbit(x);
}
int getxor(int x){
int ans=0;
while(x)ans^=c[x],x-=lowbit(x);
return ans;
}
void query(int x,int y){
int d=0;
while(true){
if(dep[x]>dep[y])swap(x,y);
int f1=top[x],f2=top[y];
if(f1==f2){
d^=getxor(pre[x]-1)^getxor(pre[y]);
break;
}
if(dep[f1]>dep[f2])swap(f1,f2),swap(x,y);
d^=getxor(pre[f2]-1)^getxor(pre[y]);
y=fa[f2];
}
if(d==0)printf("No\n");
else printf("Yes\n");
}
void change(int x,int y){
add(pre[x],v[x]);
add(pre[x],y);
v[x]=y;
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
n=read();
up(i,1,n)v[i]=read();
up(i,2,n){
int x=read(),y=read();
insert(x,y);
insert(y,x);
}
dfs1(1);
top[1]=1;
dfs2(1);
up(i,1,n)add(pre[i],v[i]);
m=read();
up(i,1,m){
char ch;
scanf(" %c",&ch);
int x=read(),y=read();
if(ch=='Q')query(x,y);
else change(x,y);
}
return 0;
}