题解 P2486 【[SDOI2011]染色】
teafrogsf
2018-04-13 10:48:55
这题目我去年看的时候想用LCT，然后没写出来。
再次看这道题怒来一发树剖。
参考初学线段树时统计颜色的某道题，将区间左右端点颜色记录，上推时如果边界颜色相同就让个数-1。
**注意每个地方都要下推。统计答案时注意边界颜色相同也要减1。查询跳链时注意与父亲颜色相同也要减1。**此外我的线段树貌似跟其他人的写法有些不同？
P.S. $\rm namespace$大法非常好，调代码利器。~~就是容易让代码变长~~
```cpp
#include<bits/stdc++.h>
#define neko 200010
#define meko 200010
#define chkmin(a,b) ((a)<(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
#define travel(i,u,v) for(register int i=head[u],v=e[i].v;i;i=e[i].next,v=e[i].v)
int n,m,t,Root;
typedef int arr[neko];
arr head,dep,siz,fa,son,w,ord,top,col;
int Sum[neko<<2],Led[neko<<2],Red[neko<<2],Pnt[neko<<2];
struct node
{
int v,next;
}e[meko<<1];
void add(int x,int y)
{
e[++t].v=y;
e[t].next=head[x];
head[x]=t;
}
namespace Seg_Tree
{
#define mid ((l+r)>>1)
#define ori tagl,tagr
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
void pushup(int root)
{
Sum[root]=Sum[root<<1]+Sum[root<<1|1];
if(Red[root<<1]==Led[root<<1|1])--Sum[root];
Led[root]=Led[root<<1],Red[root]=Red[root<<1|1];
}
void pushdown(int root)
{
if(Pnt[root])
{
Sum[root<<1]=Sum[root<<1|1]=1;
Led[root<<1]=Led[root<<1|1]=Red[root<<1]=Red[root<<1|1]=Pnt[root];
Pnt[root<<1]=Pnt[root<<1|1]=Pnt[root];
Pnt[root]=0;
}
}
void build(int root,int l,int r)
{
if(l==r){Led[root]=Red[root]=col[ord[l]],Sum[root]=1;return;}
build(lson);
build(rson);
pushup(root);
}
void update(int root,int l,int r,int tagl,int tagr,int x)
{
if(l>=tagl&&r<=tagr){Pnt[root]=x,Led[root]=Red[root]=x,Sum[root]=1;return;}
pushdown(root);
if(tagl<=mid)update(lson,ori,x);
if(tagr>mid)update(rson,ori,x);
pushup(root);
}
int query(int root,int l,int r,int tagl,int tagr)
{
if(l>=tagl&&r<=tagr)return Sum[root];
pushdown(root);
int tmp=0;
if(tagl<=mid)tmp+=query(lson,ori);
if(tagr>mid)tmp+=query(rson,ori);
if(tagl<=mid&&tagr>mid&&Red[root<<1]==Led[root<<1|1])--tmp;
return tmp;
}
int confirm(int root,int l,int r,int tag)
{
if(l==r)return Led[root];
pushdown(root);
if(tag<=mid)return confirm(lson,tag);
else return confirm(rson,tag);
}
}
namespace Siz_Subdivision
{
using namespace std;
using namespace Seg_Tree;
int cnt;
void dfs(int u)
{
dep[u]=dep[fa[u]]+1;
siz[u]=1;
travel(i,u,v)
{
if(v!=fa[u])
{
fa[v]=u;
dfs(v);
siz[u]+=siz[v];
if(!son[u]||siz[v]>siz[son[u]])son[u]=v;
}
}
}
void dfs2(int u)
{
w[u]=++cnt;
ord[cnt]=u;
if(son[fa[u]]==u)top[u]=top[fa[u]];
else top[u]=u;
if(son[u])dfs2(son[u]);
travel(i,u,v)if(v!=fa[u]&&v!=son[u])dfs2(v);
}
void pathu(int l,int r,int x)
{
while(top[l]!=top[r])
{
if(dep[top[l]]<dep[top[r]])swap(l,r);
update(1,1,n,w[top[l]],w[l],x);
l=fa[top[l]];
}if(dep[l]>dep[r])swap(l,r);
update(1,1,n,w[l],w[r],x);
}
int pathq(int l,int r)
{
int sum=0,alp,bet;
while(top[l]!=top[r])
{
if(dep[top[l]]<dep[top[r]])swap(l,r);
sum+=query(1,1,n,w[top[l]],w[l]);
alp=confirm(1,1,n,w[top[l]]),bet=confirm(1,1,n,w[fa[top[l]]]);
if(alp==bet)--sum;
l=fa[top[l]];
}if(dep[l]>dep[r])swap(l,r);
sum+=query(1,1,n,w[l],w[r]);
return sum;
}
}
int main()
{
using namespace Siz_Subdivision;
int x,y,z;char opt[30];
scanf("%d%d",&n,&m),Root=chkmin(5,n);
f(i,1,n)scanf("%d",&col[i]);
f(i,1,n-1)scanf("%d%d",&x,&y),add(x,y),add(y,x);
dfs(Root),dfs2(Root);Seg_Tree::build(1,1,n);
f(i,1,m)
{
getchar();
scanf("%s%d%d",opt,&x,&y);
if(opt[0]=='C')scanf("%d",&z),pathu(x,y,z);
else printf("%d\n",pathq(x,y));
}return 0;
}
```