珍爱生命 远离树剖

#include<bits/stdc++.h>
#include<iostream>
#include<map>
#include<vector>
#include<math.h>
#include<set>
using namespace std;
#define int long long
#define lc (u<<1)
#define rc (u<<1|1)
const int N=1000010;
int n,m,a,b,root,p;
int w[N],color[N];
vector<int>e[N];
int fa[N],dep[N],sz[N],son[N];
int top[N],id[N],nw[N],cnt;
struct Tree
{
	int l,r,l_color,r_color,lazy;
	int add,sum,maxx;
}tree[N*5];
inline void dfs1(int u,int father)
{
	fa[u]=father;
	dep[u]=dep[father]+1;
	sz[u]=1;
	for(auto v:e[u])
	{
		if(v==father)
		{
			continue;
		}
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[son[u]]<sz[v])
		{
			son[u]=v;
		}
	}
}
inline void dfs2(int u,int t)
{
	top[u]=t;
	id[u]=++cnt;
	nw[cnt]=u;
	if(!son[u])
	{
		return;
	}
	dfs2(son[u],t);
	for(auto v:e[u])
	{
		if(v==fa[u]||v==son[u])
		{
			continue;
		}
		dfs2(v,v);
	}
}
inline void pushup(int u)
{
	tree[u].l_color=tree[lc].l_color;
	tree[u].l_color=tree[lc].r_color;
	if(tree[lc].r_color==tree[rc].l_color)tree[u].sum=tree[lc].sum+tree[rc].sum-1;
}
inline void pushdown(int u)
{
	if(tree[u].lazy)
	{
		tree[u].lazy=tree[lc].lazy=tree[rc].lazy;
		tree[lc].sum=tree[rc].sum;
		tree[u].l_color=tree[u].r_color=tree[lc].l_color=tree[lc].r_color=tree[rc].l_color=tree[rc].r_color=tree[u].lazy;
		tree[u].lazy=0;
	}
}
inline void build(int u,int l,int r)
{
	tree[u].l=l;
	tree[u].r=r;
	if(l==r)
	{
		tree[u].l_color=tree[u].r_color=color[nw[l]];
		tree[u].sum=1;
		return;
	}
	int mid=(l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(u);
}
inline void change(int u,int l,int r,int p,int q,int k)
{
	tree[u].l=p;
	tree[u].r=q;
	if(tree[u].l<=l&&r<=tree[u].r)
	{
		tree[u].lazy=tree[u].l_color=tree[u].r_color=k;
		tree[u].sum=1;
		return ;
	}
	pushdown(u);
	int mid=(l+r)/2;
	if(p<=mid)
	{
		change(lc,l,mid,p,q,k);
	}
	if(q>mid)
	{
		change(rc,mid+1,r,p,q,k);
	}
	pushup(u);
}
inline Tree query(int u,int l,int r,int nl,int nr)
{
	tree[u].l=nl; tree[u].r=nr;
	if(l<=tree[u].l&&r>=tree[u].r)
	{
		return tree[u];
	}
	pushdown(u);
	int mid=(tree[u].l+tree[u].r)>>1;
	if(l<=mid)
	{
		return query(lc,l,r,nl,mid);
	}
	else if(r>mid)
	{ 
		return query(rc,l,r,mid+1,nr);
	}
	else
	{
		Tree a,b,c;
		a=query(lc,l,r,nl,mid);
		b=query(rc,l,r,mid+1,nr);
		c.l_color=a.l_color;
		c.r_color=b.r_color;
		if(a.r_color==b.l_color)
		{
			c.sum=a.sum+b.sum-1;
		}
		return c;
	}
}
inline void query_path(int u,int v,int val)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]])
		{
			swap(u,v);
		}
		change(1,id[top[u]],id[u],1,n,val);
		u=fa[top[u]]; 
	}
	if(dep[u]<dep[v])
	{ 
		swap(u,v);
	}
	change(1,id[u],id[v],1,n,val);
}
inline int query_tree(int u,int v)
{
	Tree a,b;
	a.sum=b.sum=a.l_color=a.r_color=b.l_color=b.r_color=0;
	while(top[u]!=top[v])
	{
		if(dep[top[u]]>=dep[top[v]])
		{
			Tree c=query(1,id[top[u]],id[u],1,n);
			if(a.sum==0)a=c;
			else 
			{
				if(c.r_color==a.l_color)
				{
					a.sum=a.sum+c.sum-1;
				}
				else
				{
					a.sum=a.sum+c.sum;
				}
				a.l_color=c.l_color;
			}
			u=son[top[u]];
		}
		else
		{
			Tree c=query(1,id[top[v]],id[v],1,n);
			if(b.sum==0)
			{
				b=c;
			}
			else 
			{
				if(c.r_color==b.l_color)
				{
					b.sum=b.sum+c.sum-1;
				}
				else
				{
					b.sum=b.sum+c.sum;
				}
				b.l_color=c.l_color;
			}
			v=son[top[v]];
		}
	}
	if(dep[u]>=dep[v])
	{
		Tree c=query(1,id[v],id[u],1,n);
		if(a.sum==0)
		{
			a=c;
		}
		else 
		{
			if(c.r_color==a.l_color)
			{
				a.sum=a.sum+c.sum-1;
			}
			else
			{
				a.sum=a.sum+c.sum;
			}
			a.l_color=c.l_color;
		}
	}
	else
	{
		Tree c=query(1,id[u],id[v],1,n);
		if(b.sum==0)
		{
			b=c;
		}
		else 
		{
			if(c.r_color==b.l_color)
			{
				b.sum=b.sum+c.sum-1;
			}
			else 
			{
				b.sum=b.sum+c.sum;
			}
			b.l_color=c.l_color;
		}
	}
	if(a.sum==0)
	{
		return b.sum;
	}
	else if(b.sum==0)
	{
		return a.sum;
	}
	if(a.l_color==b.l_color)
	{
		return a.sum+b.sum-1;
	}
}
//inline int querymax(int u,int l,int r,int nl,int nr)
//{
//	tree[u].l=nl; tree[u].r=nr;
//	if(l<=tree[u].l&&r>=tree[u].r)
//	{
//		return tree[u].maxx;
//	}
//	else
//	{
//		int mid=(tree[u].l+tree[u].r)>>1;
//		int res=-1000000;
//		if(l<=mid)
//		{
//			res=max(res,querymax(lc,l,r,nl,mid));
//		}
//		if(r>mid)
//		{ 
//			res=max(res,querymax(rc,l,r,mid+1,nr));
//		}
//		return res;
//	}
//}
//inline int qmax(int u,int v)
//{
//	int res=-4*N;
//	while(top[u]!=top[v])
//	{
//		if(dep[top[u]]<dep[top[v]])
//		{
//			swap(u,v);
//		}
//		res=max(res,querymax(1,id[top[u]],id[u],1,n));
//		u=fa[top[u]]; 
//	}
//	if(dep[u]>dep[v])
//	{
//		swap(u,v);
//	}
//	res=max(res,querymax(1,id[u],id[v],1,n));
//	return res;
//}
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&color[i]);
		color[i]++;
	}
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%lld%lld",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dep[1]=1;
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		char op;
		int x,y,z;
		cin>>op;
		scanf("%lld%lld",&x,&y);
		if(op=='C')
		{
			scanf("%lld",&z);
			z++;
			query_path(x,y,z);
		}
		else
		{
			printf("%lld\n",query_tree(x,y));
		}
	}
	return 0;
}