题解 P2486 【[SDOI2011]染色】
博客内食用更加
看到题解里好像没有和我做法完全一样的
来发一下
这道题，显然我们需要树剖一下
然后我们考虑怎么用线段树去维护区间颜色段数
我们会想到我们需要维护这么几个东西
1.区间段数
2.区间左端点的颜色
3.区间右端点的颜色
合并的时候就是左儿子的段数加上右儿子的段数，如果左儿子的右端点和右儿子的左端点是一个颜色，那么就段数-1
因为是区间修改，所以加上一个懒标记就可以了
更新跟普通树剖一样，但是查询不太一样
这里提供一种适用范围更广的做法
我是受到了这道题的启发，那道题是求树上最大子段和，需要维护的东西比较多，所以单纯用变量不太好做。
所以我让我们的query函数返回的是一个结构体来储存这一段的答案的段数，左端点，右端点分别是什么，然后我们再写一个merge函数来合并两个结构体，其实写起来和pushup差不多，大概是这个样子的
segment_tree merge(segment_tree l,segment_tree r){
if(!l.sum)return r;
if(!r.sum)return l;
segment_tree res;
res.lcol=l.lcol,res.rcol=r.rcol;
res.sum=l.sum+r.sum;
if(l.rcol==r.lcol)res.sum--;
return res;
}那么我们树剖查询的时候，开两个segment_tree类型的结构体变量l，r，分别表示x往上跳到他们的lca的这一段的颜色段数和y跳到lca这一段的颜色段数
然后依次合并就可以了
但是注意一点，merge函数是不满足交换律的，所以我们要把top[x]~x这一段放在左边。
最后合并的时候要把l的左端点颜色和右端点颜色交换一下，因为我们要把一个区间整体反转才能接到一起（可以画个图理解一下）
然后如果你只过了hack数据的话就查一下你的查询那一段有没有查反就好了
code time:
# include <bits/stdc++.h>
using namespace std;
# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)
const int N=1e5+5;
template <typename T> void read(T &x){
x=0;int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
x*=f;
}
int n,m;
int head[N],cnt;
int a[N],_a[N];
int faz[N],son[N],dep[N],siz[N],top[N],dfn[N],tot;
struct Edge{
int to,next;
}e[N<<1];
void add(int x,int y){
e[++cnt]=(Edge){y,head[x]},head[x]=cnt;
}
struct segment_tree{
int l,r;
int lcol,rcol,sum;
int tag;
segment_tree(){l=r=lcol=rcol=sum=tag=0;}
}seg[N<<2];
# define lc (u<<1)
# define rc (u<<1|1)
void pushup(int u){
seg[u].sum=seg[lc].sum+seg[rc].sum;
if(seg[lc].rcol==seg[rc].lcol)seg[u].sum--;
seg[u].lcol=seg[lc].lcol;
seg[u].rcol=seg[rc].rcol;
}
void pushdown(int u){
seg[lc].sum=1;
seg[lc].lcol=seg[lc].rcol=seg[u].tag;
seg[lc].tag=seg[u].tag;
seg[rc].sum=1;
seg[rc].lcol=seg[rc].rcol=seg[u].tag;
seg[rc].tag=seg[u].tag;
seg[u].tag=0;
}
segment_tree merge(segment_tree l,segment_tree r){
if(!l.sum)return r;
if(!r.sum)return l;
segment_tree res;
res.lcol=l.lcol,res.rcol=r.rcol;
res.sum=l.sum+r.sum;
if(l.rcol==r.lcol)res.sum--;
return res;
}
void build(int u,int l,int r){
seg[u].l=l,seg[u].r=r;
if(l==r){seg[u].sum=1,seg[u].lcol=seg[u].rcol=_a[l];return;}
int mid=l+r>>1;
build(lc,l,mid);
build(rc,mid+1,r);
pushup(u);
}
void update(int u,int l,int r,int k){
if(seg[u].l>=l&&seg[u].r<=r){
seg[u].sum=1;
seg[u].lcol=seg[u].rcol=k;
seg[u].tag=k;
return;
}
if(seg[u].tag)pushdown(u);
int mid=seg[u].l+seg[u].r>>1;
if(l<=mid)update(lc,l,r,k);
if(r>mid)update(rc,l,r,k);
pushup(u);
}
segment_tree query(int u,int l,int r){
if(seg[u].l>=l&&seg[u].r<=r)return seg[u];
if(seg[u].tag)pushdown(u);
int mid=seg[u].l+seg[u].r>>1;
if(r<=mid)return query(lc,l,r);
if(l>mid)return query(rc,l,r);
return merge(query(lc,l,r),query(rc,l,r));
}
void RouteModify(int x,int y,int k){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(1,dfn[top[x]],dfn[x],k);
x=faz[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
update(1,dfn[x],dfn[y],k);
}
int RouteQuery(int x,int y){
segment_tree l,r;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]){
r=merge(query(1,dfn[top[y]],dfn[y]),r);
y=faz[top[y]];
}
else{
l=merge(query(1,dfn[top[x]],dfn[x]),l);
x=faz[top[x]];
}
}
if(dep[x]<dep[y])r=merge(query(1,dfn[x],dfn[y]),r);
else l=merge(query(1,dfn[y],dfn[x]),l);
swap(l.lcol,l.rcol);
return merge(l,r).sum;
}
void dfs1(int u,int fa){
faz[u]=fa;
siz[u]=1;
dep[u]=dep[fa]+1;
RepG(i,u){
int v=e[i].to;
if(v==fa)continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void dfs2(int u,int _top){
top[u]=_top;
dfn[u]=++tot;
_a[tot]=a[u];
if(!son[u])return;
dfs2(son[u],_top);
RepG(i,u){
int v=e[i].to;
if(v==faz[u]||v==son[u])continue;
dfs2(v,v);
}
}
int main()
{
memset(head,-1,sizeof(head));
read(n),read(m);
Rep(i,1,n)read(a[i]);
Rep(i,1,n-1){
int x,y;
read(x),read(y);
add(x,y),add(y,x);
}
dfs1(1,0),dfs2(1,1);
build(1,1,n);
Rep(i,1,m){
char opt[10];
int x,y,z;
scanf("%s",opt);
if(opt[0]=='C'){
read(x),read(y),read(z);
RouteModify(x,y,z);
}
else{
read(x),read(y);
printf("%d\n",RouteQuery(x,y));
}
}
return 0;
}