[SDOI2011]染色

VI.[SDOI2011]染色

你们知道吗？LCT考的就两个，一个\(pushup\)，一个\(pushdown\)。

这里就是经典的维护颜色段。在每个节点，我们维护四个值：\(lc\)，左端颜色；\(rc\)：右端颜色；\(sc\)：区间颜色段数；\(col\)：当前点的颜色。

然后就是经典的老套路了。

注意！！！在splay翻转时，要同时交换\(lc\)和\(rc\)！！！如果你做过经典大毒瘤题，应该就没问题了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define lson t[x].ch[0]
#define rson t[x].ch[1]
int n,m;
struct LCT{
	int ch[2],fa,col,lc,rc,sc,rev,tag;
}t[100100];
int identify(int x){
	if(t[t[x].fa].ch[0]==x)return 0;
	if(t[t[x].fa].ch[1]==x)return 1;
	return -1;
}
void REV(int x){
	t[x].rev^=1,swap(lson,rson),swap(t[x].lc,t[x].rc);
}
void CHANGE(int x,int y){
	t[x].lc=t[x].rc=t[x].col=t[x].tag=y,t[x].sc=1;
}
void pushdown(int x){
	if(t[x].rev){
		if(lson)REV(lson);
		if(rson)REV(rson);
		t[x].rev=0;
	}
	if(t[x].tag){
		if(lson)CHANGE(lson,t[x].tag);
		if(rson)CHANGE(rson,t[x].tag);
		t[x].tag=0;
	}
}
void pushup(int x){
	t[x].sc=1,t[x].lc=t[x].rc=t[x].col;
	if(lson){
		t[x].sc+=t[lson].sc;
		t[x].lc=t[lson].lc;
		if(t[lson].rc==t[x].col)t[x].sc--;
	}
	if(rson){
		t[x].sc+=t[rson].sc;
		t[x].rc=t[rson].rc;
		if(t[rson].lc==t[x].col)t[x].sc--;
	}
}
void rotate(int x){
	int y=t[x].fa;
	int z=t[y].fa;
	int dirx=identify(x);
	int diry=identify(y);
	int b=t[x].ch[!dirx];
	if(diry!=-1)t[z].ch[diry]=x;t[x].fa=z;
	if(b)t[b].fa=y;t[y].ch[dirx]=b;
	t[x].ch[!dirx]=y,t[y].fa=x;
	pushup(y),pushup(x);
}
void pushall(int x){
	if(identify(x)!=-1)pushall(t[x].fa);
	pushdown(x);
}
void splay(int x){
	pushall(x);
	while(identify(x)!=-1){
		int fa=t[x].fa;
		if(identify(fa)==-1)rotate(x);
		else if(identify(x)==identify(fa))rotate(fa),rotate(x);
		else rotate(x),rotate(x);
	}
}
void access(int x){
	for(int y=0;x;x=t[y=x].fa)splay(x),rson=y,pushup(x);
}
void makeroot(int x){
	access(x),splay(x),REV(x);
}
void link(int x,int y){
	makeroot(x),t[x].fa=y;
}
void split(int x,int y){
	makeroot(x),access(y),splay(y);
}
void change(int x,int y,int z){
	split(x,y),CHANGE(y,z);
}
int query(int x,int y){
	split(x,y);
	return t[y].sc;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x;i<=n;i++)scanf("%d",&x),CHANGE(i,x);
	for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),link(x,y);
	for(int i=1,x,y,z;i<=m;i++){
		char s[10];
		scanf("%s",s);
		if(s[0]=='Q')scanf("%d%d",&x,&y),printf("%d\n",query(x,y));
		else scanf("%d%d%d",&x,&y,&z),change(x,y,z);
	}
	return 0;
}