Luogu P2486 [SDOI2011]染色

迈不过友情╰ 2021-10-24 01:10 305阅读 0赞

[P2486 \[SDOI2011\]染色][P2486 _SDOI2011]

卡了我五天的题目。。是一道树剖

一直RE查出来是无限递归，\\(cur\\)下标爆炸了。。

于是发现自己写的判断是边界重合。然后慌的改成了包含区间。我好菜啊。

其实就是用线段树维护区间的左右边界颜色，上传的时候合并ans就好了。如果\\(leftson\_\{rightcolor\}==rightson\_\{leftcolor\}\\)就\\(cur\_\{ans\}--\\)。

（什么sb题。。我为什么卡了五天）

#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #define MAXN 233333 using namespace std; int n,m,tot=0,cnt=0; int w1[MAXN]; struct qwq { int nex,to; }e[MAXN<<1]; int dep[MAXN],son[MAXN],fa[MAXN],siz[MAXN],top[MAXN]; int id[MAXN],h[MAXN]; inline void add(int x,int y) { e[++tot].to=y; e[tot].nex=h[x]; h[x]=tot; } inline void dfs_fir(int x,int f,int dept) { dep[x]=dept; fa[x]=f; siz[x]=1; int maxn=-1; for (int i=h[x],y;i;i=e[i].nex) { y=e[i].to; if (y==f) continue; dfs_fir(y,x,dept+1); siz[x]+=siz[y]; if (siz[y]>maxn) { son[x]=y; maxn=siz[y]; } } } inline void dfs_sec(int x,int ft) { id[x]=++cnt;; top[x]=ft; if (!son[x]) return; dfs_sec(son[x],ft); for (int i=h[x],y;i;i=e[i].nex) { y=e[i].to; if (y==fa[x]||y==son[x]) continue; dfs_sec(y,y); } } //segment_tree struct qq { int ans,tag,cl,cr; }f[MAXN<<2]; #define leftson cur<<1 #define rightson cur<<1|1 #define mid ((l+r)>>1) #define push_down pd(cur) #define push_up pu(cur) inline void pd(int cur) { if (!f[cur].tag) return; f[leftson].ans=f[rightson].ans=1; f[leftson].tag=f[rightson].tag=f[cur].tag; f[leftson].cl=f[leftson].cr=f[cur].cl; f[rightson].cl=f[rightson].cr=f[cur].cl; f[cur].tag=0; } void pu(int cur) { f[cur].cr=f[rightson].cr; f[cur].ans=f[leftson].ans+f[rightson].ans; if (f[leftson].cr==f[rightson].cl) { f[cur].ans--; } } void change(int adl,int adr,int cur,int l,int r,int del) { if (adl<=l&&r<=adr) { f[cur].ans=f[cur].tag=1; f[cur].cl=f[cur].cr=del; return; } push_down; if (adr<=mid) change(adl,adr,leftson,l,mid,del); else if (adl>mid) change(adl,adr,rightson,mid+1,r,del); else { change(adl,adr,leftson,l,mid,del); change(adl,adr,rightson,mid+1,r,del); } push_up; } int bookl,bookr; int query(int cur,int l,int r,int al,int ar,int bl,int br) { if (l==bl) bookl=f[cur].cl; if (r==br) bookr=f[cur].cr; if (al<=l&&r<=ar) { return f[cur].ans; } push_down; if (ar<=mid) return /*printf("qmq........1:::%d %d %d %d %d %d %d\n",leftson,l,mid,al,ar,bl,br),*/query(leftson,l,mid,al,ar,bl,br); else if (al>mid) return /*printf("qmq........2\n"),*/query(rightson,mid+1,r,al,ar,bl,br); else { int sum=query(leftson,l,mid,al,mid,bl,br)+query(rightson,mid+1,r,mid+1,ar,bl,br); if (f[leftson].cr==f[rightson].cl) sum--; return sum; } push_up; } //seg_tree.end void upd(int x,int y,int del) { while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y); change(id[top[x]],id[x],1,1,n,del); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x,y); change(id[x],id[y],1,1,n,del); } int Query(int x,int y) { int ans=0; int s1=-1,s2=-1; while (top[x]!=top[y]) { if (dep[top[x]]<dep[top[y]]) swap(x,y),swap(s1,s2); ans+=query(1,1,n,id[top[x]],id[x],id[top[x]],id[x]); if (bookr==s1) ans--; s1=bookl; x=fa[top[x]]; } if (dep[x]<dep[y]) swap(x,y),swap(s1,s2); ans+=query(1,1,n,id[y],id[x],id[y],id[x]); if (bookl==s2) ans--; if (bookr==s1) ans--; return ans; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { scanf("%d",&w1[i]); } int x,y; for (int i=1;i<n;i++) { scanf("%d%d",&x,&y); add(x,y); add(y,x); } dfs_fir(1,1,1); dfs_sec(1,1); for (int i=1;i<=n;i++) { change(id[i],id[i],1,1,n,w1[i]); } char c; int qwq,qvq,qxq; while (m--) { cin>>c; if (c=='C') { scanf("%d%d%d",&qwq,&qvq,&qxq); upd(qwq,qvq,qxq); continue; } scanf("%d%d",&qwq,&qvq); printf("%d\n",Query(qwq,qvq)); } return 0; }

转载于:https://www.cnblogs.com/Kan-kiz/p/10980688.html

[P2486 _SDOI2011]: https://www.luogu.org/problemnew/show/P2486