[SDOI2011]染色

时间:2021-12-14 07:36:19

[SDOI2011]染色

题目描述

[SDOI2011]染色

输入输出格式

[SDOI2011]染色

输出格式:

对于每个询问操作,输出一行答案。

解法

ps:这题本来是树剖的,但我用lct写的,以下是lct的写法,树剖会有所不同

我们考虑把连接不同色点的边权值设为1,连接同色的点的边权设为0,这样我们就可以把问题转化为查询这条路径上所有的边权和,你要输出的就是这个答案加一。

对于维护,我们对每条路径维护一个最左端点的值和最右端点的值,这样就可以统计O(1)地合并信息,修改时做一个懒标记,下放时将当前ans清零再修改左右端点即可。

区间反转时左右端点也要反转

区间反转时左右端点也要反转

区间反转时左右端点也要反转

重要的话说三遍(我就被坑了好久)。

代码

#include<bits/stdc++.h>
#define rg register
using namespace std;
int gi(){
char a=getchar();int b=0;
while(a<'0'||a>'9')a=getchar();
while(a>='0'&&a<='9')b=b*10+a-'0',a=getchar();
return b;
}
const int N=1e6;
int fa[N],ch[N][2],ans[N],w[N],l[N],r[N],lazy1[N],lazy2[N],fz[N],top;
int get(int x){return ch[fa[x]][1]==x;}
int isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
void pushdown(int x){
rg int L=ch[x][0],R=ch[x][1];
if(lazy1[x]){
swap(ch[x][0],ch[x][1]);
swap(l[L],r[L]);
swap(l[R],r[R]);
lazy1[L]^=1;
lazy1[R]^=1;
lazy1[x]^=1;
}
if(lazy2[x]){
w[x]=l[x]=r[x]=lazy2[L]=lazy2[R]=lazy2[x];
lazy2[x]=0;
ans[x]=0;
}
}
void pushup(int x){
pushdown(ch[x][0]);
pushdown(ch[x][1]);
ans[x]=0;
if(ch[x][0]){
l[x]=l[ch[x][0]];
if(w[x]!=r[ch[x][0]])ans[x]++;
}
else l[x]=w[x];
if(ch[x][1]){
r[x]=r[ch[x][1]];
if(w[x]!=l[ch[x][1]])ans[x]++;
}
else r[x]=w[x];
ans[x]+=ans[ch[x][0]]+ans[ch[x][1]];
}
void rotate(int x){
int y=fa[x],z=fa[y],k=get(x);
fa[x]=z;if(!isroot(y))ch[z][ch[z][1]==y]=x;
ch[y][k]=ch[x][k^1];fa[ch[y][k]]=y;
fa[y]=x;ch[x][k^1]=y;
pushup(y);pushup(x);
}
void splay(int x){
for(int i=x;;i=fa[i]){
fz[++top]=i;
if(isroot(i))break;
}
while(top){pushdown(fz[top--]);}
while(!isroot(x)){
int y=fa[x];
if(!isroot(y))
if(get(x)==get(y))rotate(y);
else rotate(x);
rotate(x);
}
}
void access(int x){for(int y=0;x;y=x,x=fa[x])splay(x),ch[x][1]=y,pushup(x);}
void makeroot(int x){access(x);splay(x);lazy1[x]^=1;}
void link(int x,int y){makeroot(x);fa[x]=y;}
void split(int x,int y){makeroot(x);access(y);splay(y);}
void update(int x,int y,int k){split(x,y);lazy2[y]=k;}
void query(int x,int y){split(x,y);printf("%d\n",ans[y]+1);}
int main(){
int n=gi(),m=gi();
for(int i=1;i<=n;++i){
w[i]=gi();
l[i]=r[i]=w[i];
}
for(int i=1;i<n;++i){
int x=gi(),y=gi();
link(x,y);
}
while(m--){
char op=getchar();
while(op!='C'&&op!='Q')op=getchar();
if(op=='C'){
int x=gi(),y=gi(),k=gi();
update(x,y,k);
}
if(op=='Q'){
int x=gi(),y=gi();
query(x,y);
}
}
return 0;
}