P2486 [SDOI2011]染色

题目链接：https://www.luogu.org/problem/P2486

思路：

首先我们看到颜色的个数，然后又是一个树上的操作很自然而然的就会想到树链剖分

但是会遇到一个问题，那就是题目并不是直接给你染色颜色的个数的，所以我们先要预处理得到颜色个数

首先我们分情况进行讨论：

第一种情况：左区间是 1234 （颜色个数4）右区间是 222 （颜色个数1）

合并后： 1234222 （颜色个数5 = 4 + 1）

没有出现重复

第二种情况：左区间是 1231 （颜色个数3）右区间是 121 （颜色个数2）

合并后 1231121 （颜色个数4 = 3 + 2 -1）

左区间的第一个元素和右区间的第一个元素一样，这就会出现重复

我们用 lc[] 和 rc[] 分别代表左区间的颜色和右区间的颜色

也就是当 左区间的最后一个元素和右区间的第一个元素一样，那么就重复了

push_up 的操作

叶子结点的左区间的颜色和右区间的颜色是一样的，从叶子结点开始往上回溯

tree[nod].lc = tree[nod<<1].lc

tree[nod].rc = tree[(nod<<1)+1].rc

对于颜色个数的操作就是普通的线段树的操作

至于剖分查询的话：

这张图已经非常的清楚了

  1 #include <stdio.h>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <string>
  5 #include <algorithm>
  6 #include <queue>
  7 #include <vector>
  8 #include <math.h>
  9 #include <map>
 10 
 11 #define LL long long
 12 #define INF 0x3f3f3f3f
 13 using namespace std;
 14 const int maxn = 2e5 + 10;
 15 
 16 struct Edge{
 17     int to,next;
 18 }edge[maxn*2];
 19 
 20 int tot,head[maxn];
 21 
 22 void add_edge(int u,int v){
 23     edge[++tot] = Edge{v,head[u]};
 24     head[u] = tot;
 25 }
 26 
 27 int fa[maxn];
 28 int dep[maxn];
 29 int siz[maxn];
 30 int son[maxn];
 31 
 32 void dfs1(int u,int f){
 33     fa[u] = f;
 34     dep[u] = dep[f] + 1;
 35     siz[u] = 1;
 36     int maxsize = -1;
 37     for (int i=head[u];~i;i=edge[i].next){
 38         int v = edge[i].to;
 39         if (v == f)
 40             continue;
 41         dfs1(v,u);
 42         siz[u] += siz[v];
 43         if (siz[v] > maxsize){
 44             son[u] = v;
 45             maxsize = siz[v];
 46         }
 47     }
 48 }
 49 
 50 int tim;
 51 int dfn[maxn];
 52 int w[maxn];
 53 int v[maxn];
 54 int top[maxn];
 55 
 56 void dfs2(int u,int t){
 57     dfn[u] = ++tim;
 58     top[u] = t;
 59     w[tim] = v[u];
 60     if (!son[u])
 61         return ;
 62     dfs2(son[u],t);
 63     for (int i=head[u];~i;i=edge[i].next){
 64         int v = edge[i].to;
 65         if (v == fa[u] || v == son[u])
 66             continue;
 67         dfs2(v,v);
 68     }
 69 }
 70 
 71 struct segment_tree{
 72     int l,r;
 73     int sum,c;
 74     int lazy;
 75     int lc,rc;
 76 }tree[maxn*4];
 77 
 78 void pushdown(int nod){
 79     if (tree[nod].lazy != 0 ){
 80         tree[nod<<1].lazy = tree[(nod<<1)+1].lazy = tree[nod].lazy;
 81         tree[nod<<1].c = tree[(nod<<1)+1].c = tree[nod].lazy;
 82         tree[nod<<1].lc = tree[nod<<1].rc = tree[(nod<<1)+1].lc = tree[(nod<<1)+1].rc = tree[nod].lazy;
 83         tree[nod<<1].sum = tree[(nod<<1)+1].sum = 1;
 84         tree[nod].lazy = 0;
 85     }
 86 }
 87 
 88 void build(int l,int r,int nod){
 89     tree[nod].l = l;
 90     tree[nod].r = r;
 91     if (l == r){
 92         tree[nod].c = w[l];
 93         tree[nod].lc = tree[nod].rc = w[l];
 94         tree[nod].sum = 1;
 95         return ;
 96     }
 97     int mid = (l + r) >> 1;
 98     build(l,mid,nod<<1);
 99     build(mid+1,r,(nod<<1)+1);
100     tree[nod].sum = (tree[nod<<1].sum + tree[(nod<<1)+1].sum);
101     if (tree[nod<<1].rc == tree[(nod<<1)+1].lc ){
102         tree[nod].sum -= 1;
103     }
104     tree[nod].lc = tree[nod<<1].lc;
105     tree[nod].rc = tree[(nod<<1)+1].rc;
106 }
107 
108 void update(int x,int y,int c,int nod=1){
109     int l = tree[nod].l,r = tree[nod].r;
110     if (x <= l && y >= r){
111         tree[nod].c = c;
112         tree[nod].lazy = c;
113         tree[nod].sum = 1;
114         tree[nod].lc = tree[nod].rc = c;
115         return ;
116     }
117     pushdown(nod);
118     int mid = (l + r) >> 1;
119     if (x <= mid){
120         update(x,y,c,nod<<1);
121     }
122     if (y > mid){
123         update(x,y,c,(nod<<1)+1);
124     }
125     tree[nod].sum = (tree[nod<<1].sum + tree[(nod<<1)+1].sum);
126     if (tree[nod<<1].rc == tree[(nod<<1)+1].lc ){
127         tree[nod].sum -= 1;
128     }
129     tree[nod].lc = tree[nod<<1].lc;
130     tree[nod].rc = tree[(nod<<1)+1].rc;
131 }
132 
133 int query(int x,int y,int nod=1){
134     int l = tree[nod].l,r = tree[nod].r;
135     if (x <= l && y >= r){
136         return tree[nod].sum;
137     }
138     pushdown(nod);
139     int ret = 0;
140     int mid = (l + r) >> 1;
141     if (x <= mid){
142         ret += query(x,y,nod<<1);
143     }
144     if (y > mid){
145         ret += query(x,y,(nod<<1)+1);
146         if (x <= mid && tree[nod<<1].rc == tree[(nod<<1)+1].lc ){
147             ret -= 1;
148         }
149     }
150     return ret;
151 }
152 
153 int Qc(int x,int y,int nod=1){
154     int l = tree[nod].l,r = tree[nod].r;
155     if (x <= l && y >= r){
156         return tree[nod].c;
157     }
158     pushdown(nod);
159     int mid = (l + r) >> 1;
160     if (x <= mid){
161         return Qc(x,y,nod<<1);
162     }
163     if (y > mid)
164         return Qc(x,y,(nod<<1)+1);
165 }
166 
167 void uprange(int x,int y,int c){
168     while (top[x] != top[y]){
169         if (dep[top[x]] < dep[top[y]])
170             swap(x,y);
171         update(dfn[top[x]],dfn[x],c);
172         x = fa[top[x]];
173     }
174     if (dep[x] > dep[y])
175         swap(x,y);
176     update(dfn[x],dfn[y],c);
177 }
178 
179 int Qsum(int x,int y){
180     int ans = 0,Cson,Cfa;
181     while (top[x] != top[y]){
182         if (dep[top[x]] < dep[top[y]])
183             swap(x,y);
184         ans += query(dfn[top[x]],dfn[x]);
185         Cfa = Qc(dfn[fa[top[x]]],dfn[fa[top[x]]]);
186         Cson = Qc(dfn[top[x]],dfn[top[x]]);
187         if (Cson == Cfa)
188             ans -= 1;
189         x = fa[top[x]];
190     }
191     if (dep[x] > dep[y])
192         swap(x,y);
193     ans += query(dfn[x],dfn[y]);
194     return ans;
195 }
196 
197 
198 
199 int main(){
200     int n,m;
201     scanf("%d%d",&n,&m);
202     memset(head,-1, sizeof(head));
203     for (int i=1;i<=n;i++){
204         scanf("%d",&v[i]);
205     }
206     for (int i=1;i<=n-1;i++){
207         int x,y;
208         scanf("%d%d",&x,&y);
209         add_edge(x,y);
210         add_edge(y,x);
211     }
212     dfs1(1,0);
213     dfs2(1,1);
214     build(1,n,1);
215     while (m--){
216         char op[4];
217         scanf("%s",op);
218         if (op[0] == 'Q'){
219             int x,y;
220             scanf("%d%d",&x,&y);
221             printf("%d\n",Qsum(x,y));
222         }
223         else {
224             int x,y,z;
225             scanf("%d%d%d",&x,&y,&z);
226             uprange(x,y,z);
227         }
228     }
229     return 0;
230 }

附上dalao的博客：https://www.cnblogs.com/Tony-Double-Sky/p/9283262.html