P2486 [SDOI2011]染色

https://www.luogu.com.cn/problem/P2486

题意:求出一段路径的颜色段数量;

很明显路径通常通过树剖来解决;

我们在树剖之后,查询两点之间颜色段的数量的时候,对于不同的两个区间,我们先将答案都加起来,

然后假如这两点区间的连接处颜色相同,我们再将答案减1;

那么什么时候会有连接点呢;

我们已经将树剖分为一条条的链,当我们查找完一条链,即将查询下一条链的时候,这个时候就有连接点;

我们在这个地方进行判断即可;

代码如下:

  1 #include<algorithm>
  2 #include<iostream>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<cstdio>
  6 #define Rint register int
  7 #define mem(a,b) memset(a,(b),sizeof(a))
  8 #define Temp template<typename T>
  9 using namespace std;
 10 typedef long long LL;
 11 const int maxn=200000+10;
 12 int n,m,r;
 13 //见题意
 14 int w[maxn],wt[maxn];
 15 //链式前向星数组,w[]、wt[]初始点权数组
 16 int son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],siz[maxn],top[maxn];
 17 //son[]重儿子编号,id[]新编号,fa[]父亲节点,cnt dfs_clock/dfs序,dep[]深度,siz[]子树大小,top[]当前链顶端节点
 18 //查询答案
 19 struct node
 20 {
 21     int v,nxt;
 22 }G[maxn<<2]; int head[maxn]; int num;
 23 struct tre
 24 {
 25     int l,r,lazy,sum;
 26     int jl,jr;
 27 }tree[maxn<<2];
 28 void add(int u,int v)
 29 {
 30     G[++num].v=v;G[num].nxt=head[u];head[u]=num;
 31     G[++num].v=u;G[num].nxt=head[v];head[v]=num;
 32 }
 33 void pushdown(int rt,int lenn){
 34     tree[rt<<1].lazy=tree[rt].lazy;
 35     tree[rt<<1|1].lazy=tree[rt].lazy;
 36     tree[rt<<1].sum=1;
 37     tree[rt<<1|1].sum=1;
 38     tree[rt<<1].jl=tree[rt<<1].jr=tree[rt].lazy;
 39     tree[rt<<1|1].jl=tree[rt<<1|1].jr=tree[rt].lazy;
 40     tree[rt].lazy=0;
 41 }
 42 
 43 void build(int l,int r,int root){
 44     tree[root].l=l;tree[root].r=r;
 45     tree[root].sum=tree[root].lazy=0;
 46     if(l==r){
 47         tree[root].sum=1;
 48         tree[root].jl=tree[root].jr=wt[l];
 49         return;
 50     }
 51     int mid=l+r>>1;
 52     build(l,mid,root<<1);
 53     build(mid+1,r,root<<1|1);
 54     tree[root].sum=tree[root<<1].sum+tree[root<<1|1].sum;
 55     if(tree[root<<1].jr==tree[root<<1|1].jl) tree[root].sum--;
 56     tree[root].jl=tree[root<<1].jl;
 57     tree[root].jr=tree[root<<1|1].jr;
 58 }
 59 
 60 tre query(int l,int r,int root){
 61     int L=tree[root].l;int R=tree[root].r;
 62     if(l<=L&&R<=r){
 63         return tree[root];
 64     }
 65     if(tree[root].lazy) pushdown(root,R-L+1);
 66     int mid=L+R>>1;
 67     tre ans;
 68     int flag=0;
 69     if(l<=mid) ans=query(l,r,root<<1),flag=1;
 70     if(r>mid){
 71         if(!flag) ans=query(l,r,root<<1|1);
 72         else{
 73             tre tmp;
 74             tmp=query(l,r,root<<1|1);
 75             ans.sum+=tmp.sum;
 76             if(ans.jr==tmp.jl) ans.sum--;
 77             ans.jr=tmp.jr;
 78         }
 79     }
 80     return ans;
 81 }
 82 void update(int l,int r,int val,int root){
 83     int L=tree[root].l;int R=tree[root].r;
 84     if(l<=L&&R<=r){
 85         tree[root].lazy=val;
 86         tree[root].sum=1;
 87         tree[root].jl=tree[root].jr=val;
 88     }
 89     else{
 90         if(tree[root].lazy)pushdown(root,R-L+1);
 91         int mid=L+R>>1;
 92         if(l<=mid)update(l,r,val,root<<1);
 93         if(r>mid) update(l,r,val,root<<1|1);
 94         tree[root].sum=tree[root<<1].sum+tree[root<<1|1].sum;
 95         if(tree[root<<1].jr==tree[root<<1|1].jl) tree[root].sum--;
 96         tree[root].jl=tree[root<<1].jl;
 97         tree[root].jr=tree[root<<1|1].jr;
 98     }
 99 }
