记录编号	371495	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]黑树白	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	3.978 s
提交时间	2017-02-16 10:57:39	内存使用	234.06 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define ll long long 
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
	return x*f;
}
const int maxn=80100;
struct edge{int to,next;}e[maxn*2];
int tot,head[maxn];
void add(int u,int v){
	e[++tot]=(edge){v,head[u]};head[u]=tot;
}

int n,m,c[maxn],ans,cnt,le,ri;
int sta[maxn],end[maxn],dfn;
int size[maxn],deep[maxn],fa[maxn];
int son[maxn],top[maxn];

void dfs(int u){
	sta[u]=++dfn;size[u]=1;
	for(int i=head[u];i;i=e[i].next){
		int to=e[i].to;
		if(size[to])continue;
		fa[to]=u,deep[to]=deep[u]+1;
		dfs(to);size[u]+=size[to];
		if(size[to]>size[son[u]])son[u]=to;
	}
	end[u]=dfn;
}
void dfs(int u,int tp){
	top[u]=tp;
	if(son[u])dfs(son[u],tp);
	for(int i=head[u];i;i=e[i].next)
		if(!top[e[i].to])dfs(e[i].to,e[i].to);
}
int lca(int a,int b){
	while(top[a]!=top[b]){
		if(deep[top[a]]<deep[top[b]])swap(a,b);
		a=fa[top[a]];
	}return deep[a]<deep[b]?a:b;
}

int lc[maxn*250],rc[maxn*250],sum[maxn*250];
int root[maxn],tree[maxn];
void insert(int l,int r,int pr,int &rt,int p,int x){
	sum[rt=++cnt]=sum[pr]+x;
	if(l==r) return;int mid=(l+r)/2;
	lc[rt]=lc[pr],rc[rt]=rc[pr];
	if(p<=mid) insert(l,mid,lc[pr],lc[rt],p,x);
	else insert(mid+1,r,rc[pr],rc[rt],p,x);
}
void Build(int u,int Fa){
	insert(1,n,root[Fa],root[u],c[u],1);
	for(int i=head[u];i;i=e[i].next)
		if(e[i].to!=Fa) Build(e[i].to,u);
}
void add(int x,int y,int ad){
	if(!x)return;
	for(int i=x;i<=n;i+=i&-i)
		insert(1,n,tree[i],tree[i],y,ad);
}
int query(int l,int r,int rt){
	if(!rt) return 0;
	if(le<=l&&ri>=r) return sum[rt];
	int mid=(l+r)/2,res=0;
	if(le<=mid) res+=query(l,mid,lc[rt]);
	if(ri>mid) res+=query(mid+1,r,rc[rt]);
	return res;
}
int Add(int x){
	if(!x) return 0;
	ll res=query(1,n,root[x]);
	for(int i=sta[x];i;i-=i&-i)res+=query(1,n,tree[i]);
	return res;
}
int Sub(int x){
	if(!x) return 0;
	ll res=query(1,n,root[x]);
	for(int i=sta[x];i;i-=i&-i)res+=query(1,n,tree[i]);
	return res;
}
int main(){
	freopen("D_Tree.in","r",stdin);freopen("D_Tree.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++) c[i]=read();
	for(int i=1;i<n;i++){
		int a=read(),b=read();
		add(a,b);add(b,a);
	}
	dfs(1);dfs(1,1);Build(1,0);
	char op[5];
	while(m--){
		scanf("%s",op);
		int u=(read()+ans)%n+1,v=(read()+ans)%n+1;
		if(op[0]=='M'){
			add(sta[u],c[u],-1);add(end[u]+1,c[u],1);
			c[u]=v;
			add(sta[u],c[u],1);add(end[u]+1,c[u],-1);
		}else{
			int lc=lca(u,v);le=read(),ri=read();
			ans=Add(u)+Add(v)-Sub(lc)-Sub(fa[lc]);
			printf("%d\n",ans);
		}
	}
	fclose(stdin);fclose(stdout);
	return 0;
}