先考虑如何判定一个集合是否存在两个异或和相同的子集 \(s,t\)，不然解决这道题就是无稽之谈。
根据异或的优良性质，不妨在 \(s,t\) 中分别去掉 \(s\cap t\)，之后从 \(s\) 中任意移动 \(|s|-1\) 个元素到 \(t\) 中去，易发现此时两个集合的元素异或和还是相同。也就是说，我们现在只需要逐个判断当前元素能否被其他元素异或出来即可。
于是我们构造一个线性基，逐个插入元素，插入的时候判断一下：如果插入不成功，则说明当前元素可以被异或出来，输出 YES。
但在给出的集合数以及集合大小都为 \(10^5\) 的情况下该如何处理？我们再尝试寻找一些性质：根据线性基的大小不超过 \(\log V\)，不难得出我们插入成功也必定不超过 \(\log V\) 次。也就是说，如果集合大小 \(>\log V\)，直接输出 YES 即可。
再回到原问题。这是一个树上带修问题——使用树链剖分解决即可。树剖中可以不写线段树，只需要写一个区改单查的树状数组。代码细节不多，较为好写。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); i++)
#define FR(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 1e5 + 10, W = 29;
namespace T{
int n, tot, d[N], fa[N], sz[N], tp[N], son[N], id[N];
vector<int> e[N];
namespace BIT{
int c[N];
void Add(int x, int v){
for(; x <= n; x += x & -x) c[x] ^= v;
}
int Ask(int x, int r = 0){
for(; x; x -= x & -x) r ^= c[x]; return r;
}
}
void Dfs1(int u){
d[u] = d[fa[u]] + (sz[u] = 1);
for(const int &v: e[u]) if(v != fa[u]){
fa[v] = u, Dfs1(v), sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
}
void Dfs2(int u){
id[u] = ++tot, tp[u] = (son[fa[u]] == u? tp[fa[u]] : u);
if(son[u]) Dfs2(son[u]);
for(const int &v: e[u])
if(v != fa[u] && v != son[u])
Dfs2(v);
}
int Lca(int x, int y){
while(tp[x] != tp[y]){
if(d[tp[x]] < d[tp[y]]) swap(x, y);
x = fa[tp[x]];
}
return d[x] < d[y]? x : y;
}
void Upd(int x, int y, int z){
while(tp[x] != tp[y]){
if(d[tp[x]] < d[tp[y]]) swap(x, y);
BIT::Add(id[tp[x]], z);
BIT::Add(id[x] + 1, z), x = fa[tp[x]];
}
if(d[x] < d[y]) swap(x, y);
BIT::Add(id[y], z), BIT::Add(id[x] + 1, z);
}
int Qry(int x){return BIT::Ask(id[x]);}
}
using namespace T;
struct LinearBasis{
int a[W + 2];
void init(){fill(a, a + W + 1, 0);}
int insert(int x){
FR(i, W, 0) if((x >> i) & 1){
if(!a[i]){a[i] = x; return 1;}
else x ^= a[i];
}
return 0;
}
} b;
int q, a[N];
int main(){
scanf("%d%d", &n, &q);
char op[10]; int x, y, z, lca, u, flag;
FL(i, 1, n) scanf("%d", &a[i]);
FL(i, 2, n){
scanf("%d%d", &x, &y);
e[x].emplace_back(y), e[y].emplace_back(x);
}
Dfs1(1), Dfs2(1); FL(i, 1, n) Upd(i, i, a[i]);
while(q--){
scanf("%s%d%d", op, &x, &y);
if(op[0] == 'U') scanf("%d", &z), Upd(x, y, z);
else{
lca = Lca(x, y), b.init();
flag = (d[x] + d[y] - d[lca] - d[fa[lca]] <= 30);
for(u = x; flag && u != lca; u = fa[u])
if(!b.insert(Qry(u))) flag = 0;
for(u = y; flag && u != fa[lca]; u = fa[u])
if(!b.insert(Qry(u))) flag = 0;
printf(flag? "NO\n" : "YES\n");
}
}
return 0;
}