题解 P2486 【[SDOI2011]染色】
SuperJvRuo
2018-10-14 15:04:38
这是一篇树剖+[珂朵莉树](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;
}
```