提交上去大红大紫的/kk

调了3天，心态快崩了

（给关注）

#include <bits/stdc++.h>
#define int long long
using namespace std;

inline int read(){
	int x=0,f=0;char ch=getchar();
	while(!isdigit(ch))f^=!(ch^45),ch=getchar();
	while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
inline void write(int x){
	if(x<0)x=-x,putchar('-');
	if(x>=10)write(x/10);
	putchar(x%10+'0');
}
inline void writeln(int x){write(x);puts("");}

struct edge{
	int to,nxt;
}e[100005<<1];
int head[100005],idx;
void link(int x,int y){
	e[++idx]={y,head[x]};
	head[x]=idx;
}

int fa[100005],son[100005],dep[100005],siz[100005];
int top[100005],seg[100005],a[100005],w[100005];
int dfn;

void dfs1(int u,int f,int d){
	dep[u]=d;fa[u]=f;siz[u]=1;
	int mx=-1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v!=f){
			dfs1(v,u,d+1);
			siz[u]+=siz[v];
			if(siz[v]>mx){son[u]=v;mx=siz[v];}
		}
	}
}
void dfs2(int u,int tp){
	top[u]=tp;
	seg[u]=++dfn;
	w[dfn]=a[u];
	if(!son[u])return;
	dfs2(son[u],tp);
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(!seg[v])dfs2(v,v);
	}
}

struct segment{
	int l,r,sum;
	int lazy;
	int lc,rc;
}tr[100005<<2];
inline int ls(int p){return p<<1;}
inline int rs(int p){return p<<1|1;}
inline void push_up(int p){
	tr[p].sum=tr[ls(p)].sum+tr[rs(p)].sum;
	tr[p].lc=tr[ls(p)].lc,tr[p].rc=tr[rs(p)].rc;
	if(tr[ls(p)].rc==tr[rs(p)].lc)tr[p].sum--;
}
void build(int p,int l,int r){
	tr[p].l=l;tr[p].r=r;
	if(l==r){
		tr[p].sum=1;
		tr[p].lc=tr[p].rc=w[p];
		return;
	}
	int mid=l+r>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	push_up(p);
}
void push_down(int p){
	if(tr[p].lazy){
		tr[ls(p)].lazy=tr[p].lazy;
		tr[rs(p)].lazy=tr[p].lazy;
		tr[ls(p)].lc=tr[ls(p)].rc=tr[p].lazy;
		tr[rs(p)].lc=tr[rs(p)].rc=tr[p].lazy;
		tr[ls(p)].sum=1;
		tr[rs(p)].sum=1;
		tr[p].lazy=0;
	}
}
void tr_update(int p,int l,int r,int k){
	if(tr[p].l==l&&tr[p].r==r){
		tr[p].lc=tr[p].rc=k;
		tr[p].lazy=k;
		tr[p].sum=1;
		return;
	}
	push_down(p);
	int mid=tr[p].l+tr[p].r>>1;
	if(mid<l)tr_update(rs(p),l,r,k);
	else if(mid>=r)tr_update(ls(p),l,r,k);
	else{
		tr_update(ls(p),l,mid,k);
		tr_update(rs(p),mid+1,r,k);
	}
	push_up(p);
}
void seg_update(int x,int y,int k){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		tr_update(1,seg[top[x]],seg[x],k);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	tr_update(1,seg[x],seg[y],k);
}
int tr_query(int p,int l,int r){
	if(tr[p].l==l&&tr[p].r==r)return tr[p].sum;
	push_down(p);
	int mid=tr[p].l+tr[p].r>>1;
	if(mid<l)return tr_query(rs(p),l,r);
	else if(mid>=r)return tr_query(ls(p),l,r);
	else{
		int ans=tr_query(ls(p),l,mid)+tr_query(rs(p),mid+1,r);
		if(tr[ls(p)].rc==tr[rs(p)].lc)ans--;
		return ans;
	}
}
int modify(int p,int x){
	if(tr[p].l==tr[p].r)return tr[p].lc;
	push_down(p);
	int mid=tr[p].l+tr[p].r>>1;
	if(x<=mid)return modify(ls(p),x);
	else return modify(rs(p),x);
}
int seg_query(int x,int y){
	int ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans+=tr_query(1,seg[top[x]],seg[x]);
		int c1=modify(1,seg[top[x]]),c2=modify(1,seg[fa[top[x]]]);
		if(c1==c2)ans--;
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	ans+=tr_query(1,seg[x],seg[y]);
	return ans;
}

signed main(){
	int n=read(),m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		link(u,v);link(v,u);
	}
	dfs1(1,-1,1);
	dfs2(1,1);
	build(1,1,n);
	while(m--){
		char ch;cin>>ch;
		if(ch=='C'){
			int a=read(),b=read(),c=read();
			seg_update(a,b,c);
		}else{
			int a=read(),b=read();
			writeln(seg_query(a,b));
		}
	}
	#ifndef ONLINE_JUDGE
	system("pause");
	#endif
	return 0;
}