学步园

#include<iostream>
#include<cstdio>
#define N 100001
using namespace std;
struct edge{
	int to,next;
}e[2*N];
struct seg{
	int l,r,lc,rc,s,tag;
}tr[4*N];
int n,m,cnt,head[N],size[N],fa[N][18],pos[N],belong[N],deep[N],sz,v[N];
bool vis[N];
void ins(int u,int v){
	e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
	e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;
}
void dfs1(int x){
	vis[x]=size[x]=1;
	for(int i=1;i<=17;i++)
		if(deep[x]<(1<<i))break;
		else fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=head[x];i;i=e[i].next){
		if(vis[e[i].to])continue;
		fa[e[i].to][0]=x;
		deep[e[i].to]=deep[x]+1;
		dfs1(e[i].to);
		size[x]+=size[e[i].to];
	}
}
void dfs2(int x,int chain){
	pos[x]=++sz;belong[x]=chain;
	int k=0;
	for(int i=head[x];i;i=e[i].next)
		if(size[e[i].to]>size[k]&&deep[e[i].to]>deep[x])
			k=e[i].to;
	if(!k)return;
	dfs2(k,chain);
	for(int i=head[x];i;i=e[i].next)
		if(deep[e[i].to]>deep[x]&&e[i].to!=k)
			dfs2(e[i].to,e[i].to);
}
int lca(int x,int y){
	if(deep[x]<deep[y])swap(x,y);
	int d=deep[x]-deep[y];
	for(int i=0;i<=17;i++){
		if(d&(1<<i))x=fa[x][i];
	}
	for(int i=17;i>=0;i--){
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	}
	if(x==y)return x;
	return fa[x][0];
}
void build(int k,int l,int r){
	tr[k].l=l;tr[k].r=r;
	tr[k].s=1;tr[k].tag=-1;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
void pushup(int k){
	tr[k].lc=tr[k<<1].lc;tr[k].rc=tr[k<<1|1].rc;
	tr[k].s=tr[k<<1].s+tr[k<<1|1].s-(tr[k<<1].rc==tr[k<<1|1].lc);
}
void pushdown(int k){
	int c=tr[k].tag;tr[k].tag=-1;
	if(c==-1||tr[k].l==tr[k].r)return;
	tr[k<<1].s=tr[k<<1|1].s=1;
	tr[k<<1].tag=tr[k<<1|1].tag=c;
	tr[k<<1].lc=tr[k<<1].rc=tr[k<<1|1].lc=tr[k<<1|1].rc=c;
}
void change(int k,int x,int y,int c){
	pushdown(k);
	int l=tr[k].l,r=tr[k].r;
	if(l==x&&r==y){
		tr[k].lc=tr[k].rc=tr[k].tag=c;
		tr[k].s=1;
		return;
	}
	int mid=(l+r)>>1;
	if(y<=mid)change(k<<1,x,y,c);
	else if(x>mid)change(k<<1|1,x,y,c);
	else{
		change(k<<1,x,mid,c);
		change(k<<1|1,mid+1,y,c);
	}
	pushup(k);
}
int ask(int k,int x,int y){
	pushdown(k);
	int l=tr[k].l,r=tr[k].r;
	if(l==x&&r==y)return tr[k].s;
	int mid=(l+r)>>1;
	if(y<=mid)return ask(k<<1,x,y);
	else if(x>mid)return ask(k<<1|1,x,y);
	else return ask(k<<1,x,mid)+ask(k<<1|1,mid+1,y)-(tr[k<<1].rc==tr[k<<1|1].lc);
}
int getc(int k,int x){
	pushdown(k);
	int l=tr[k].l,r=tr[k].r;
	if(l==r)return tr[k].lc;
	int mid=(l+r)>>1;
	if(x<=mid)return getc(k<<1,x);
	else if(x>mid)return getc(k<<1|1,x);
}
int solvesum(int x,int y){
	int sum=0;
	while(belong[x]!=belong[y]){
		sum+=ask(1,pos[belong[x]],pos[x]);
		if(getc(1,pos[belong[x]])==getc(1,pos[fa[belong[x]][0]]))sum--;
		x=fa[belong[x]][0];
	}
	sum+=ask(1,pos[y],pos[x]);
	return sum;
}
void solvechange(int x,int y,int c){
	while(belong[x]!=belong[y]){
		change(1,pos[belong[x]],pos[x],c);
		x=fa[belong[x]][0];
	}
	change(1,pos[y],pos[x],c);
}
void solve(){
	dfs1(1);
	dfs2(1,1);
	build(1,1,n);
	for(int i=1;i<=n;i++)
		change(1,pos[i],pos[i],v[i]);
	for(int i=1;i<=m;i++){
		char ch[10];
		scanf("%s",ch);
		if(ch[0]=='Q'){
			int a,b;
			scanf("%d%d",&a,&b);
			int t=lca(a,b);
			printf("%d\n",solvesum(a,t)+solvesum(b,t)-1);
		}
		else{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			int t=lca(a,b);
			solvechange(a,t,c);solvechange(b,t,c);
		}
	}
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&v[i]);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		ins(x,y);
	}
}
int main(){
	init();
	solve();
	return 0;
}