【题意】
有一棵n个节点的树，每个节点有一种颜色，现在要进行m次操作，操作分两种
C a b c：将节点a到节点b的路径上所有节点染成c色
Q a b：询问节点a到节点b的路径上节点的颜色段的数量，例如说:112211就是3个颜色段
【输入】
第一行n、m
接下来一行n个数字表示n个节点的颜色
接下来n-1行每行表示一条边来描述树
之后的m行每行一次操作
【输出】
对于每次询问，输出一行一个数字表示颜色段的个数
据说是动态树的模板问题……
说到动态树，就学了link-cut tree，无奈没有摸到门路，至今没搞懂怎么搞
作为替代，学习了树链剖分
这类问题为什么不能用寻常的方式解决呢，因为无法把大块大块的点归为一块快速处理
树链剖分就是将其有序化的一种划分方式
简单来说，将树剖成一根一根链，然后用线段树修改查询
线段树是个有序结构，所以需要对节点重标号
对于一棵树的根节点，选择其中子树节点最多的节点加入链中按序标号，然后将这条链上的所有节点拿掉，会产生一片森林
对于森林里的每棵树都进行相同操作，直至森林为空
这样树就被拆成了一条一条的链，并且一条链上的节点标号都是有序的，可以用线段树修改查询
从一个节点返回到根节点，可以从该节点跳到链的顶端，再从链的顶端跳到其父节点，再跳到父节点所在链的顶端……
但是这样会很快吗？最坏情况从根到树的底部需要路过多少条链？
log2(n)条
为什么呢……因为每一条链都将树至少划分成两个规模更小的树
十分容易理解的算法，但是比较长
我这里写错了，写的是每次选择最长的一条链进行剖分，最差n^0.5
program paint;
var
ans,fa,top,x,y,tot,n,m,i,j,k,a,b,c:longint;
color,height,up,go,total,num,dd,root:array [0..100001] of longint;
father:array [0..20,0..100001] of longint;
next,point:array [0..200001] of longint;
sum,lb,rb,left,right:array [0..2000001] of longint;
stop:array [0..2000001] of boolean;
order:char;
procedure swap (var a,b:longint);inline;
var
i:longint;
begin
i:=a;
a:=b;
b:=i;
end;
procedure connect (u,v:longint);inline;
begin
inc(tot);
point[tot]:=v;
next[tot]:=root[u];
root[u]:=tot;
end;
procedure update (now:longint);inline;
begin
lb[left[now]]:=lb[now];
rb[left[now]]:=lb[now];
lb[right[now]]:=rb[now];
rb[right[now]]:=rb[now];
stop[now]:=false;
stop[left[now]]:=true;
stop[right[now]]:=true;
sum[left[now]]:=1;
sum[right[now]]:=1;
end;
procedure insert (c,s,e,l,r,now:longint);
var
mid:longint;
begin
if (l=s)and(r=e) then
begin
lb[now]:=c;
rb[now]:=c;
sum[now]:=1;
stop[now]:=true;
exit;
end;
mid:=(l+r) div 2;
if left[now]=0 then
begin
inc(tot);
left[now]:=tot;
end;
if right[now]=0 then
begin
inc(tot);
right[now]:=tot;
end;
if stop[now] then update(now);
if e<=mid then insert(c,s,e,l,mid,left[now])
else
if s>mid then insert(c,s,e,mid+1,r,right[now])
else
begin
insert(c,s,mid,l,mid,left[now]);
insert(c,mid+1,e,mid+1,r,right[now]);
end;
sum[now]:=sum[left[now]]+sum[right[now]];
if rb[left[now]]=lb[right[now]] then dec(sum[now]);
lb[now]:=lb[left[now]];
rb[now]:=rb[right[now]];
end;
function look (x,l,r,now:longint):longint;
var
mid:longint;
begin
if (x=l)or(stop[now]) then exit(lb[now]);
mid:=(l+r) div 2;
if x<=mid then exit(look(x,l,mid,left[now]))
else exit(look(x,mid+1,r,right[now]));
end;
function find (s,e,l,r,now:longint):longint;
var
ans,mid:longint;
begin
if (s=l)and(e=r) then exit(sum[now]);
if stop[now] then update(now);
mid:=(l+r) div 2;
if e<=mid then exit(find(s,e,l,mid,left[now]))
else
if s>mid then exit(find(s,e,mid+1,r,right[now]))
else
begin
ans:=find(s,mid,l,mid,left[now])+find(mid+1,e,mid+1,r,right[now]);
if rb[left[now]]=lb[right[now]] then dec(ans);
exit(ans);
end;
end;
function lca (a,b:longint):longint;inline;
var
i:longint;
begin
if height[a]<height[b] then swap(a,b);
while height[a]-height[b]<>0 do
a:=father[trunc(ln(height[a]-height[b])/ln(2)),a];
if a=b then exit(a);
i:=20;
repeat
if father[0,a]=father[0,b] then exit(father[0,a]);
while father[i,a]=father[i,b] do dec(i);
a:=father[i,a];
b:=father[i,b];
until false;
end;
procedure addup (now,high:longint);
var
i:longint;
begin
i:=0;
while father[i,now]<>0 do
begin
father[i+1,now]:=father[i,father[i,now]];
inc(i);
end;
height[now]:=high;
total[now]:=1;
go[now]:=0;
i:=root[now];
while i<>0 do
begin
if point[i]<>father[0,now] then
begin
father[0,point[i]]:=now;
addup(point[i],high+1);
if total[point[i]]+1>total[now] then
begin
total[now]:=total[point[i]]+1;
go[now]:=point[i];
end;
end;
i:=next[i];
end;
end;
procedure build (now,top:longint);
var
i:longint;
begin
up[now]:=top;
inc(tot);
num[now]:=tot;
if go[now]<>0 then build(go[now],top);
i:=root[now];
while i<>0 do
begin
if (point[i]<>go[now])and(point[i]<>father[0,now]) then
build(point[i],point[i]);
i:=next[i];
end;
end;
begin
assign(input,'paint.in');
reset(input);
assign(output,'paint.out');
rewrite(output);
read(n,m);
for i:=1 to n do
read(color[i]);
for i:=1 to n-1 do
begin
readln(x,y);
inc(dd[x]);
inc(dd[y]);
connect(x,y);
connect(y,x);
end;
for top:=1 to n do
if dd[top]=1 then break;
addup(top,1);
tot:=0;
build(top,top);
fillchar(stop,sizeof(stop),false);
for i:=1 to n do
insert(color[i],num[i],num[i],1,n,0);
for i:=1 to m do
begin
read(order);
if order='C' then
begin
readln(a,b,c);
fa:=lca(a,b);
while up[a]<>up[fa] do
begin
insert(c,num[up[a]],num[a],1,n,0);
a:=father[0,up[a]];
end;
insert(c,num[fa],num[a],1,n,0);
while up[b]<>up[fa] do
begin
insert(c,num[up[b]],num[b],1,n,0);
b:=father[0,up[b]];
end;
insert(c,num[fa],num[b],1,n,0);
end
else
begin
readln(a,b);
if a=b then
begin
writeln(1);
continue;
end;
fa:=lca(a,b);
ans:=0;
k:=0;
while up[a]<>up[fa] do
begin
ans:=ans+find(num[up[a]],num[a],1,n,0);
if look(num[a],1,n,0)=k then dec(ans);
k:=look(num[up[a]],1,n,0);
a:=father[0,up[a]];
end;
ans:=ans+find(num[fa],num[a],1,n,0);
if look(num[a],1,n,0)=k then dec(ans);
k:=0;
while up[b]<>up[fa] do
begin
ans:=ans+find(num[up[b]],num[b],1,n,0);
if look(num[b],1,n,0)=k then dec(ans);
k:=look(num[up[b]],1,n,0);
b:=father[0,up[b]];
end;
ans:=ans+find(num[fa],num[b],1,n,0);
if look(num[b],1,n,0)=k then dec(ans);
dec(ans);
writeln(ans);
end;
end;
close(input);
close(output);
end.