文章目錄

• 題目描述
• 解析
• 代碼
• thanks for reading！

傳送門

首先，對hash學姐對本題拔刀相助的debug行為表示衷心的感謝

題目描述

解析

用線段樹維護顏色序列個數、最左顏色與最右顏色
合并時如果左兒子的最右顏色等于右兒子的最左顏色，就把加和-1
在加上樹剖的基本操作即可
幾點注意事項：

1.從重鏈頭往父親跳的時候要判斷一下，如果鏈頭與父親同色，需要減一
2.線段樹區間查詢合并答案也要注意兩邊如果顏色相同要減一！（我就因為這個調了一個多點。。。）

代碼

#include<bits/stdc++.h> using namespace std; const int N=4e5+100; #define ll long long #define ls k<<1 #define rs k<<1|1 int fa[N],dep[N],size[N]; int dfs[N],pos[N],tot; int top[N],hson[N]; ll b[N],a[N]; ll add[4*N],col[4*N],le[4*N],ri[4*N]; int n,m,root;struct node{int to,nxt; }p[N*2]; int fi[N],cnt=-1; void addline(int x,int y){p[++cnt]=(node){y,fi[x]};fi[x]=cnt; }void merge(int k){le[k]=le[ls];ri[k]=ri[rs];col[k]=col[ls]+col[rs];if(ri[ls]==le[rs]&&col[k]>1) col[k]--; } void Add(int k,int l,int r,int v){add[k] = v;ri[k]=le[k]=v;col[k] = 1; } void pushdown(int k,int l,int r,int mid){if(add[k]==-1) return;Add(2*k,l,mid,add[k]);Add(2*k+1,mid+1,r,add[k]);add[k] = -1; } long long longquery(int k,int l,int r,int x,int y){if(x<=l&&r<=y) return col[k];int mid=(l+r) >> 1;pushdown(k,l,r,mid);long long res=0;if(x<=mid) res += longquery(2*k,l,mid,x,y);if(y>mid) res += longquery(2*k+1,mid+1,r,x,y);if(x<=mid&&y>=mid+1&&ri[ls]==le[rs]) res--;merge(k);return res; } void longchange(int k,int l,int r,int x,int y,int v){if(x<=l&&r<=y){Add(k,l,r,v);return;}int mid = (l+r) >> 1;pushdown(k,l,r,mid);if(x<=mid) longchange(2*k,l,mid,x,y,v);if(y>mid) longchange(2*k+1,mid+1,r,x,y,v);merge(k);return; } void build(int k,int l,int r){if(l==r){col[k]=1;ri[k]=le[k]=a[l]; // printf("pl=%d le=%d\n",l,a[l]);return;}int mid=(l+r)/2;build(2*k,l,mid);build(2*k+1,mid+1,r);merge(k);return; } int dotask(int k,int l,int r,int x){if(l==r){return ri[k];}int mid=l+r>>1;pushdown(k,l,r,mid);if(x<=mid) return dotask(ls,l,mid,x);else return dotask(rs,mid+1,r,x);merge(k); }void dfs1(int x,int f){size[x]=1;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==f) continue;dep[to]=dep[x]+1;fa[to]=x;dfs1(to,x);size[x]+=size[to];if(!hson[x]||size[to]>size[hson[x]]) hson[x]=to;}return; } void dfs2(int x,int tp){top[x]=tp;dfs[++tot]=x;pos[x]=tot;a[tot]=b[x];if(!hson[x]) return;dfs2(hson[x],tp);for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==fa[x]) continue;if(to==hson[x]) continue;else dfs2(to,to);}return; }void roadchange(int x,int y,int v){while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);longchange(1,1,tot,pos[top[x]],pos[x],v);x=fa[top[x]];}if(dep[x]<dep[y]) swap(x,y);longchange(1,1,tot,pos[y],pos[x],v);return; } ll roadask(int x,int y){ll ans=0;while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);ans+=longquery(1,1,tot,pos[top[x]],pos[x]); // printf("+=%d %d\n",pos[top[x]],pos[x]); // printf("x=%d top=%d fa=%d\n",x,top[x],fa[top[x]]); // printf("col1=%d col2=%d\n",dotask(1,1,tot,pos[top[x]]),dotask(1,1,tot,pos[fa[top[x]]]));if(dotask(1,1,tot,pos[top[x]])==dotask(1,1,tot,pos[fa[top[x]]])) ans--;x=fa[top[x]];}if(dep[x]<dep[y]) swap(x,y);ans+=longquery(1,1,tot,pos[y],pos[x]); // printf("+=%d %d\n",pos[y],pos[x]);return ans; }void print_dfs(){for(int i=1;i<=tot;i++) printf("i=%d pos=%d size=%d hson=%d top=%d\n",i,pos[i],size[i],hson[i],top[i]); }int main(){memset(fi,-1,sizeof(fi));memset(add,-1,sizeof(add));scanf("%d%d",&n,&m);int u,v,w;for(int i=1;i<=n;i++) scanf("%lld",&b[i]);for(int i=1;i<n;i++){scanf("%d%d",&u,&v);addline(u,v);addline(v,u);}dfs1(1,0);dfs2(1,1);build(1,1,tot); // print_dfs();for(int i=1;i<=m;i++){char flag;scanf(" %c ",&flag);if(flag=='C'){scanf("%d%d%d",&u,&v,&w);roadchange(u,v,w);} // else if(flag=='a'){ // scanf("%d",&u); // printf("%d\n",dotask(1,1,tot,pos[u])); // }else{scanf("%d%d",&u,&v);printf("%lld\n",roadask(u,v));}} } /* 6 155 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*/

thanks for reading！

總結

以上是生活随笔為你收集整理的染色（树链剖分 洛谷-P2486）的全部內容，希望文章能夠幫你解決所遇到的問題。

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