萌新刚学oi,简单树剖求调，已过样例，WA加MLE，悬赏一关注

#include<bits/stdc++.h>
#define N 100010
using namespace std;
int to[N],nex[N],beg[N],e,rev[N];
int w[N];
int lc,rc;
struct note {
	int l,r,cl,cr;
	int sum,lazy;
} tree[N*4];
inline void add(int x,int y) {
	to[++e]=y;
	nex[e]=beg[x];
	beg[x]=e;
}
inline void push_up(int x) {
	tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
	tree[x].cl=tree[x<<1].cl;
	tree[x].cr=tree[x<<1|1].cr;
	if(tree[x<<1].cr==tree[x<<1|1].cl)tree[x].sum--;
}
inline void build(int x,int l,int r) {
	int mid=l+r>>1;
	tree[x].l=l,tree[x].r=r,tree[x].lazy=-1;
	if(l==r) {
		tree[x].cl=tree[x].cr=w[rev[l]];
		tree[x].sum=1;
		return ;
	}
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	push_up(x);
}
int fa[N],deep[N],Snum[N],son[N];
inline void dfs1(int x,int f) {
	deep[x]=deep[f]+1,fa[x]=f;
	Snum[x]=1;
	int maxn=-1;
	for(int i=beg[x]; i; i=nex[i]) {
		int y=to[i];
		if(y==f)continue;
		dfs1(y,x);
		Snum[x]+=Snum[y];
		if(Snum[y]>maxn)maxn=Snum[y],son[x]=y;
	}
}
int top[N],name[N],cnt;
inline void dfs2(int x,int Top) {
	top[x]=Top;
	name[x]=++cnt;
	rev[cnt]=x;
	if(!son[x])return ;
	dfs2(son[x],Top);
	for(int i=beg[x]; i; i=nex[i]) {
		int y=to[i];
		if(y==fa[x]||y==son[x])continue;
		dfs2(y,y);
	}
}
inline void pushdown(int x) {
	if(tree[x].lazy==-1)return ;
	tree[x<<1].lazy=tree[x<<1|1].lazy=tree[x].lazy;
	tree[x<<1].sum=tree[x<<1|1].sum=1;
	tree[x<<1].cl=tree[x<<1].cr=tree[x].cl;
	tree[x<<1|1].cl=tree[x<<1|1].cr=tree[x].cr;
	tree[x].lazy=-1;
}
inline int query(int x,int L,int R) {
	if(L<=tree[x].l&&tree[x].r<=R) {
		if(tree[x].l==L)lc=tree[x].cl;
		if(tree[x].r==R)rc=tree[x].cr;
		return tree[x].sum;
	}
	pushdown(x);
	int mid=tree[x].l+tree[x].r>>1;
	if(L<=mid)return query(x<<1,L,R);
	if(R>mid)return query(x<<1|1,L,R);
	int ans=query(x<<1,L,R)+query(x<<1|1,L,R);
	if(tree[x<<1].cr==tree[x<<1|1].cl)ans--;
	return ans;
}
inline void up_date(int x,int L,int R,int k) {
	if(L<=tree[x].l&&tree[x].r<=R) {
		tree[x].cl=tree[x].cr=k;
		tree[x].sum=tree[x].lazy=1;
		return ;
	}
	pushdown(x);
	int mid=tree[x].l+tree[x].r>>1;
	if(L<=mid)up_date(x<<1,L,R,k);
	if(R>mid)up_date(x<<1|1,L,R,k);
	push_up(x);
}
inline int Query(int x,int y) {
	int ans=0;
	int ans1=0,ans2=0;
	while(top[x]!=top[y]) {
		if(deep[top[x]]<deep[top[y]])swap(x,y),swap(ans1,ans2);
		ans+=query(1,name[top[x]],name[x]);
		if(rc==ans1)ans--;
		ans1=lc;
		x=fa[top[x]];
	}
	if(deep[x]>deep[y])swap(x,y),swap(ans1,ans2);
	ans+=query(1,name[x],name[y]);
	if(lc==ans1)ans--;
	if(rc==ans2)ans--;
	return ans;
}
inline void update(int x,int y,int k) {
	while(top[x]!=top[y]) {
		if(deep[top[x]]<deep[top[y]])swap(x,y);
		up_date(1,name[top[x]],name[x],k);
		x=fa[top[x]];
	}
	if(deep[x]>deep[y])swap(x,y);
	up_date(1,name[x],name[y],k);
	return ;
}
int main() {
	int n,m;
	cin>>n>>m;
	int x,y;
	for(int i=1; i<=n; i++) {
		cin>>w[i];
	}
	for(int i=1; i<n; i++) {
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	while(m--) {
		char op;
		int x,y,z;
		cin>>op;
		if(op=='Q') {
			cin>>x>>y;
			cout<<Query(x,y)<<"\n";
		} else {
			cin>>x>>y>>z;
			update(x,y,z);
		}
	}
	return 0;
}