BZOJ2243 [SDOI2011]染色（LCT）

传送门

明明是道树剖的题……

然而我硬生生做成了LCT

虽然的确用LCT只是板子啦（LCT的题哪道不是板子）

就是把颜色打上标记，然后基本就是板子

 //minamoto

 #include<bits/stdc++.h>

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 char obuf[<<],*o=obuf;

 inline void print(int x){

     if(x>) print(x/);

     *o++=x%+;

 }

 const int N=;

 int fa[N],s[N],ch[N][],col[N],lcol[N],rcol[N],tag[N],rev[N],tot[N],top;

 inline bool isroot(int x){return ch[fa[x]][]!=x&&ch[fa[x]][]!=x;}

 void pushup(int x){

     lcol[x]=ch[x][]?lcol[ch[x][]]:col[x];

     rcol[x]=ch[x][]?rcol[ch[x][]]:col[x];

     tot[x]=;

     if(ch[x][]) tot[x]+=tot[ch[x][]]-(rcol[ch[x][]]==col[x]);

     if(ch[x][]) tot[x]+=tot[ch[x][]]-(lcol[ch[x][]]==col[x]);

 }

 inline void pushrev(int x){if(x) rev[x]^=,swap(ch[x][],ch[x][]),swap(lcol[x],rcol[x]);}

 inline void change(int x,int y){if(x) tag[x]=col[x]=lcol[x]=rcol[x]=y,tot[x]=;}

 inline void pushdown(int x){

     if(rev[x]) pushrev(ch[x][]),pushrev(ch[x][]),rev[x]=;

     if(tag[x]) change(ch[x][],tag[x]),change(ch[x][],tag[x]),tag[x]=;

 }

 void rotate(int x){

     int y=fa[x],z=fa[y],d=ch[y][]==x;

     if(!isroot(y)) ch[z][ch[z][]==y]=x;

     fa[x]=z,fa[y]=x,fa[ch[x][d^]]=y,ch[y][d]=ch[x][d^],ch[x][d^]=y;pushup(y);

 }

 void splay(int x){

     s[top=]=x;for(int i=x;!isroot(i);i=fa[i]) s[++top]=fa[i];

     for(int i=top;i;--i) pushdown(s[i]);

     for(int y=fa[x],z=fa[y];!isroot(x);y=fa[x],z=fa[y]){

         if(!isroot(y)) ((ch[y][]==x)^(ch[z][]==y))?rotate(x):rotate(y);

         rotate(x);

     }

     pushup(x);

 }

 void access(int x){for(int y=;x;x=fa[y=x]) splay(x),ch[x][]=y,pushup(x);}

 void makeroot(int x){access(x),splay(x),pushrev(x);}

 void split(int x,int y){makeroot(x),access(y),splay(y);}

 void link(int x,int y){makeroot(x),fa[x]=y;}

 void cut(int x,int y){split(x,y),fa[x]=ch[y][]=;}

 int main(){

     //freopen("testdata.in","r",stdin);

     int n=read(),m=read();

     for(int i=;i<=n;++i) col[i]=lcol[i]=rcol[i]=read(),tot[i]=;

     for(int i=;i<n;++i){

         int u=read(),v=read();

         link(u,v);

     }

     while(m--){

         char ch;

         while((ch=getc())!='C'&&ch!='Q');

         int a=read(),b=read();split(a,b);

         if(ch=='C'){int k=read();change(b,k);}

         else print(tot[b]),*o++='\n';

     }

     fwrite(obuf,o-obuf,,stdout);

     return ;

 }