bzoj 2243: [SDOI2011]染色

  1 #include<cstdio>
  2 #include<iostream>
  3 #define M 1000006
  4 #define N 1000006
  5 using namespace std;
  6 int head[N],next[M],u[M],se[N],se1[N],n,m,size[N],l[N],lc[N][22],f1[N],cnt,dui[N],lian[N],tim,l1,l2;
  7 int r1;
  8 struct data
  9 {
 10     int l,r,sum,tag;
 11 }shu[4*N];
 12 void jia(int a1,int a2)
 13 {
 14     cnt++;
 15     next[cnt]=head[a1];
 16     head[a1]=cnt;
 17     u[cnt]=a2;
 18     return;
 19 }
 20 void dfs(int a1)
 21 {
 22     f1[a1]=1;
 23     size[a1]=1;
 24     for(int i=1;i<=21;i++)
 25       {
 26         if(l[a1]<(1>>i))
 27           break;
 28         lc[a1][i]=lc[lc[a1][i-1]][i-1];
 29       }
 30     for(int i=head[a1];i;i=next[i])
 31       if(!f1[u[i]])
 32         {
 33             lc[u[i]][0]=a1;
 34             l[u[i]]=l[a1]+1;
 35             dfs(u[i]);
 36             size[a1]+=size[u[i]];
 37         }
 38     return;
 39 }
 40 void dfs1(int a1,int a2)
 41 {
 42     tim++;
 43     dui[a1]=tim;
 44     lian[a1]=a2;
 45     int k=0;
 46     for(int i=head[a1];i;i=next[i])
 47       if(!dui[u[i]]&&size[k]<size[u[i]])
 48         k=u[i];
 49     if(!k)
 50       return;
 51     dfs1(k,a2);
 52     for(int i=head[a1];i;i=next[i])
 53       if(!dui[u[i]])
 54         dfs1(u[i],u[i]);
 55     return;
 56 }
 57 void geng(int a1)
 58 {
 59     shu[a1].l=shu[a1*2].l;
 60     shu[a1].r=shu[a1*2+1].r;
 61     shu[a1].sum=shu[a1*2].sum+shu[a1*2+1].sum;
 62     if(shu[a1*2].r==shu[a1*2+1].l)
 63       shu[a1].sum--;
 64     return;
 65 }
 66 void build(int a1,int a2,int a3)
 67 {
 68     if(a2==a3)
 69       {
 70         shu[a1].sum=1;
 71         shu[a1].l=se1[a2];
 72         shu[a1].r=se1[a2];
 73         return;
 74       }
 75     int mid=(a2+a3)>>1;
 76     build(a1*2,a2,mid);
 77     build(a1*2+1,mid+1,a3);
 78     geng(a1);
 79     return;
 80 }
 81 int lca(int a1,int a2)
 82 {
 83     if(l[a1]<l[a2])
 84       swap(a1,a2);
 85     int a3=l[a1]-l[a2];
 86     for(int i=0;i<=21;i++) 
 87       if(a3&(1<<i))
 88         a1=lc[a1][i];
 89     for(int i=21;i>=0;i--)
 90       if(lc[a1][i]!=lc[a2][i])
 91         {
 92             a1=lc[a1][i];
 93             a2=lc[a2][i];
 94         }
 95     if(a1==a2)
 96       return a1;
 97     return lc[a1][0];
 98 }
 99 void geng1(int a1)
100 {
101     int a2=shu[a1].l;
102     shu[a1*2].l=a2;
103     shu[a1*2].r=a2;
104     shu[a1*2].sum=1;
105     shu[a1*2].tag=1;
106     shu[a1*2+1].l=a2;
107     shu[a1*2+1].r=a2;
108     shu[a1*2+1].sum=1;
109     shu[a1*2+1].tag=1;
110     shu[a1].tag=0;
111 }
112 void gai1(int a1,int a2,int a3,int a4,int a5,int a6)
113 {
114     if(a4<=a2&&a5>=a3)
115       {
116          shu[a1].l=a6;
117          shu[a1].r=a6;
118          shu[a1].sum=1;
119          shu[a1].tag=1;
120          return;
121       }
122     if(shu[a1].tag)
123       geng1(a1);
124     int mid=(a2+a3)>>1;
125     if(a4<=mid)
126       gai1(a1*2,a2,mid,a4,a5,a6);
127     if(a5>mid)
128       gai1(a1*2+1,mid+1,a3,a4,a5,a6);
129     geng(a1);
130 }
131 void gai(int a1,int t,int a3)
132 {
133     for(;lian[a1]!=lian[t];)
134       {
135         gai1(1,1,n,dui[lian[a1]],dui[a1],a3);
136         a1=lc[lian[a1]][0];
137       }
138     gai1(1,1,n,dui[t],dui[a1],a3);
139 }
140 int xun1(int a1,int a2,int a3,int a4,int a5)
141 {
142     int ss=0;
143     if(a4<=a2&&a5>=a3)
144       {
145         if(l1==-1)
146           l1=shu[a1].l;
147         r1=shu[a1].r;
148         return shu[a1].sum;
149       }
150     if(shu[a1].tag)
151       geng1(a1);
152     int mid=(a2+a3)>>1;
153     if(a4<=mid)
154       ss+=xun1(a1*2,a2,mid,a4,a5);
155     if(a5>mid)
156       ss+=xun1(a1*2+1,mid+1,a3,a4,a5);
157     if(a4<=mid&&a5>mid&&shu[a1*2].r==shu[a1*2+1].l)
158       ss--;
159     return ss;
160 }
161 int xun(int a1,int t)
162 {
163     int sum=0;
164     l2=-1;
165     for(;lian[a1]!=lian[t];)
166       {
167         l1=-1;
168         sum+=xun1(1,1,n,dui[lian[a1]],dui[a1]);
169         a1=lc[lian[a1]][0];
170         if(r1==l2)
171           sum--;
172         l2=l1;
173       }
174     l1=-1;
175     sum+=xun1(1,1,n,dui[t],dui[a1]);
176     if(r1==l2)
177       sum--;
178     return sum;
179 }
180 int main()
181 {
182     scanf("%d%d",&n,&m);
183     for(int i=1;i<=n;i++)
184       scanf("%d",&se[i]);
185     for(int i=1;i<n;i++)
186       {
187         int a1,a2;
188         scanf("%d%d",&a1,&a2);
189         jia(a1,a2);
190         jia(a2,a1);
191       }
192     dfs(1);
193     dfs1(1,1);
194     for(int i=1;i<=n;i++)
195       se1[dui[i]]=se[i];
196     build(1,1,n);
197     char ch[5];
198     for(int i=1;i<=m;i++)
199       {
200         int a1,a2,a3=0,a5=0;
201         scanf("%s%d%d",ch,&a1,&a2);
202         int t=lca(a1,a2);
203         if(ch[0]==‘C‘)
204           {
205             scanf("%d",&a3);
206             gai(a1,t,a3);
207             gai(a2,t,a3);
208           }
209         else
210           {
211             a3=xun(a1,t);
212             a5=xun(a2,t);
213             a3+=a5;
214             a3--;
215             printf("%d\n",a3);
216           }
217       }
218     return 0;
219 }