WA 50pts 求调

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,inf=1e9+1;
int n,m,a[N];
int son[N],siz[N],dep[N],top[N];
int id[N],idy,f[N];
struct edge{
	int v,next;
}e[N<<1];
int head[N],idx;
void con(int u,int v){
	idx++;
	e[idx].v=v;
	e[idx].next=head[u];
	head[u]=idx;
}
void dfs1(int u,int fa){
	siz[u]=1,son[u]=0;
	f[u]=fa;
	dep[u]=dep[fa]+1;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].v;
		if(v==fa) continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
}
void dfs2(int u,int topu){
	top[u]=topu;
	id[u]=++idy;
	if(!son[u]) return;
	dfs2(son[u],topu);
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].v;
		if(v==f[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}
struct tree{
	int l,r,cnt;
};
tree sb;
tree hb(tree L,tree R){
	if(!L.cnt)return R;
	if(!R.cnt)return L;
	sb=(tree){0,0,0};
	sb.l=L.l,sb.r=R.r;
	sb.cnt=L.cnt+R.cnt-(L.r==R.l&&L.r!=0);
	return sb;	
}
struct bt{
	tree t[N<<2];
	int tag[N<<2];
	#define mid (l+r>>1)
	#define ls p<<1
	#define rs p<<1|1
	void pu(int p){
		t[p]=hb(t[ls],t[rs]);
	}
	void build(int p,int l,int r){
		if(l>r) return;
		if(l==r){
			t[p].l=t[p].r=a[id[l]];
			t[p].cnt=1;
			return;
		}
		build(ls,l,mid),build(rs,mid+1,r);
		pu(p);
	}
	void pd(int p){
		if(!tag[p])return;
		tag[ls]=tag[rs]=tag[p];
		t[ls].l=t[rs].r=t[ls].r=t[rs].l=tag[p];
		t[ls].cnt=t[rs].cnt=1;
		tag[p]=0;
	}
	void upd(int p,int l,int r,int xl,int xr,int c){
		if(l>r) return;
		if(l>=xl&&r<=xr){
			t[p].l=t[p].r=tag[p]=c;
			t[p].cnt=1;
			return;
		}
		pd(p);
		if(xl<=mid) upd(ls,l,mid,xl,xr,c);
		if(xr>mid) upd(rs,mid+1,r,xl,xr,c);
		pu(p);
	}
	tree query(int p,int l,int r,int xl,int xr){
	//	if(p==1) cout<<xl<<" "<<xr<<" ";
		tree ans=(tree){0,0,0};
		if(l>r||!p) return ans;
		if(l>=xl&&r<=xr)return t[p];
		pd(p);
		if(xl<=mid)ans=query(ls,l,mid,xl,xr);
		if(xr>mid){
			ans=hb(ans,query(rs,mid+1,r,xl,xr));
		}
	//	if(p==1) cout<<ans.l<<" "<<ans.r<<" "<<ans.cnt<<"\n";
		return ans;
	}
}T;
void modi(int u,int v,int c){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		T.upd(1,1,n,id[top[u]],id[u],c);
		u=f[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	T.upd(1,1,n,id[u],id[v],c);
}
int que(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	tree L=(tree){0,0,0},R=(tree){0,0,0};
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]]){
			L=hb(T.query(1,1,n,id[top[u]],id[u]),L);
			u=f[top[u]];
		}
		else{
			R=hb(T.query(1,1,n,id[top[v]],id[v]),R);
			v=f[top[v]];
		}
	}
	tree lc=(tree){0,0,0};
	if(dep[u]>dep[v]){
		lc=T.query(1,1,n,id[v],id[u]);
		if(lc.l==R.l&&lc.l!=0)lc.cnt--;
		if(lc.r==L.r&&lc.r!=0)lc.cnt--;
	}
	else{
		lc=T.query(1,1,n,id[u],id[v]);
		if(lc.l==L.l&&lc.l!=0)lc.cnt--;
		if(lc.r==R.r&&lc.r!=0)lc.cnt--;
	}
	lc.cnt+=L.cnt+R.cnt;
	return lc.cnt;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		con(u,v);
		con(v,u);
	}
	dfs1(1,0);
	dfs2(1,1);
	T.build(1,1,n);
	for(int i=1;i<=m;i++){
		char x;
		int u,v,c;
		cin>>x>>u>>v;
		if(x=='Q'){
			cout<<que(u,v)<<"\n";
		}
		else {
			cin>>c;
			modi(u,v,c);
		}
	}
	return 0;
}