P2486 [SDOI2011]染色

題意：

題解：

與一般的樹鏈剖分相比，不同點在于查詢的不是路徑上顏色的數量而是顏色段的數量
對于兩個顏色段，112和221，兩個顏色段數量都是2
如果合在一起顏色段的數量就是3，因為左邊顏色段的右側和右邊顏色段的左側是一樣的顏色，合在一起后就成一段
所以本題其實就是將常規的區間求和改成這種特殊情況，在求完和的基礎上，對左區間的最后一個顏色和右區間的第一個顏色進行判斷，如果一樣就減一

樹剖中是把兩點之間剖成了若干條鏈，所以我們還要解決不同的鏈之間的顏色重復問題，解決top[a]與fa[top[a]]顏色重復問題即可（如圖）

總結一下：
就是判斷所有接口處顏色是否一樣

代碼：

#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<algorithm> #define lid (id << 1) #define rid (id << 1) | 1 using namespace std; int read(){int out = 0,flag = 1;char c = getchar();while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}return flag * out;} const int maxn = 100019; int num,na,nume,cnt; int head[maxn]; struct Node{int v,nxt; }E[maxn * 2]; void add(int u,int v){E[++nume].nxt = head[u];E[nume].v = v;head[u] = nume;} int size[maxn],wson[maxn],dep[maxn],fa[maxn],top[maxn],pos[maxn],ori[maxn]; int col[maxn]; void dfs1(int id,int F){size[id] = 1;for(int i = head[id];i;i = E[i].nxt){int v = E[i].v;if(v == F)continue;dep[v] = dep[id] + 1;fa[v] = id;dfs1(v,id);size[id] += size[v];if(size[v] > size[wson[id]])wson[id] = v;} } void dfs2(int id,int TP){top[id] = TP;pos[id] = ++cnt;ori[cnt] = id;if(!wson[id])return ;dfs2(wson[id],TP);for(int i = head[id];i;i = E[i].nxt){int v = E[i].v;if(v == fa[id] || v == wson[id])continue;dfs2(v,v);} } int lc[maxn << 2]; int rc[maxn << 2]; struct sag_tree{int l,r;int sum,c;//區間顏色總數，葉子顏色int lazy;//兒子的顏色 }tree[maxn << 2]; void pushup(int id) {tree[id].sum = tree[lid].sum + tree[rid].sum;if(rc[lid] == lc[rid])tree[id].sum -= 1;//如果連接處顏色一樣，減一 lc[id] = lc[lid];rc[id] = rc[rid]; } void build(int id,int l,int r){tree[id].l = l;tree[id].r = r;if(l == r){tree[id].c = col[ori[l]];//賦值：葉子顏色lc[id] = rc[id] = col[ori[l]];//賦值：區間左顏色和區間右顏色tree[id].sum = 1;//顏色數為1return ;}int mid = l + r >> 1;build(lid,l,mid);build(rid,mid + 1,r);pushup(id); } void pushdown(int id){if(tree[id].lazy != 0 && tree[id].l != tree[id].r){int c = tree[id].lazy;tree[lid].lazy = tree[rid].lazy = c;//粉刷tree[lid].c = tree[rid].c = c;lc[lid] = rc[lid] = lc[rid] = rc[rid] = c;//更新左右tree[lid].sum = tree[rid].sum = 1;//粉刷完以后只有一種顏色了tree[id].lazy = 0;} } void update(int id,int c,int l,int r){pushdown(id);if(tree[id].l == l && tree[id].r == r){tree[id].c = c;//更新顏色 tree[id].lazy = c;tree[id].sum = 1;//此時區間內只有一種顏色 lc[id] = rc[id] = c;return ;}int mid = tree[id].l + tree[id].r >> 1;if(mid < l){update(rid,c,l,r);}else if(mid >= r){update(lid,c,l,r);}else{update(lid,c,l,mid);update(rid,c,mid + 1,r);}pushup(id); } int query(int id,int l,int r)//查詢區間顏色數量 {pushdown(id);if(tree[id].l == l && tree[id].r == r){return tree[id].sum;}int mid = tree[id].l + tree[id].r >> 1;if(mid < l){return query(rid,l,r);}else if(mid >= r){return query(lid,l,r);}else{int ret = query(lid,l,mid) + query(rid,mid + 1,r);if(rc[lid] == lc[rid])ret -= 1;//如果連接處顏色一樣 return ret;} } int Qc(int id,int l,int r){//查詢單點的顏色pushdown(id);if(tree[id].l == l && tree[id].r == r){return tree[id].c;}int mid = tree[id].l + tree[id].r >> 1;if(mid < l)return Qc(rid,l,r);else return Qc(lid,l,r); } void uprange(int x,int y,int c){while(top[x] != top[y]){if(dep[top[x]] < dep[top[y]])swap(x,y);update(1,c,pos[top[x]],pos[x]);x = fa[top[x]];}if(dep[x] > dep[y])swap(x,y);update(1,c,pos[x],pos[y]); } int Qsum(int x,int y){int ans = 0,Cson,Cfa;//兒子的顏色，爸爸的顏色while(top[x] != top[y]){if(dep[top[x]] < dep[top[y]])swap(x,y);ans += query(1,pos[top[x]],pos[x]);Cson = Qc(1,pos[top[x]],pos[top[x]]);Cfa = Qc(1,pos[fa[top[x]]],pos[fa[top[x]]]);if(Cson == Cfa)ans -= 1;x = fa[top[x]];}if(dep[x] > dep[y])swap(x,y);ans += query(1,pos[x],pos[y]);return ans; } int main(){num = read();na = read();for(int i = 1;i <= num;i++)col[i] = read();int u,v;for(int i = 1;i <= num - 1;i++){u = read();v = read();add(u,v);add(v,u);}dfs1(1,-1);dfs2(1,1);build(1,1,num);char ask;int c;for(int i = 1;i <= na;i++){cin>>ask;if(ask == 'Q'){u = read();v = read();printf("%d\n",Qsum(u,v));}else{u = read();v = read();c = read();uprange(u,v,c);}}return 0;}

總結

以上是生活随笔為你收集整理的P2486 [SDOI2011]染色的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。