100 tre qRange(int x,int y){
101     tre ans,tmp;
102     tre t1,t2;
103     int flag=0;
104     while(top[x]!=top[y]){//当两个点不在同一条链上
105         if(dep[top[x]]<dep[top[y]])swap(x,y);//把x点改为所在链顶端的深度更深的那个点
106         if(!flag)
107             ans=query(id[top[x]],id[x],1),flag=1;//ans加上x点到x所在链顶端 这一段区间的点权和
108         else tmp=query(id[top[x]],id[x],1),ans.sum+=tmp.sum;
109         t1=query(id[top[x]],id[top[x]],1);
110         t2=query(id[fa[top[x]]],id[fa[top[x]]],1);
111         if(t1.jl==t2.jl) ans.sum--;
112         x=fa[top[x]];//把x跳到x所在链顶端的那个点的上面一个点
113     }
114     //直到两个点处于一条链上
115     if(dep[x]>dep[y])swap(x,y); //把x点深度更深的那个点
116     tmp=query(id[x],id[y],1); //这时再加上此时两个点的区间和即可
117     if(!flag) return tmp;
118     ans.sum+=tmp.sum;
119     return ans;
120 }
121 void updRange(int x,int y,int k){//同上
122     while(top[x]!=top[y]){
123         if(dep[top[x]]<dep[top[y]])swap(x,y);
124         update(id[top[x]],id[x],k,1);
125         x=fa[top[x]];
126     }
127     if(dep[x]>dep[y])swap(x,y);
128     update(id[x],id[y],k,1);
129 }
130 
131 void dfs1(int u,int f,int deep){//x当前节点,f父亲,deep深度
132     dep[u]=deep;//标记每个点的深度
133     fa[u]=f;//标记每个点的父亲
134     siz[u]=1;//标记每个非叶子节点的子树大小
135     int maxson=-1;//记录重儿子的儿子数
136     for(int i=head[u];i!=-1;i=G[i].nxt){
137         int v=G[i].v;
138         if(v==f)continue;//若为父亲则continue
139         dfs1(v,u,deep+1);//dfs其儿子
140         siz[u]+=siz[v];//把它的儿子数加到它身上
141         if(siz[v]>maxson)son[u]=v,maxson=siz[v];//标记每个非叶子节点的重儿子编号
142     }
143 }
144 
145 void dfs2(int u,int topf){//x当前节点,topf当前链的最顶端的节点
146     id[u]=++cnt;//标记每个点的新编号
147     wt[cnt]=w[u];//把每个点的初始值赋到新编号上来
148     top[u]=topf;//这个点所在链的顶端
149     if(!son[u])return;//如果没有儿子则返回
150     dfs2(son[u],topf);//按先处理重儿子,再处理轻儿子的顺序递归处理
151     for(int i=head[u];i!=-1;i=G[i].nxt){
152         int v=G[i].v;
153         if(v==fa[u]||v==son[u])continue;
154         dfs2(v,v);//对于每一个轻儿子都有一条从它自己开始的链
155     }
156 }
157 void init()
158 {
159     memset(head,-1,sizeof(head));
160     num=-1;
161 }
162 int main(){
163     init();
164     int n,m;
165     scanf("%d%d",&n,&m);
166     for(int i=1;i<=n;i++){
167         scanf("%d",&w[i]);
168     }
169     for(int i=1;i<n;i++){
170         int u,v;
171         scanf("%d%d",&u,&v);
172         add(u,v);
173     }
174     dfs1(1,0,1);
175     dfs2(1,1);
176     build(1,n,1);
177     while(m--){
178         char tmp;
179         cin>>tmp;
180         if(tmp=='C'){
181             int u,v,w;
182             scanf("%d%d%d",&u,&v,&w);
183             updRange(u,v,w);
184         }
185         else{
186             int u,v;
187             scanf("%d%d",&u,&v);
188             tre ans=qRange(u,v);
189             printf("%d\n",ans.sum);
190         }
191     }
192     return 0;
193 }

 

上一篇:【数据结构】Venice技巧


下一篇:AT3611-Tree MST【点分治,最小生成树】