给定一棵有n个节点的无根树和m个操作，操作有2类：

1、将节点a到节点b路径上所有点都染成颜色c；

2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。

请你写一个程序依次完成这m个操作。

第一行包含2个整数n和m，分别表示节点数和操作数；

第二行包含n个正整数表示n个节点的初始颜色

下面行每行包含两个整数x和y，表示x和y之间有一条无向边。

下面行每行描述一个操作：

“C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c；

“Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。

对于每个询问操作，输出一行答案。

数N<=10^5，操作数M<=10^5，所有的颜色C为整数且在[0, 10^9]之间。

第一轮day1

  1 #include<cstdio>  2 const int maxn=1e5+10;  3 inline int min_(int x,int y){return x<y?x:y;}  4 inline int max_(int x,int y){return x>y?x:y;}  5 inline void swap_(int&x,int&y){x^=y,y^=x,x^=y;}  6 int n,m;  7 int a,b,c,ans;  8 int ss,s[maxn];  9 int h[maxn],hs,et[maxn<<1],en[maxn<<1]; 10 int t[maxn<<2],tl[maxn<<2],tr[maxn<<2],tf[maxn<<2]; 11 int ps[maxn],pd[maxn],pf[maxn],psz[maxn],pws[maxn],pp[maxn],pps,pt[maxn]; 12 void dfs1(int k,int f,int d){ 13     psz[k]=1,pf[k]=f,pd[k]=d; 14     for(int i=h[k];i;i=en[i]) 15     if(et[i]!=f){ 16         dfs1(et[i],k,d+1); 17         psz[k]+=psz[et[i]]; 18         if(psz[et[i]]>psz[pws[k]]) pws[k]=et[i]; 19     } 20 } 21 void dfs2(int k,int t){ 22     ++pps,s[pps]=ps[k],pp[k]=pps,pt[k]=t; 23     if(pws[k]) dfs2(pws[k],t); 24     for(int i=h[k];i;i=en[i]) 25     if(et[i]!=pf[k]&&et[i]!=pws[k]) 26     dfs2(et[i],et[i]); 27 } 28 void build(int k,int l,int r){ 29     if(l==r){tl[k]=tr[k]=s[++ss],t[k]++;return;} 30     int mid=l+r>>1,ls=k<<1,rs=ls|1; 31     build(ls,l,mid); 32     build(rs,mid+1,r); 33     t[k]=t[ls]+t[rs]; 34     if(tr[ls]==tl[rs]) t[k]--; 35     tl[k]=tl[ls],tr[k]=tr[rs]; 36 } 37 void down(int k){ 38     int ls=k<<1,rs=ls|1; 39     tl[ls]=tr[ls]=tl[rs]=tr[rs]=tf[ls]=tf[rs]=tf[k]; 40     t[ls]=t[rs]=1; 41     tf[k]=0; 42 } 43 void change(int k,int l,int r,int al,int ar,int v){ 44     if(l==al&&r==ar){tl[k]=tr[k]=tf[k]=v,t[k]=1;return;} 45     if(tf[k]) down(k); 46     int mid=l+r>>1,ls=k<<1,rs=ls|1; 47     if(al<=mid) change(ls,l,mid,al,min_(ar,mid),v); 48     if(ar>mid) change(rs,mid+1,r,max_(al,mid+1),ar,v); 49     t[k]=t[ls]+t[rs]; 50     if(tr[ls]==tl[rs]) t[k]--; 51     tl[k]=tl[ls],tr[k]=tr[rs]; 52 } 53 int query(int k,int l,int r,int al,int ar){ 54     if(l==al&&r==ar) return t[k]; 55     if(tf[k]) down(k); 56     int mid=l+r>>1,ls=k<<1,rs=ls|1,ret=0,nl=0,nr=0; 57     if(al<=mid) ret+=query(ls,l,mid,al,min_(ar,mid)),nl=tr[ls]; 58     if(ar>mid) ret+=query(rs,mid+1,r,max_(al,mid+1),ar),nr=tl[rs]; 59     if(nl&&nr&&nl==nr) ret--; 60     return ret; 61 } 62 int color(int k,int l,int r,int v){ 63     if(l==r) return tl[k]; 64     if(tf[k]) down(k); 65     int mid=l+r>>1,ls=k<<1,rs=ls|1; 66     if(v<=mid) return color(ls,l,mid,v); 67     else return color(rs,mid+1,r,v); 68 } 69 int main(){ 70     scanf("%d%d",&n,&m); 71     for(int i=1;i<=n;i++) scanf("%d",&ps[i]); 72     for(int i=1;i<n;i++){ 73         scanf("%d%d",&a,&b); 74         ++hs,et[hs]=b,en[hs]=h[a],h[a]=hs; 75         ++hs,et[hs]=a,en[hs]=h[b],h[b]=hs; 76     } 77     dfs1(1,0,1); 78     dfs2(1,1); 79     build(1,1,n); 80     char ch[3]; 81     while(m--){ 82         scanf("%s",ch); 83         if(ch[0]==‘C‘){ 84             scanf("%d%d%d",&a,&b,&c); 85             while(pt[a]!=pt[b]){ 86                 if(pd[pt[a]]<pd[pt[b]]) swap_(a,b); 87                 change(1,1,n,pp[pt[a]],pp[a],c); 88                 a=pf[pt[a]]; 89             } 90             if(pd[a]>pd[b]) swap_(a,b); 91             change(1,1,n,pp[a],pp[b],c); 92         } 93         if(ch[0]==‘Q‘){ 94             scanf("%d%d",&a,&b),ans=0; 95             while(pt[a]!=pt[b]){ 96                 if(pd[pt[a]]<pd[pt[b]]) swap_(a,b); 97                 ans+=query(1,1,n,pp[pt[a]],pp[a]); 98                 if(color(1,1,n,pp[pf[pt[a]]])==color(1,1,n,pp[pt[a]])) ans--; 99                 a=pf[pt[a]];100             }101             if(pd[a]>pd[b]) swap_(a,b);102             ans+=query(1,1,n,pp[a],pp[b]);103             printf("%d\n",ans);104         }105     }106     return 0;107 }