树链剖分，线段树维护三个值:区间颜色数、区间左端颜色、区间右端颜色，当左区间右端颜色=右区间左端颜色时候，总颜色-1，树上的维护类似。
代码
1 #include<cstdio> 2 const int M = 1001010; 3 const int N = 300010; 4 int dp,p[N],pre[N],tt[N],size[N],f[N],gf[N],go[N],deep[N],color[N]; 5 int id[N],n,m,i,a,b,c,tot,e[N]; 6 int l[M],r[M],lc[M],rc[M],s[M],v[M]; 7 void link(int x,int y) 8 { 9 dp++;pre[dp]=p[x];p[x]=dp;tt[dp]=y; 10 } 11 struct O{ 12 int ans,lc,rc; 13 void clear() 14 { 15 ans=0;lc=0;rc=0; 16 } 17 void set(int a,int b,int c) 18 { 19 ans=a;lc=b;rc=c; 20 } 21 }; 22 void dfs(int x,int fa) 23 { 24 int i=p[x]; 25 size[x]=1; 26 deep[x]=deep[fa]+1; 27 while (i) 28 { 29 if (tt[i]!=fa) 30 { 31 f[tt[i]]=x; 32 dfs(tt[i],x); 33 if (size[tt[i]]>size[go[x]]) go[x]=tt[i]; 34 size[x]+=size[tt[i]]; 35 } 36 i=pre[i]; 37 } 38 } 39 void gao(int x,int Fa,int fa) 40 { 41 int i=p[x]; 42 gf[x]=Fa;id[x]=++tot;e[tot]=color[x]; 43 if (go[x]) gao(go[x],Fa,x); 44 while (i) 45 { 46 if ((tt[i]!=fa)&&(tt[i]!=go[x])) 47 gao(tt[i],tt[i],x); 48 i=pre[i]; 49 } 50 } 51 void updata(int x) 52 { 53 lc[x]=lc[2*x]; 54 rc[x]=rc[2*x+1]; 55 s[x]=s[2*x]+s[2*x+1]; 56 if (rc[2*x]==lc[2*x+1]) s[x]--; 57 } 58 void build(int x,int a,int b) 59 { 60 int m; 61 l[x]=a;r[x]=b;v[x]=-1; 62 if (b-a>1) 63 { 64 m=(a+b)>>1; 65 build(2*x,a,m); 66 build(2*x+1,m,b); 67 updata(x); 68 } 69 else 70 { 71 lc[x]=e[b]; 72 rc[x]=e[b]; 73 s[x]=1; 74 } 75 } 76 void clean(int x) 77 { 78 if (v[x]>=0) 79 { 80 s[x]=1; 81 lc[x]=rc[x]=v[x]; 82 v[2*x]=v[x]; 83 v[2*x+1]=v[x]; 84 v[x]=-1; 85 } 86 } 87 void change(int x,int a,int b,int c) 88 { 89 int m; 90 clean(x); 91 if ((a<=l[x])&&(r[x]<=b)) 92 { 93 v[x]=c; 94 return; 95 } 96 m=(l[x]+r[x])>>1; 97 if (a<m) change(2*x,a,b,c); 98 if (m<b) change(2*x+1,a,b,c); 99 clean(2*x);clean(2*x+1); 100 updata(x); 101 } 102 O query(int x,int a,int b) 103 { 104 int m; 105 O tmp;tmp.clear(); 106 clean(x); 107 if ((a<=l[x])&&(r[x]<=b)) 108 { 109 tmp.set(s[x],lc[x],rc[x]); 110 return tmp; 111 } 112 m=(l[x]+r[x])>>1; 113 int L=-1,R=-1,A=-1; 114 if (a<m) 115 { 116 tmp=query(2*x,a,b); 117 L=tmp.lc; 118 R=tmp.rc; 119 A=tmp.ans; 120 } 121 if (m<b) 122 { 123 tmp=query(2*x+1,a,b); 124 if (L==-1) 125 { 126 L=tmp.lc; 127 R=tmp.rc; 128 A=tmp.ans; 129 } 130 else 131 { 132 A+=tmp.ans; 133 if (R==tmp.lc) A--; 134 R=tmp.rc; 135 } 136 } 137 tmp.set(A,L,R);return tmp; 138 } 139 void gai(int a,int b,int c) 140 { 141 while (1) 142 { 143 if (gf[a]==gf[b]) 144 { 145 if (deep[a]<deep[b]) a^=b^=a^=b; 146 change(1,id[b]-1,id[a],c); 147 return; 148 } 149 else 150 { 151 if (deep[gf[a]]<deep[gf[b]]) a^=b^=a^=b; 152 change(1,id[gf[a]]-1,id[a],c); 153 a=f[gf[a]]; 154 } 155 } 156 } 157 int wen(int a,int b) 158 { 159 int ac=-1,bc=-1,ans=0; 160 while (1) 161 { 162 if (gf[a]==gf[b]) 163 { 164 if (deep[a]<deep[b]) a^=b^=a^=b,ac^=bc^=ac^=bc; 165 O tmp=query(1,id[b]-1,id[a]); 166 ans+=tmp.ans; 167 if (tmp.rc==ac) ans--; 168 if (tmp.lc==bc) ans--; 169 return ans; 170 } 171 else 172 { 173 if (deep[gf[a]]<deep[gf[b]]) a^=b^=a^=b,ac^=bc^=ac^=bc; 174 O tmp=query(1,id[gf[a]]-1,id[a]); 175 ans+=tmp.ans; 176 if (tmp.rc==ac) ans--;ac=tmp.lc; 177 a=f[gf[a]]; 178 } 179 } 180 } 181 int main() 182 { 183 scanf("%d%d",&n,&m); 184 for (i=1;i<=n;i++) 185 scanf("%d",&color[i]); 186 for (i=1;i<n;i++) 187 { 188 scanf("%d%d",&a,&b); 189 link(a,b); 190 link(b,a); 191 } 192 dfs(1,0); 193 gao(1,1,0); 194 build(1,0,n); 195 for (i=1;i<=m;i++) 196 { 197 char typ; 198 scanf(" %c",&typ); 199 if (typ=='Q') 200 { 201 scanf("%d%d",&a,&b); 202 printf("%d ",wen(a,b)); 203 } 204 else 205 { 206 scanf("%d%d%d",&a,&b,&c); 207 gai(a,b,c); 208 } 209 } 210 }