正确复杂度TLE求优化

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=100009; 
ll n,q,v[N],son[N],top[N],tI[N],id[N],timer=0,d[N],p[N],sz[N],C[N];
vector<ll> to[N];
struct edge{ll l,r,toXor;}tr[4*N];
void buildST(ll x,ll l,ll r){
	tr[x]=(edge){l,r,0};
	if(l==r){tr[x].toXor=v[tI[l]];return;}////
	ll mid=l+(r-l)/2;
	buildST(x*2,l,mid);
	buildST(x*2+1,mid+1,r);
}
void add(ll x,ll l,ll r,ll z){
//	if(x==1) cout<<l<<"~"<<r<<":"<<z<<"\n"; 
	if(tr[x].l>r||tr[x].r<l) return;
	if(l<=tr[x].l&&tr[x].r<=r){tr[x].toXor^=z;return;}
	add(x*2,l,r,z);
	add(x*2+1,l,r,z);
}
ll query(ll x,ll i){
	if(tr[x].l==tr[x].r) return tr[x].toXor;
	return tr[x].toXor^(i<=tr[x*2].r?query(x*2,i):query(x*2+1,i));
}
void dfs2(ll x,ll fa){
	if(son[fa]==x) top[x]=top[fa];
	else top[x]=x;
	tI[id[x]=++timer]=x;//id[i]:节点->线段树
						//tI[i]:线段树->节点
	if(son[x]) dfs2(son[x],x);
	for(ll i=0,v;i<to[x].size();++i)
		if((v=to[x][i])^fa&&v^son[x])
			dfs2(v,x);
}
void dfs1(ll x,ll fa){
	p[x]=fa,d[x]=d[fa]+1,sz[x]=1;
	for(ll i=0,v;i<to[x].size();++i)
		if((v=to[x][i])^fa){
			dfs1(v,x);
			sz[x]+=sz[v];
			if(sz[v]>sz[son[x]]) son[x]=v;
		}
}
ll lca(ll x,ll y){
	while(top[x]^top[y]){
		ll &a=(d[top[x]]>d[top[y]]?x:y);
		a=p[top[a]];
	}
	return (d[x]<d[y]?x:y);
}
bool jiAdd(ll a){
//	cout<<"jiAdd:"<<a<<"\n";
	if(a==0) return 1;//// 
	for(ll i=30;i>=0;--i)
		if(a&(1<<i)){
			if(C[i]) a^=C[i];
			else{C[i]=a;return 0;}
		}
	return 1;
}
bool Q(ll x,ll y){
	ll l=lca(x,y);
	if(d[x]+d[y]-2*d[l]+1>=32) return 1;
//	cout<<"Q:"<<x<<" "<<y<<" "<<l<<"\n";
	memset(C,0,sizeof(C));
	while(1){
		if(jiAdd(query(1,id[x]))) return 1;
		if(x==l) break;
		x=p[x];
	}
	while(1){
		if(y==l) break;
		if(jiAdd(query(1,id[y]))) return 1;
		y=p[y];
	}
	return 0;
}
void adlian(ll x,ll fa,ll v){
	while(d[top[x]]>=d[fa]){
		add(1,id[top[x]],id[x],v),
		x=p[top[x]];
	}
	if(d[x]>=d[fa]) add(1,id[fa],id[x],v);
}
void upd(ll x,ll y,ll v){
	ll l=lca(x,y);
	adlian(x,l,v);
	adlian(y,l,v);
	add(1,id[l],id[l],v);////
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n>>q;
	for(ll i=1;i<=n;++i) cin>>v[i];
	for(ll i=1;i<n;++i){
		ll x,y;
		cin>>x>>y;
		to[x].push_back(y);
		to[y].push_back(x);
	}
	dfs1(1,0);
	dfs2(1,0);
	buildST(1,1,n);
	for(ll i=1;i<=q;++i){
		string op;
		cin>>op;
		if(op=="Update"){
			ll x,y,v;
			cin>>x>>y>>v;
			upd(x,y,v);
		}else{
			ll x,y;
			cin>>x>>y;
			if(Q(x,y)) cout<<"YES\n";
			else cout<<"NO\n";
		}
	}
	return 0;
}