题解 P2486 【[SDOI2011]染色】

SuperJvRuo

2018-10-14 15:04:38

Solution

这是一篇树剖+[珂朵莉树](https://www.luogu.org/blog/ACdreamer/chtholly-tree)的题解。 首先显然是要树剖了。此题大约有一半的操作为珂朵莉树的区间赋值,可以考虑珂朵莉树骗分。(然后一不小心就A了)另一部分的操作也很好搞。 具体实现看代码: ``` #include<cctype> #include<cstdio> #include<set> #include<algorithm> inline int Read() { int x=0;char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+(c^48); c=getchar(); } return x; } const int maxn=200000+10; int n,m; int son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],size[maxn],top[maxn],w[maxn],wt[maxn]; struct Edge { int to,next; }edge[maxn]; int head[maxn],ecnt; void Add_edge(int u,int v) { edge[++ecnt]=(Edge){v,head[u]}; head[u]=ecnt; edge[++ecnt]=(Edge){u,head[v]}; head[v]=ecnt; } struct node { int l,r; mutable int v; node(int L,int R=-1,int V=0):l(L),r(R),v(V){} bool operator<(const node& o) const { return l < o.l; } }; //这样的一个节点表示[l,r]内的所有数都是v。 typedef node Ret; Ret operator + (Ret l,Ret r) { return Ret(l.l?l.l:r.l,r.r?r.r:l.r,l.v+r.v-(l.r==r.l)); } //这样的一个Ret表示左边颜色为l,右边颜色为r,共有v段颜色。 using std::set; set<node> s; #define IT set<node>::iterator //split(pos)操作是指将原来含有pos位置的节点分成两部分:[l,pos−1]和[pos,r]。 IT split(int pos) { IT it=s.lower_bound(node(pos)); if(it!=s.end()&&it->l==pos) return it; --it; int L=it->l,R=it->r,V=it->v; s.erase(it); s.insert(node(L,pos-1,V)); return s.insert(node(pos,R,V)).first; } //区间赋值,把l和r+1进行split,再把[l,r]合成一个节点。 void assign(int l,int r,int val=0) { IT itr=split(r+1),itl=split(l); s.erase(itl,itr); s.insert(node(l,r,val)); } void build(int l,int r) { int cnt=1,last=wt[l]; for(int i=l+1;i<=r;++i) { if(wt[i]!=last) { s.insert(node(i-cnt,i-1,last)); cnt=1; last=wt[i]; } else { ++cnt; } } s.insert(node(r+1-cnt,r,last)); s.insert(node(r+1,r+3,0)); } Ret query(int l,int r) { Ret ans=Ret(0); IT itr=split(r+1),itl=split(l); for(;itl!=itr;++itl) { ans=ans+Ret(itl->v,itl->v,1); } return ans; } int qRange(int x,int y) { Ret lans=Ret(0),rans=Ret(0); //lans表示x一侧的结果,rans表示y一侧的结果 while(top[x]!=top[y]) { if(dep[top[x]]>dep[top[y]]) { lans=query(id[top[x]],id[x])+lans; x=fa[top[x]]; } else { rans=query(id[top[y]],id[y])+rans; y=fa[top[y]]; } } if(dep[x]>dep[y]) { lans=query(id[y],id[x])+lans; } else { rans=query(id[x],id[y])+rans; } std::swap(lans.l,lans.r); return (lans+rans).v; } void updRange(int x,int y,int k) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) std::swap(x,y); assign(id[top[x]],id[x],k); x=fa[top[x]]; } if(dep[x]>dep[y]) std::swap(x,y); assign(id[x],id[y],k); } //树剖基操 void dfs1(int x,int f,int deep) { dep[x]=deep; fa[x]=f; size[x]=1; int maxson=-1; for(int i=head[x];i;i=edge[i].next) { int v=edge[i].to; if(v==f) continue; dfs1(v,x,deep+1); size[x]+=size[v]; if(size[v]>maxson) { son[x]=v; maxson=size[v]; } } } void dfs2(int x,int topf) { id[x]=++cnt; wt[cnt]=w[x]; top[x]=topf; if(!son[x]) return; dfs2(son[x],topf); for(int i=head[x];i;i=edge[i].next) { int v=edge[i].to; if(v!=fa[x]&&v!=son[x]) dfs2(v,v); } } int main() { n=Read(),m=Read(); for(int i=1;i<=n;i++) w[i]=Read(); for(int i=1;i<n;i++) { int a=Read(),b=Read(); Add_edge(a,b); } dfs1(1,0,1); dfs2(1,1); build(1,n); char opt[5]; while(m--) { int x,y,z; scanf("%s",opt); if(opt[0]=='C') { x=Read(),y=Read(),z=Read(); updRange(x,y,z); } else { x=Read(),y=Read(); printf("%d\n",qRange(x,y)); } } return 0; } ```