学完LCT后赶脚树剖忘光光了
LCT板子题LCT的全是板子题
对每个点维护区间最左边的颜色lcol，区间最右边的颜色rcol和颜色段数tot。
合并时若左边的rcol==右边的lcol，新的tot=左tot+右tot-1；
不是就新tot=左tot+右tot
修改打个覆盖标记即可。
注意：翻转操作要修改lcol和rcol！！！
注意：翻转操作要修改lcol和rcol！！！
注意：翻转操作要修改lcol和rcol！！！
蒟蒻因为这个de了1.5h的bug。。。
// It is made by XZZ
#include<cstdio>
#include<algorithm>
#define il inline
#define rg register
#define vd void
#define sta static
typedef long long ll;
il int gi(){
rg int x=0,f=1;rg char ch=getchar();
while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int maxn=100001;
int ch[maxn][2],fa[maxn],tot[maxn],col[maxn],lcol[maxn],rcol[maxn],tag[maxn];
bool rev[maxn];
typedef const int& fast;
il vd upd(fast x){
lcol[x]=ch[x][0]?lcol[ch[x][0]]:col[x];
rcol[x]=ch[x][1]?rcol[ch[x][1]]:col[x];
if(ch[x][0]&&ch[x][1])tot[x]=tot[ch[x][0]]+tot[ch[x][1]]+1-(rcol[ch[x][0]]==col[x])-(lcol[ch[x][1]]==col[x]);
else if(ch[x][0])tot[x]=tot[ch[x][0]]+(rcol[ch[x][0]]!=col[x]);
else if(ch[x][1])tot[x]=tot[ch[x][1]]+(lcol[ch[x][1]]!=col[x]);
else tot[x]=1;
}
il bool isrt(fast x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
il vd Rev(fast x){if(x)rev[x]^=1,std::swap(ch[x][0],ch[x][1]),std::swap(lcol[x],rcol[x]);}
il vd Change(fast x,int y){if(x)tag[x]=y,col[x]=lcol[x]=rcol[x]=y,tot[x]=1;}
il vd down(fast x){
if(!isrt(x))down(fa[x]);
if(rev[x])Rev(ch[x][0]),Rev(ch[x][1]),rev[x]=0;
if(tag[x])Change(ch[x][0],tag[x]),Change(ch[x][1],tag[x]),tag[x]=0;
}
il vd rotate(fast x){
sta int y,z,o;y=fa[x],z=fa[y],o=x==ch[y][1];
if(!isrt(y))ch[z][y==ch[z][1]]=x;fa[x]=z;
ch[y][o]=ch[x][!o];fa[ch[x][!o]]=y;
fa[y]=x,ch[x][!o]=y;
upd(y);
}
il vd splay(fast x){
down(x);
sta int y,z;
for(y=fa[x],z=fa[y];!isrt(x);rotate(x),y=fa[x],z=fa[y])
if(!isrt(y))rotate(((ch[y][0]==x)^(ch[z][0]==y))?x:y);
upd(x);
}
il vd access(int x){for(rg int y=0;x;x=fa[y=x])splay(x),ch[x][1]=y,upd(x);}
il vd makert(fast x){access(x),splay(x),Rev(x);}
il vd split(fast x,fast y){makert(x),access(y),splay(y);}
il vd link(fast x,fast y){makert(x),fa[x]=y;}
int main(){
freopen("2243.in","r",stdin);
freopen("2243.out","w",stdout);
int n=gi(),m=gi();
for(rg int i=1;i<=n;++i)col[i]=lcol[i]=rcol[i]=gi(),tot[i]=1;
for(rg int i=1;i<n;++i)link(gi(),gi());
while(m--){
sta char opt[10];sta int a,b;
scanf("%s",opt),a=gi(),b=gi();
split(a,b);
if(opt[0]=='C')Change(b,gi());
else printf("%d
",tot[b]);
}
return 0;
}