LOJ10141染色

SDOI 2011 染色

给定一棵有 n 个节点的无根树和 m 个操作，操作共两类。

将节点 a 到节点 b 路径上的所有节点都染上颜色；

询问节点 a 到节点 b 路径上的颜色段数量，连续相同颜色的认为是同一段，例如 112221 由三段组成：11 、 222、1。

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

输入格式
第一行包括两个整数 n,m，表示节点数和操作数；

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

接下来若干行包含两个整数 x 和 y，表示 x 和 y 之间有一条无向边；

接下来若干行每行描述一个操作：

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

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

输出格式
对于每个询问操作，输出一行询问结果。

样例
样例输入
6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5
样例输出
3
1
2
数据范围与提示
对于 100% 的数据，N,M≤10^5，所有颜色 C 为整数且在 [0,10^9] 之间。

_____________________________________________________________________________________

树链剖分，需要维护

sum[]：表示段内的色段数

lc[]：表示左侧点的颜色

rc[]：表示右侧点的颜色

所以，

sum[cur]=sum[cur<<1]+sum[cur<<1|1]-(rc[cur<<1]==lc[cur<<1|1])

lc[cur]=lc[cur<<1]

rc[cur]=rc[cur<<1|1]

需要注意，树链之间两点的颜色是否相同。

———————————————————————————————————————————————

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int maxn=1e5+10;
  4 int n,m;
  5 struct edge
  6 {
  7     int u,v,nxt;
  8 }e[maxn<<1];
  9 int head[maxn],js;
 10 void addage(int u,int v)
 11 {
 12     e[++js].u=u;e[js].v=v;
 13     e[js].nxt=head[u];head[u]=js;
 14 }
 15 int w[maxn];
 16 int dep[maxn],fat[maxn],son[maxn],siz[maxn];
 17 void dfs(int u,int fa)
 18 {
 19     dep[u]=dep[fa]+1;
 20     fat[u]=fa;
 21     siz[u]=1;
 22     for(int i=head[u];i;i=e[i].nxt)
 23     {
 24         int v=e[i].v;
 25         if(v==fa)continue;
 26         dfs(v,u);
 27         siz[u]+=siz[v];
 28         if(!son[u] || siz[son[u]]<siz[v])son[u]=v;
 29     }
 30 }
 31 int pos[maxn],fos[maxn],top[maxn],p;
 32 void getpos(int u,int fa)
 33 {
 34     pos[u]=++p;
 35     fos[p]=u;
 36     top[u]=fa;
 37     if(!son[u])return;
 38     getpos(son[u],fa);
 39     for(int i=head[u];i;i=e[i].nxt)
 40     {
 41         int v=e[i].v;
 42         if(v!=fat[u] && v!=son[u])getpos(v,v);
 43     }
 44 }
 45 int sum[maxn<<2],lc[maxn<<2],rc[maxn<<2],delt[maxn<<2];
 46 void update(int cur)
 47 {
 48     lc[cur]=lc[cur<<1];
 49     rc[cur]=rc[cur<<1|1];
 50     sum[cur]=sum[cur<<1]+sum[cur<<1|1]-(rc[cur<<1]==lc[cur<<1|1]);
 51 }
 52 void build(int cur,int l,int r)
 53 {
 54     if(l==r)
 55     {
 56         lc[cur]=rc[cur]=w[fos[l]];
 57         sum[cur]=1;
 58         return;
 59     }
 60     int mid=(l+r)>>1;
 61     build(cur<<1,l,mid);
 62     build(cur<<1|1,mid+1,r);
 63     update(cur);
 64 }
 65 void down(int cur)
 66 {
 67     sum[cur<<1]=sum[cur<<1|1]=1;
 68     delt[cur<<1]=delt[cur<<1|1]=lc[cur<<1]=rc[cur<<1]=lc[cur<<1|1]=rc[cur<<1|1]=delt[cur];
 69     delt[cur]=-1;
 70 }
 71 void modi(int cur,int l,int r,int ql,int qr,int x)
 72 {
 73     if(ql<=l && r<=qr)
 74     {
 75         sum[cur]=1;
 76         delt[cur]=lc[cur]=rc[cur]=x;
 77         return ;
 78     }
 79     int mid=(l+r)>>1;
 80     if(delt[cur]!=-1)down(cur);
 81     if(ql<=mid)modi(cur<<1,l,mid,ql,qr,x);
 82     if(mid<qr)modi(cur<<1|1,mid+1,r,ql,qr,x);
 83     update(cur);
 84 }
 85 void change(int u,int v,int x)
 86 {
 87     int tpu=top[u],tpv=top[v];
 88     while(tpu!=tpv)
 89     {
 90         if(dep[tpu]<dep[tpv])
 91         {
 92             swap(u,v);swap(tpu,tpv);
 93         }
 94         modi(1,1,n,pos[tpu],pos[u],x);
 95         u=fat[tpu];tpu=top[u];
 96     }
 97     if(dep[u]>dep[v])swap(u,v);
 98     modi(1,1,n,pos[u],pos[v],x);
 99 }
100 int query_c(int cur,int l,int r,int p)
101 {
102     if(l==r)return lc[cur];
103     int mid=(l+r)>>1;
104     if(delt[cur]!=-1)down(cur);
105     if(p<=mid)return query_c(cur<<1,l,mid,p);
106     else return query_c(cur<<1|1,mid+1,r,p);
107 }
108 int query(int cur,int l,int r,int ql,int qr)
109 {
110     if(ql<=l && r<=qr)return sum[cur];
111     int mid=(l+r)>>1,ans=0;
112     if(delt[cur]!=-1)down(cur);
113     if(ql<=mid)ans+=query(cur<<1,l,mid,ql,qr);
114     if(qr>mid)ans+=query(cur<<1|1,mid+1,r,ql,qr);
115     if(ql<=mid && mid<qr)ans-=rc[cur<<1]==lc[cur<<1|1];
116     return ans;
117 } 
118 int ask(int u,int v)
119 {
120     int ans=0;
121     int clt,clp;
122     int tpu=top[u],tpv=top[v];
123     while(tpu!=tpv)
124     {
125             if(dep[tpu]<dep[tpv])
126             {
127                 swap(u,v);swap(tpu,tpv);
128             }
129             clt=query_c(1,1,n,pos[tpu]);
130             clp=query_c(1,1,n,pos[fat[tpu]]);
131             ans+=query(1,1,n,pos[tpu],pos[u])-(clt==clp);
132             u=fat[tpu];tpu=top[u];
133     }
134     if(dep[u]>dep[v])swap(u,v);
135     ans+=query(1,1,n,pos[u],pos[v]);
136     return ans;
137 }
138 int main()
139 {
140     scanf("%d%d",&n,&m);
141     for(int i=1;i<=n;++i)scanf("%d",w+i);
142     for(int u,v,i=1;i<n;++i)
143     {
144         scanf("%d%d",&u,&v);
145         addage(u,v);addage(v,u);
146     }
147     dfs(1,0);
148     getpos(1,1);
149     memset(delt,-1,sizeof(delt));
150     build(1,1,n);
151     char s[3];
152     int a,b,c;
153     while(m--)
154     {
155         scanf("%s",s);
156         if(s[0]=='C')
157         {
158             scanf("%d%d%d",&a,&b,&c);
159             change(a,b,c);
160         }
161         else
162         {
163             scanf("%d%d",&a,&b);
164             printf("%d
",ask(a,b));
165         }
166     }
167     return 0;
168 }

View Code