bzoj2243 [SDOI2011]染色 樹鍊剖分

Description

給定一棵有n個節點的無根樹和m個操作，操作有2類：

1、将節點a到節點b路徑上所有點都染成顔色c；

2、詢問節點a到節點b路徑上的顔色段數量（連續相同顔色被認為是同一段），

如“112221”由3段組成：“11”、“222”和“1”。

請你寫一個程式依次完成這m個操作。

“C a b c”表示這是一個染色操作，把節點a到節點b路徑上所有點（包括a和b）都染成顔色c；

“Q a b”表示這是一個詢問操作，詢問節點a到節點b（包括a和b）路徑上的顔色段數量。

HINT

數N<=10^5，操作數M<=10^5，所有的顔色C為整數且在[0, 10^9]之間。

Solution

很自然地就想到了樹鍊剖分，線段樹維護左邊第一個顔色，右邊第一個顔色，以及這一段顔色的數量

考慮到在查詢重邊的時候會有相鄰顔色相同的一段，那麼我們每做完一條重邊就判斷它的父親是否和重邊中較淺的點顔色相同

Code

#include <stdio.h>
#include <string.h>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define fill(x,t) memset(x,t,sizeof(x))
const int N=;
const int E=;
struct edge{int x,y,next;}e[E];
int lazy[N<<],tot[N<<],lc[N<<],rc[N<<];
int size[N],pos[N],dep[N],bl[N],fa[N],cnt=;
int ls[N],edCnt=;
int c[N];
int n,m;
int read() {
    int x=,v=; char ch=getchar();
    for (;ch<'0'||ch>'9';v=(ch=='-')?(-):(v),ch=getchar());
    for (;ch<='9'&&ch>='0';x=x*+ch-'0',ch=getchar());
    return x*v;
}
void addEdge(int x,int y) {
    e[++edCnt]=(edge){x,y,ls[x]}; ls[x]=edCnt;
    e[++edCnt]=(edge){y,x,ls[y]}; ls[y]=edCnt;
}
void swap(int &x,int &y) {x^=y; y^=x; x^=y;}
void buildTree(int now,int tl,int tr) {
    if (tl==tr) {return ;}
    int mid=(tl+tr)>>;
    buildTree(now<<,tl,mid);
    buildTree(now<<|,mid+,tr);
}
void dfs1(int now) {
    size[now]=;
    for (int i=ls[now];i;i=e[i].next) {
        if (e[i].y==fa[now]) {continue;}
        dep[e[i].y]=dep[now]+;
        fa[e[i].y]=now;
        dfs1(e[i].y);
        size[now]+=size[e[i].y];
    }
}
void dfs2(int now,int up) {
    pos[now]=++cnt;
    bl[now]=up;
    int mx=;
    for (int i=ls[now];i;i=e[i].next) {
        if (dep[e[i].y]>dep[now]&&size[e[i].y]>size[mx]) {mx=e[i].y;}
    }
    if (!mx) {return ;}
    dfs2(mx,up);
    for (int i=ls[now];i;i=e[i].next) {
        if (dep[e[i].y]<dep[now]||e[i].y==mx) {continue;}
        dfs2(e[i].y,e[i].y);
    }
}
void push_down(int now) {
    if (!lazy[now]) {return ;}
    lazy[now<<]=lazy[now<<|]=lazy[now];
    lc[now<<]=rc[now<<]=lc[now<<|]=rc[now<<|]=lazy[now];
    tot[now<<]=tot[now<<|]=;
    lazy[now]=;
}
void push_up(int now) {
    tot[now]=tot[now<<]+tot[now<<|];
    if (rc[now<<]==lc[now<<|]) tot[now]-=;
    lc[now]=lc[now<<];
    rc[now]=rc[now<<|];
}
void modify(int now,int tl,int tr,int l,int r,int v) {
    push_down(now);
    if (tl==l&&tr==r) {
        lazy[now]=v;
        tot[now]=;
        lc[now]=rc[now]=v;
        return ;
    }
    int mid=(tl+tr)>>;
    if (r<=mid) {
        modify(now<<,tl,mid,l,r,v);
    } else if (l>mid) {
        modify(now<<|,mid+,tr,l,r,v);
    } else {
        modify(now<<,tl,mid,l,mid,v);
        modify(now<<|,mid+,tr,mid+,r,v);
    }
    push_up(now);
}
int query(int now,int tl,int tr,int l,int r) {
    push_down(now);
    if (tl==l&&tr==r) {return tot[now];}
    int mid=(tl+tr)>>;
    if (r<=mid) {return query(now<<,tl,mid,l,r);}
    else if (l>mid) {return query(now<<|,mid+,tr,l,r);}
    else {
        int qx=query(now<<,tl,mid,l,mid);
        int qy=query(now<<|,mid+,tr,mid+,r);
        int ret=qx+qy;
        if (rc[now<<]==lc[now<<|]) ret-=;
        return ret;
    }
}
int query_color(int now,int tl,int tr,int pos) {
    push_down(now);
    if (tl==tr) {return lc[now];}
    int mid=(tl+tr)>>;
    if (pos<=mid) {return query_color(now<<,tl,mid,pos);}
    else {return query_color(now<<|,mid+,tr,pos);}
}
int get_ans(int x,int y) {
    int ret=;
    while (bl[x]!=bl[y]) {
        if (dep[bl[x]]<dep[bl[y]]) {swap(x,y);}
        ret+=query(,,n,pos[bl[x]],pos[x]);
        int color1=query_color(,,n,pos[bl[x]]);
        int color2=query_color(,,n,pos[fa[bl[x]]]);
        if (color1==color2) {ret-=;}
        x=fa[bl[x]];
    }
    if (dep[x]>dep[y]) {swap(x,y);}
    ret+=query(,,n,pos[x],pos[y]);
    return ret;
}
void solve(int x,int y,int z) {
    while (bl[x]!=bl[y]) {
        if (dep[bl[x]]<dep[bl[y]]) {swap(x,y);}
        modify(,,n,pos[bl[x]],pos[x],z);
        x=fa[bl[x]];
    }
    if (dep[x]>dep[y]) {swap(x,y);}
    modify(,,n,pos[x],pos[y],z);
}
int main(void) {
    n=read();
    m=read();
    rep(i,,n) {c[i]=read();}
    rep(i,,n) {
        int x=read();
        int y=read();
        addEdge(x,y);
    }
    dfs1();
    dfs2(,);
    rep(i,,n) {modify(,,n,pos[i],pos[i],c[i]);}
    while (m--) {
        char opt[]; scanf("%s",opt);
        if (opt[]=='Q') {
            int x=read();
            int y=read();
            int prt=get_ans(x,y);
            printf("%d\n",prt);
        } else if (opt[]=='C') {
            int x=read();
            int y=read();
            int z=read();
            solve(x,y,z);
        }
    }
    return ;
}