rt

  都对着第一篇题解调了（代码都差不多了），总是莫名全RE（还有一个点WA）

  求助QwQ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lc(x) x<<1
#define rc(x) (x<<1)|1
#define MID (l+r)>>1
using namespace std;
const int MAXN=1e5+10,MAXM=2e5+10;
struct Edge{
	int u,v;
}edge[MAXM];
struct Node{
	int sum,tag,lcolor,rcolor;
}tree[MAXN<<2];
int first[MAXN],next[MAXM],tot;
int n,m,w[MAXN];
int depth[MAXN],fa[MAXN],size[MAXN],son[MAXN],top[MAXN],dfn[MAXN],ord[MAXN],dfntot;
char opt,a,b,c;
inline void addedge(int u,int v){
	edge[++tot].u=u;edge[tot].v=v;
	next[tot]=first[u];first[u]=tot;
}
void dfs1(int u,int father){
	depth[u] = depth[father]+1;
	fa[u] = father;
	size[u] = 1;
	for(int j=first[u];j;j=next[j]){
		int v = edge[j].v;
		if(v==father)continue;
		dfs1(v,u);
		size[u] += size[v];
		if((son[u]==0) || (size[v] > size[son[u]])){
			son[u] = v;
		}
	}
}
void dfs2(int u,int topnode){
	dfn[u] = ++dfntot;ord[dfntot] = u;
	top[u] = topnode;
	if(!son[u])return;
	dfs2(son[u],topnode);
	for(int j=first[u];j;j=next[j]){
		int v = edge[j].v;
		if( (v==fa[u]) || (v == son[u]))continue;
		dfs2(v,v);
	}
}
void push_up(int x){
	tree[x].sum = tree[lc(x)].sum + tree[rc(x)].sum;
	if(tree[lc(x)].rcolor == tree[rc(x)].lcolor){tree[x].sum--;}
	tree[x].lcolor = tree[lc(x)].lcolor;
	tree[x].rcolor = tree[rc(x)].rcolor;
}
void push_down(int x,int l,int r){
	if(!tree[x].tag)return;
	tree[lc(x)].sum = tree[rc(x)].sum = 1;
	tree[lc(x)].lcolor = tree[lc(x)].rcolor = tree[rc(x)].lcolor = tree[rc(x)].rcolor = tree[x].tag;
	tree[lc(x)].tag=tree[rc(x)].tag=tree[x].tag;
	tree[x].tag=0;
}
void build(int x,int l,int r){
	if(l==r){
		tree[x].sum = 1;
		tree[x].lcolor = tree[x].rcolor = w[ord[l]];
		return;
	}
	int mid = MID;
	build(lc(x),l,mid);
	build(rc(x),mid+1,r);
	push_up(x);
}
Node query(int x,int l,int r,int ql,int qr){
	if(ql <= l && qr >= r){
		return tree[x];
	}
	int mid = MID;
	Node sum = (Node){0,0,0,0},tmp;
	push_down(x,l,r);
	if(ql <= mid){
		tmp = query(lc(x),l,mid,ql,qr);
		sum.sum += tmp.sum;
		sum.lcolor = tmp.lcolor;
		sum.rcolor = tmp.rcolor;
	}
	if(qr > mid){
		tmp = query(rc(x),mid+1,r,ql,qr);
		sum.sum += tmp.sum;
		if(!sum.lcolor)sum.lcolor = tmp.lcolor;
		sum.rcolor = tmp.rcolor;
	}
	if((ql <= mid) && (qr > mid)){
		if(tree[lc(x)].rcolor == tree[rc(x)].lcolor)sum.sum--;
	}
	push_up(x);
	return sum;
}
void update(int x,int l,int r,int ql,int qr,int v){
	if(ql <= l && qr >= r){
		tree[x].sum = 1;
		tree[x].lcolor = tree[x].rcolor = tree[x].tag = v;
		return;
	}
	push_down(x,l,r);
	int mid = MID;
	if(ql <= mid){
		update(lc(x),l,mid,ql,qr,v);
	}
	if(qr > mid){
		update(rc(x),mid+1,r,ql,qr,v);
	}
	push_up(x);
}
int query_tree(int x,int y){
	int sum = 0,tmp1 = -1,tmp2 = -1;
	while(top[x] != top[y]){
		if(depth[top[x]] > depth[top[y]]){
			Node tmp = query(1,1,n,dfn[top[x]],dfn[x]);
			sum += tmp.sum;
			if(tmp.rcolor == tmp1){
				sum--;
			} 
			tmp1 = tmp.lcolor;
			x = fa[top[x]];
		}else{
			Node tmp = query(1,1,n,dfn[top[y]],dfn[y]);
			sum += tmp.sum;
			if(tmp.rcolor == tmp2){
				sum--;
			}
			tmp2 = tmp.rcolor;
			y = fa[top[y]];
		}
	}
	if(depth[x] < depth[y]){
		Node tmp =  query(1,1,n,dfn[x],dfn[y]);
		sum += tmp.sum;
		if(tmp.lcolor == tmp1)sum--;
		if(tmp.rcolor == tmp2)sum--;
	}else{ 
		Node tmp = query(1,1,n,dfn[y],dfn[x]);
		sum += tmp.sum;
		if(tmp.rcolor == tmp1)sum--;
		if(tmp.lcolor == tmp2)sum--;
	}
	return sum;
}
void update_tree(int x,int y,int c){
	while(top[x] != top[y]){
		if(depth[top[x]] > depth[top[y]]){
			update(1,1,n,dfn[top[x]],dfn[x],c);
			x = fa[top[x]];
		}else{
			update(1,1,n,dfn[top[y]],dfn[y],c);
			y = fa[top[y]];
		}
	}
	if(depth[x] < depth[y]){
		update(1,1,n,dfn[x],dfn[y],c);
	}else{
		update(1,1,n,dfn[y],dfn[x],c);
	}	 
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&w[i]);
	}
	for(int i=1,u,v;i<n;i++){
		scanf("%d%d",&u,&v);
		addedge(u,v);addedge(v,u);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		cin>>opt;
		if(opt=='C'){
			scanf("%d%d%d",&a,&b,&c);
			update_tree(a,b,c);
		}else{
			scanf("%d%d",&a,&b);
			printf("%d\n",query_tree(a,b));
		}
	}
	return 0;
}