明明是道树剖的题……
然而我硬生生做成了LCT
虽然的确用LCT只是板子啦（LCT的题哪道不是板子）
就是把颜色打上标记，然后基本就是板子
1 //minamoto 2 #include<bits/stdc++.h> 3 using namespace std; 4 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 5 char buf[1<<21],*p1=buf,*p2=buf; 6 inline int read(){ 7 #define num ch-'0' 8 char ch;bool flag=0;int res; 9 while(!isdigit(ch=getc())) 10 (ch=='-')&&(flag=true); 11 for(res=num;isdigit(ch=getc());res=res*10+num); 12 (flag)&&(res=-res); 13 #undef num 14 return res; 15 } 16 char obuf[1<<24],*o=obuf; 17 inline void print(int x){ 18 if(x>9) print(x/10); 19 *o++=x%10+48; 20 } 21 const int N=100005; 22 int fa[N],s[N],ch[N][2],col[N],lcol[N],rcol[N],tag[N],rev[N],tot[N],top; 23 inline bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;} 24 void pushup(int x){ 25 lcol[x]=ch[x][0]?lcol[ch[x][0]]:col[x]; 26 rcol[x]=ch[x][1]?rcol[ch[x][1]]:col[x]; 27 tot[x]=1; 28 if(ch[x][0]) tot[x]+=tot[ch[x][0]]-(rcol[ch[x][0]]==col[x]); 29 if(ch[x][1]) tot[x]+=tot[ch[x][1]]-(lcol[ch[x][1]]==col[x]); 30 } 31 inline void pushrev(int x){if(x) rev[x]^=1,swap(ch[x][0],ch[x][1]),swap(lcol[x],rcol[x]);} 32 inline void change(int x,int y){if(x) tag[x]=col[x]=lcol[x]=rcol[x]=y,tot[x]=1;} 33 inline void pushdown(int x){ 34 if(rev[x]) pushrev(ch[x][0]),pushrev(ch[x][1]),rev[x]=0; 35 if(tag[x]) change(ch[x][0],tag[x]),change(ch[x][1],tag[x]),tag[x]=0; 36 } 37 void rotate(int x){ 38 int y=fa[x],z=fa[y],d=ch[y][1]==x; 39 if(!isroot(y)) ch[z][ch[z][1]==y]=x; 40 fa[x]=z,fa[y]=x,fa[ch[x][d^1]]=y,ch[y][d]=ch[x][d^1],ch[x][d^1]=y;pushup(y); 41 } 42 void splay(int x){ 43 s[top=1]=x;for(int i=x;!isroot(i);i=fa[i]) s[++top]=fa[i]; 44 for(int i=top;i;--i) pushdown(s[i]); 45 for(int y=fa[x],z=fa[y];!isroot(x);y=fa[x],z=fa[y]){ 46 if(!isroot(y)) ((ch[y][1]==x)^(ch[z][1]==y))?rotate(x):rotate(y); 47 rotate(x); 48 } 49 pushup(x); 50 } 51 void access(int x){for(int y=0;x;x=fa[y=x]) splay(x),ch[x][1]=y,pushup(x);} 52 void makeroot(int x){access(x),splay(x),pushrev(x);} 53 void split(int x,int y){makeroot(x),access(y),splay(y);} 54 void link(int x,int y){makeroot(x),fa[x]=y;} 55 void cut(int x,int y){split(x,y),fa[x]=ch[y][0]=0;} 56 int main(){ 57 //freopen("testdata.in","r",stdin); 58 int n=read(),m=read(); 59 for(int i=1;i<=n;++i) col[i]=lcol[i]=rcol[i]=read(),tot[i]=1; 60 for(int i=1;i<n;++i){ 61 int u=read(),v=read(); 62 link(u,v); 63 } 64 while(m--){ 65 char ch; 66 while((ch=getc())!='C'&&ch!='Q'); 67 int a=read(),b=read();split(a,b); 68 if(ch=='C'){int k=read();change(b,k);} 69 else print(tot[b]),*o++=' '; 70 } 71 fwrite(obuf,o-obuf,1,stdout); 72 return 0; 73 }