1 #include<cmath>  2 #include<cstdio>  3 #include<cstring>  4 #include<cstdlib>  5 #include<algorithm>  6 #include<iostream>  7 #define N 100100  8 #define M 200100  9 using namespace std; 10  11 int n,m,a,b,p; 12 int color[N],head[N],go[M],next[M]; 13  14 void build(int a,int b) 15 { 16     go[++p]=b; 17     next[p]=head[a]; 18     head[a]=p; 19 } 20  21 struct dfsdata 22 { 23     int a,i; 24     void newdata(int x,int y){a=x;i=y;} 25 }Stack[N]; 26  27 struct makedata 28 { 29     int a,i,yes; 30     void newdata(int x,int y,int z=1){a=x;i=y;yes=z;} 31 }S[N]; 32  33 int tail,f[N],size[N],max_son[N],u,v,deep[N]; 34  35 void dfs() 36 { 37     int i; 38     Stack[tail=1].newdata(1,head[1]);f[1]=0;size[1]=1;deep[1]=1; 39     while (tail) 40     { 41         i=Stack[tail].i;v=Stack[tail].a; 42         if (!i) 43         { 44             size[f[v]]+=size[v]; 45             if (size[v]>size[max_son[f[v]]]) max_son[f[v]]=v; 46             tail--; 47             continue; 48         } 49         u=go[i]; 50         Stack[tail].i=next[i]; 51         if (f[v]!=u) 52         { 53             size[u]=1; 54             f[u]=v; 55             deep[u]=deep[v]+1; 56             Stack[++tail].newdata(u,head[u]); 57         } 58     } 59 } 60  61 int L[N],l_deep[N],top[N],len,que[N]; 62  63 void make() 64 { 65     int i; 66     S[tail=1].newdata(1,head[1]);L[1]=len=1;l_deep[1]=1;top[1]=1;que[1]=1; 67     while (tail) 68     { 69         v=S[tail].a;i=S[tail].i; 70         if (!i || size[v]==1){tail--;continue;} 71         if (S[tail].yes) 72         { 73             S[tail].yes=0; 74             u=max_son[v]; 75             L[u]=++len; 76             que[len]=u; 77             l_deep[u]=l_deep[v]; 78             top[u]=top[v]; 79             S[++tail].newdata(u,head[u]); 80             continue; 81         } 82         u=go[i]; 83         S[tail].i=next[i]; 84         if (u!=f[v] && u!=max_son[v]) 85         { 86             L[u]=++len; 87             que[len]=u; 88             l_deep[u]=l_deep[v]+1; 89             top[u]=u; 90             S[++tail].newdata(u,head[u]); 91         } 92     } 93 } 94  95 //==========================SegmentTree===========================// 96 int tree[N<<2],SL[N<<2],SR[N<<2],LZ[N<<2],lazy[N<<2]; 97  98 void update(int a) 99 {100     tree[a]=tree[a<<1]+tree[(a<<1)+1];101     SL[a]=SL[a<<1];SR[a]=SR[(a<<1)+1];102     if (SR[a<<1]==SL[(a<<1)+1]) tree[a]--;103 }104 105 void BuildTree(int p,int l,int r)106 {107     if (l==r)108     {109         tree[p]=1;110         SL[p]=SR[p]=color[que[l]];111         return;112     }113     int mid=(l+r)>>1;114     BuildTree(p<<1,l,mid);115     BuildTree((p<<1)+1,mid+1,r);116     update(p);117 }118 119 void Push_down(int a)120 {121     if (!LZ[a]) return;122     LZ[a]=0;123     LZ[a<<1]=LZ[(a<<1)+1]=1;124     lazy[a<<1]=lazy[(a<<1)+1]=lazy[a];125     SL[a<<1]=SR[a<<1]=SL[(a<<1)+1]=SR[(a<<1)+1]=lazy[a];126     tree[a]=tree[a<<1]=tree[(a<<1)+1]=1;127 }128 129 void Change(int p,int l,int r,int fl,int fr,int c)130 {131     if (fl<=l&&r<=fr)132     {133         LZ[p]=1;134         lazy[p]=c;135         SL[p]=SR[p]=c;136         tree[p]=1;137         return;138     }139     Push_down(p);140     int mid=(l+r)>>1;141     if (fl<=mid) Change(p<<1,l,mid,fl,fr,c);142     if (fr>mid) Change((p<<1)+1,mid+1,r,fl,fr,c);143     update(p);144 }145 146 int Query(int p,int l,int r,int fl,int fr,int al,int &x,int ar,int &y)147 {148     if (l==fl&&r==fr)149     {150         if (LZ[p])151         {152             if (l==r)153             {154                 LZ[p]=0;155                 tree[p]=1;156                 SL[p]=SR[p]=lazy[p];157             }158             else Push_down(p),update(p);159         }160         if (l==al) x=SL[p];161         if (r==ar) y=SR[p];162         return tree[p];163     }164     Push_down(p);165     int mid=(l+r)>>1;166     if (fr<=mid) return Query(p<<1,l,mid,fl,fr,al,x,ar,y);167     if (fl>mid) return Query((p<<1)+1,mid+1,r,fl,fr,al,x,ar,y);168     int ans=Query(p<<1,l,mid,fl,mid,al,x,ar,y)+Query((p<<1)+1,mid+1,r,mid+1,fr,al,x,ar,y);169     if (SR[p<<1]==SL[(p<<1)+1]) ans--;170     return ans;171 }172 //==========================SegmentTree===========================//173 174 void Change(int a,int b,int c)175 {176     while (top[a]!=top[b])177     {178         if (l_deep[a]<l_deep[b]) swap(a,b);179         color[a]=c;180         if (top[a]!=a)181         {182             Change(1,1,n,L[top[a]],L[a],c);183             a=top[a];184         }185         else186         {187             Change(1,1,n,L[a],L[a],c);188             a=f[a];189         }190     }191     color[a]=color[b]=c;192     if (L[a]>L[b]) swap(a,b);193     Change(1,1,n,L[a],L[b],c);194 }195 196 void Query(int a,int b)197 {198     int ans=0,ac=-1,bc=-1,x,y;199     if (a==b)200     {201         printf("1\n");202         return;203     }204     while (top[a]!=top[b])205     {206         if (l_deep[a]<l_deep[b]) swap(a,b),swap(ac,bc);207         if (top[a]!=a)208         {209             ans+=Query(1,1,n,L[top[a]]+1,L[a],L[top[a]]+1,x,L[a],y);210             if (y==ac) ans--;211             ac=x;212             a=top[a];213         }214         else215         {216             ans+=Query(1,1,n,L[a],L[a],L[a],x,L[a],y);217             if (y==ac) ans--;218             ac=x;219             a=f[a];220         }221     }222     if (L[a]>L[b]) swap(a,b),swap(ac,bc);223     ans+=Query(1,1,n,L[a],L[b],L[a],x,L[b],y);224     if (x==ac) ans--;225     if (y==bc) ans--;226     printf("%d\n",ans);227 }228 229 int main()230 {231     scanf("%d%d",&n,&m);232     for (int i=1;i<=n;i++) scanf("%d",color+i);233     for (int i=1;i<n;i++)234     {235         scanf("%d%d\n",&a,&b);236         build(a,b);237         build(b,a);238     }239     dfs();240     make();241     BuildTree(1,1,n);242     for (int i=1;i<=m;i++)243     {244         char ch;int c;245         scanf("%c",&ch);246         if (ch==‘C‘)247         {248             scanf("%d%d%d\n",&a,&b,&c);249             Change(a,b,c);250         }251         else252         {253             scanf("%d%d\n",&a,&b);254             Query(a,b);255         }256     }257     return 0;258 }