【题目大意】：

给定一棵N颗节点无根树，每个结点有个颜色；以及M个操作：

C X Y Z 把X到Y的路径全染成Z颜色

Q X Y    询问X到Y的路径有多少个颜色段

【题目分析】：

1、树链剖分，线段树维护两端颜色及颜色段数；

2、动态树，Splay维护两段颜色及颜色段数；

在AndyBear的鼓舞下我使用Link—Cut—Tree AC了此题。（膜拜自顶而下的Splay）

PS：一个Splay里面的小Bug卡了我老半天……~~~~(>_<)~~~~

【附代码如下】：

Const	maxn=100000;Type	link=^node;	node=record		id:longint;		next:link;	end;Var	q,f,l,r,lc,rc,d,c,rev:array[0..maxn]of longint;	tp:array[0..maxn]of boolean;	ee:array[0..maxn*2]of node;	e:array[0..maxn]of link;	ne,n,m,x,y,z,i:longint; o:char;Procedure Swap(var a,b:boolean);	var t:boolean;	begin		t:=a; a:=b; b:=t;	end;Procedure Update(x:longint);	begin		if l[x]<>0 then lc[x]:=lc[l[x]] else lc[x]:=c[x];		if r[x]<>0 then rc[x]:=rc[r[x]] else rc[x]:=c[x];		d[x]:=d[l[x]]+d[r[x]]+1-ord(c[x]=rc[l[x]])-ord(c[x]=lc[r[x]]);	end;Procedure Zig(x:longint);	var y:longint;	begin		y:=f[x]; f[x]:=f[y]; Swap(tp[x],tp[y]);		if y=l[f[y]] then l[f[y]]:=x else		if y=r[f[y]] then r[f[y]]:=x;		l[y]:=r[x]; if r[x]<>0 then f[r[x]]:=y;		r[x]:=y; f[y]:=x;		Update(x); Update(y);	end;Procedure Zag(x:longint);	var y:longint;	begin		y:=f[x]; f[x]:=f[y]; Swap(tp[x],tp[y]);		if y=l[f[y]] then l[f[y]]:=x else		if y=r[f[y]] then r[f[y]]:=x;		r[y]:=l[x]; if l[x]<>0 then f[l[x]]:=y;		l[x]:=y; f[y]:=x;		Update(x); Update(y);	end;Procedure Modify(x,k:longint);	begin		if x=0 then exit;		lc[x]:=k; rc[x]:=k; c[x]:=k; d[x]:=1; rev[x]:=k;	end;Procedure Spread(x:longint);	begin		if rev[x]>0 then begin			Modify(l[x],rev[x]);			Modify(r[x],rev[x]);			rev[x]:=0;		end;	end;Procedure Splay(x,fa:longint);	var y:longint;	begin		Spread(x);		while (f[x]<>fa) and (not tp[x]) do begin			y:=f[x];			if (not tp[y]) and (f[y]<>0) then Spread(f[y]);			Spread(y); Spread(x);			if tp[y] or (f[y]=fa) then begin				if x=l[y] then Zig(x) else Zag(x); break;			end;			if x=l[y] then begin				if y=l[f[y]] then begin Zig(y); Zig(x); end else begin Zig(x); Zag(x); end;			end else begin				if y=r[f[y]] then begin Zag(y); Zag(x); end else begin Zag(x); Zig(x); end;			end;		end;	end;Procedure Color(x,y,k:longint);	var i:longint;	begin		i:=0;		while x<>0 do begin			Splay(x,0);			tp[r[x]]:=true; tp[x]:=true;			r[x]:=i; tp[i]:=false; f[i]:=x;			Update(x);			i:=x; x:=f[x];		end;		i:=0;		while y<>0 do begin			Splay(y,0);			if f[y]=0 then begin				c[y]:=k; Modify(r[y],k); Modify(i,k); Update(y);			end;			tp[r[y]]:=true; tp[y]:=true;			r[y]:=i; tp[i]:=false; f[i]:=y;			Update(y);			i:=y; y:=f[y];		end;	end;Function Query(x,y:longint):longint;	var i:longint;	begin		i:=0;		while x<>0 do begin			Splay(x,0);			tp[r[x]]:=true; tp[x]:=true;			r[x]:=i; tp[i]:=false; f[i]:=x;			Update(x);			i:=x; x:=f[x];		end;		i:=0;		while y<>0 do begin			Splay(y,0);			if f[y]=0 then begin				Query:=d[i]+d[r[y]]+1-ord(c[y]=lc[r[y]])-ord(c[y]=lc[i]);			end;			tp[r[y]]:=true; tp[y]:=true;			r[y]:=i; tp[i]:=false; f[i]:=y;			Update(y);			i:=y; y:=f[y];		end;		writeln(Query);	end;Procedure Add(x,y:longint);	var p:link;	begin		inc(ne); p:=@ee[ne]; p^.id:=y; p^.next:=e[x]; e[x]:=p;	end;Procedure Bfs;	var h,t:longint; p:link;	begin		h:=0; t:=1; q[1]:=1;		while h
     
      nil do with p^ do begin				if f[q[h]]<>id then begin					inc(t); q[t]:=id; f[id]:=q[h];				end;				p:=next;			end;		end;	end;Begin	Assign(input,'paint.in'); reset(input);	Assign(output,'paint.out'); rewrite(output);	readln(n,m);	for i:=1 to n do begin		read(c[i]); d[i]:=1; lc[i]:=c[i]; rc[i]:=c[i]; rev[i]:=0; tp[i]:=true;	end;	for i:=1 to n-1 do begin		readln(x,y); if x<>y then begin add(x,y); add(y,x); end;	end;	Bfs;	for i:=1 to m do begin		read(o);		case o of			'C':begin					readln(x,y,z); Color(x,y,z);				end;			'Q':begin					readln(x,y); Query(x,y);				end;		end;	end;	Close(input); Close(output);End.