题目
传送门：QWQ
分析
先敲了个树链剖分，发现无法AC（其实是自己弱，懒得debug、手写栈）
然后去学了学正解
核心挺好理解的，$ query(a) $是$ a $到根的异或和。
答案就是$ lca(x,y) \hat{} query(x) \hat{} query(b) $
接着维护异或和，很显然线段树挺容易搞的。
但我们今天学学树状数组来维护异或和
若将区间$ [l,r] $内的元素全部异或x，相当于在第l位标记x，再在第r+1位标记x，
这样，对于第r位以后的元素，这两个命令互相抵消，查询某个元素的值，只需用树状数组把它之前的命令全部累加起来即可。
强无敌了~~~
代码
lca+dfs序+树状数组：
#include <bits/stdc++.h>
using namespace std;
const int maxn=;
int fa[maxn][],depth[maxn],w[maxn];
int in[maxn],out[maxn],cnt,vis[maxn],n,bit[maxn];
vector<int> G[maxn];
int dfs(int u){
for(int i=;i<;i++){
if(depth[u] < ( << i)) break;
fa[u][i]=fa[fa[u][i-]][i-];
}
in[u]=++cnt;
for(int i=;i<G[u].size();i++){
int v=G[u][i]; if(vis[v]) continue; vis[v]=;
fa[v][]=u; depth[v]=depth[u]+; dfs(v);
} out[u]=cnt;
}
int lca(int x,int y){
if(depth[x]<depth[y]) swap(x,y);
int d=(depth[x]-depth[y]);
for(int i=;i<;i++){
if((<<i) & d) x=fa[x][i];
}
for(int i=;i>=;i--){
if(fa[x][i]!=fa[y][i]){
x=fa[x][i]; y=fa[y][i];
}
}
if(x==y) return x;
else return fa[x][];
}
void add(int x,int v){for(;x<=n;x+=x&-x) bit[x]^=v;}
int query(int x){int ans=;for(;x>;x-=x&-x) ans^=bit[x];return ans;}
int main()
{
int u,v,q;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&w[i]);
for(int i=;i<n;i++){
scanf("%d%d",&u,&v);
G[u].push_back(v);G[v].push_back(u);
}
vis[]=;dfs();
for(int i=;i<=n;i++){
add(in[i],w[i]); add(out[i]+,w[i]);
}
scanf("%d",&q);
int a,b; char s[];
while(q--){
scanf("%s%d%d",s,&a,&b);
if(s[]=='Q'){
int ans=w[lca(a,b)]^query(in[a])^query(in[b]);
if(ans!=) puts("Yes");
else puts("No");
// printf("--------------- %d %d %d\n",lca(a,b),query(in[a]),query(in[b]));
}
else{
add(in[a],w[a]);add(out[a]+,w[a]);
w[a]=b;
add(in[a],w[a]);add(out[a]+,w[a]);
}
}
return ;
}
/*
8
1 3 5 2 5 3 1 1
1 5
3 5
2 5
1 4
6 3
7 4
8 3
13
Q 1 2
Q 3 5
Q 1 8
Q 3 5
Q 6 2
C 2 5
C 4 6
C 8 5
Q 1 2
Q 3 5
Q 1 8
Q 3 5
Q 6 2
*/
树链剖分（无法AC）：
#include <bits/stdc++.h>
using namespace std;
const int maxn=;
int top[maxn],fa[maxn],son[maxn],dep[maxn],siz[maxn];
int wt[*maxn],w[*maxn],id[*maxn],v[*maxn],cnt,n;
vector<int> G[maxn];
void build(int o,int l,int r){
if(l==r){ v[o]=wt[l]; return; }
int mid=l+r>>;
build(o<<,l,mid); build(o<<|,mid+,r);
v[o]=v[o<<]^v[o<<|];
}
void update(int o,int l,int r,int val,int L){
// printf("--->>> %d %d %d %d %d\n",o,l,r,val,L);
if(l==r){
v[o]=val; return;
}
int mid=l+r>>;
if(L<=mid) update(o<<,l,mid,val,L);
else update(o<<|,mid+,r,val,L);
v[o]=v[o<<]^v[o<<|];
}
int query(int o,int l,int r,int L,int R){
if(l>R||r<L) return ;
if(l>=L&&r<=R){return v[o];}
int mid=l+r>>;
int ans=query(o<<,l,mid,L,R)^query(o<<|,mid+,r,L,R);
return ans;
}
///////////////////////////////////////////
int dfs1(int x,int f,int depth){
dep[x]=depth; fa[x]=f; siz[x]=;
int maxnum=;
for(int i=;i<G[x].size();i++){
int v=G[x][i];
if(v==f) continue;
dfs1(v,x,depth+);
siz[x]+=siz[v];
if(maxnum<siz[v]){
maxnum=siz[v]; son[x]=v;
}
}
}
void dfs2(int x,int topf){
top[x]=topf; id[x]=++cnt; wt[id[x]]=w[x];
if(!son[x]) return;
dfs2(son[x],topf);
for(int i=;i<G[x].size();i++){
int v=G[x][i];
if(v!=son[x]&&v!=fa[x]){
dfs2(v,v);
}
}
}
void debug(){
puts("\ndepth: ");
for(int i=;i<=n;i++) printf("%d ",dep[i]);
puts("\nson: ");
for(int i=;i<=n;i++) printf("%d ",son[i]);
puts("\ntop: ");
for(int i=;i<=n;i++) printf("%d ",top[i]);
}
int Qu(int x,int y){
int ans=;
for(;top[x]!=top[y];){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans^=query(,,n,id[top[x]],id[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans^=query(,,n,id[x],id[y]);
return ans;
}
int main()
{
// freopen("1.txt","r",stdin); // int __size__=30<<20;
// char *__p__=(char*)malloc(__size__)+__size__;
// __asm__("movl %0, %%esp\n"::"r"(__p__));
int u,v,q;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&w[i]);
for(int i=;i<n;i++){
scanf("%d%d",&u,&v);
G[u].push_back(v);G[v].push_back(u);
}
dfs1(,,); dfs2(,);
build(,,n);
scanf("%d",&q);
// printf("====== %d\n",query(1,1,n,1,1));
int a,b; char s[];
while(q--){
// printf("========= %d\n",q);
scanf("%s%d%d",s,&a,&b);
if(s[]=='Q'){
int ans=Qu(a,b);
if(ans!=) puts("Yes");
else puts("No");
}
else{
update(,,n,b,id[a]);
}
}
// debug();
return ;
}
/*
8
1 3 5 2 5 3 1 1
1 5
3 5
2 5
1 4
6 3
7 4
8 3
13
Q 1 2
Q 3 5
Q 1 8
Q 3 5
Q 6 2
C 2 5
C 4 6
C 8 5
Q 1 2
Q 3 5
Q 1 8
Q 3 5
Q 6 2
*/