P2486 [SDOI2011] 染色
题目链接
分两段，最后靠同一条重链合
树剖加线段树，典中典。
这题的线段树维护比较新颖。
线段树中维护这个区间左右端点的颜色和颜色段数量。
建树和查询和修改时要判断左区间的右端点和右区间的左端点是否颜色相同。
如果不相同，直接将段数相加，否则减一。
然后就是查询路径时，可以想象成两端点相遇，分成两部分。
然后每部分合并时判断连接处是否颜色一样。
最后两部分合并时，判断最后一条链和左右部分的相连处颜色是否相同。（注意，左右顺序）
我们可以通过dfs序，来判断左右部分。
然后其他就是树剖和线段树的板子。
代码
/*
* @Author: Ishar-zdl
* @Date: 2023-10-04 15:48:52
* @Last Modified by: Ishar-zdl
* @Last Modified time: 2023-10-05 15:16:50
*/
#include<bits/stdc++.h>
using namespace std;
#define lc (p<<1)
#define rc (p<<1|1)
inline int read(){
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
return x*f;
}
inline void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+48);
}
const int N=1e5+5;
int tl,tr;
int tll,tlr,trl,trr,ansr,ansl;
int n,m,tot,head[N],top[N],w[N],fa[N],son[N],siz[N],dep[N],dfn[N],rnk[N];
struct edge{
int v,next;
}e[N*4];
struct segment_tree{
int ls,rs,l,r,sum,cha;
#define ls(p) t[p].ls
#define rs(p) t[p].rs
#define l(p) t[p].l
#define r(p) t[p].r
#define sum(p) t[p].sum
#define cha(p) t[p].cha
}t[N*4];
void add(int u,int v){
e[++tot]={v,head[u]};head[u]=tot;
}
void dfs1(int x){
siz[x]=1;
for(int i=head[x],y;i;i=e[i].next)
if(!dep[y=e[i].v]){
fa[y]=x;dep[y]=dep[x]+1,dfs1(y),siz[x]+=siz[y];
if(!son[x]||siz[y]>siz[son[x]])son[x]=y;
}
}
void dfs2(int x,int t){
dfn[x]=++tot;rnk[tot]=x;top[x]=t;
if(son[x])dfs2(son[x],t);
for(int i=head[x],y;i;i=e[i].next){
y=e[i].v;
if(y!=fa[x]&&y!=son[x])dfs2(y,y);
}
}
void build(int p,int l,int r){
l(p)=l,r(p)=r;
if(l==r){rs(p)=ls(p)=w[rnk[l]],sum(p)=1;return;}
int mid=l(p)+r(p)>>1;
build(lc,l,mid),build(rc,mid+1,r);
ls(p)=ls(lc),rs(p)=rs(rc),sum(p)=sum(lc)+sum(rc);
if(rs(lc)==ls(rc))sum(p)--;
}
inline void pushdown(int p){
if(!cha(p))return;
ls(lc)=rs(lc)=ls(rc)=rs(rc)=cha(lc)=cha(rc)=cha(p);
sum(lc)=sum(rc)=1;
cha(p)=0;
}
inline void update(int p,int l,int r,int k){
if(l<=l(p)&&r>=r(p)){
ls(p)=rs(p)=k;sum(p)=1,cha(p)=k;
return;
}pushdown(p);
int mid=l(p)+r(p)>>1;
if(l<=mid)update(lc,l,r,k);
if(r>mid)update(rc,l,r,k);
sum(p)=sum(lc)+sum(rc);
if(rs(lc)==ls(rc))sum(p)--;
ls(p)=ls(lc),rs(p)=rs(rc);
}
inline void modified(int u,int v,int k){
int fu=top[u],fv=top[v];
while(fu!=fv){
if(dep[fu]>dep[fv])update(1,dfn[fu],dfn[u],k),u=fa[fu],fu=top[u];
else update(1,dfn[fv],dfn[v],k),v=fa[fv],fv=top[v];
}
if(dep[u]>dep[v])swap(u,v);
update(1,dfn[u],dfn[v],k);
}
inline int ask(int p,int l,int r){
if(l<=l(p)&&r>=r(p)){
if(tl==0){tl=ls(p);tr=rs(p);return sum(p);}
if(ls(p)==tr){tr=rs(p);return sum(p)-1;}
tr=rs(p);return sum(p);
}
pushdown(p);
int mid=l(p)+r(p)>>1,ans=0;
if(l<=mid)ans+=ask(p<<1,l,r);
if(r>mid)ans+=ask(p<<1|1,l,r);
return ans;
}
inline void query(int u,int v){
tl=tr=0;
tll=tlr=trl=trr=ansl=ansr=0;
int fu=top[u],fv=top[v],ans1=0,ans2=0;
while(fu!=fv){
if(dep[fu]>dep[fv]){
ans1+=ask(1,dfn[fu],dfn[u]),u=fa[fu],fu=top[u];
if(ansr==tr)ans1--;
ansr=tl;
}
else{
ans2+=ask(1,dfn[fv],dfn[v]),v=fa[fv],fv=top[v];
if(ansl==tr)ans2--;
ansl=tl;
}
tl=tr=0;
}
if(dfn[u]>dfn[v])swap(u,v),swap(ansr,ansl);
int ans=ans1+ans2+ask(1,dfn[u],dfn[v]);
if(tl==ansr)ans--;
if(tr==ansl)ans--;
write(ans);putchar('\n');
}
int main(){
// freopen("date.in","r",stdin);freopen("date.out","w",stdout);
n=read(),m=read();fa[1]=dep[1]=1;
for(int i=1;i<=n;i++)w[i]=read();
for(int i=1,u,v;i<n;i++)
u=read(),v=read(),add(u,v),add(v,u);
dfs1(1);tot=0;dfs2(1,1);build(1,1,n);
for(int i=1,u,v,k;i<=m;i++){
char s;cin>>s;
u=read(),v=read();
if(s=='Q')query(u,v);
if(s=='C') k=read(),modified(u,v,k);
}
return 0;
}
附:这题调了一下午。