【BZOJ2243】【SDOI2011】染色（樹鍊剖分+線段樹）

Description

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

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

2、詢問節點a到節點b路徑上的顔色段數量（連續相同顔色被認為是同一段），如“112221”由3段組成：“11”、“222”和“1”。

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

Input

第一行包含2個整數n和m，分别表示節點數和操作數；

第二行包含n個正整數表示n個節點的初始顔色

下面 行每行包含兩個整數x和y，表示x和y之間有一條無向邊。

下面 行每行描述一個操作：

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

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

Output

對于每個詢問操作，輸出一行答案。

Sample Input

6 5

2 2 1 2 1 1

1 2

1 3

2 4

2 5

2 6

Q 3 5

C 2 1 1

Q 3 5

C 5 1 2

Q 3 5

Sample Output

3

1

2

HINT

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

題解：

樹鍊剖分+線段樹。比較好的一道題，主要是細節要注意，也就是接駁處顔色是否相同。樹剖後，線段樹要記錄左端點l,右端點r，左端點的顔色lc,右端點的顔色rc,區間成段更新的标記tag,區間有多少顔色段。區間合并的時候要注意如果左子樹的右端和右子樹的左端顔色相同那麼數量要減一。但是存在一個問題目前剖到的鍊與上一次的鍊在相交的邊緣可能顔色相同，如果顔色相同答案需要減一。是以統計答案的時候要記錄下上一次剖到的鍊的左端點的顔色，與目前剖到的鍊右端點的顔色（因為在處理出的線段樹中越靠近根的點位置越左），比較這兩個顔色，若相同則答案減1。

代碼如下：

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#define N 100005
#define ll long long
#define inf 0x7f7f7f7f
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
using namespace std;
int n,m,cnt,sz,hd[N],dep[N],siz[N],bl[N],pos[N],v[N],fa[N][];
struct seg
{
    int l,r,lc,rc,s,tag;
}t[N*3];
struct edge
{
    int to,nex;
}e[N<<];
void insert(int u,int v)
{
    e[++cnt].to=v,e[cnt].nex=hd[u],hd[u]=cnt;
    e[++cnt].to=u,e[cnt].nex=hd[v],hd[v]=cnt;
}
void dfs1(int x,int f)
{
    siz[x]=;
    for(int i=;i<= && (<<i)<=dep[x];i++)
    fa[x][i]=fa[fa[x][i-]][i-];
    for(int i=hd[x];i;i=e[i].nex)
    {
        if(e[i].to==f) continue;
        dep[e[i].to]=dep[x]+;
        fa[e[i].to][]=x;
        dfs1(e[i].to,x);
        siz[x]+=siz[e[i].to];
    }
}
void dfs2(int x,int top)
{
    pos[x]=++sz;bl[x]=top;
    int k=;
    for(int i=hd[x];i;i=e[i].nex)
    if(dep[e[i].to]>dep[x] && siz[k]<siz[e[i].to]) k=e[i].to;
    if(k) dfs2(k,top);
    for(int i=hd[x];i;i=e[i].nex)
    if(dep[e[i].to]>dep[x] && k!=e[i].to) dfs2(e[i].to,e[i].to);
}
int lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    int t=dep[x]-dep[y];
    for(int i=;i<=;i++)
    if(t&(<<i)) x=fa[x][i];
    for(int i=;i>=;i--)
    if(fa[x][i]!=fa[y][i])
    x=fa[x][i],y=fa[y][i];
    if(x==y) return x;
    return fa[x][];
}
void build(int k,int l,int r)
{
    t[k].l=l;t[k].r=r;t[k].s=;t[k].tag=-;
    if(l==r) return;
    build(ls,l,mid);build(rs,mid+,r);
}
void pushup(int k)
{
    t[k].lc=t[ls].lc;t[k].rc=t[rs].rc;
    if(t[ls].rc^t[rs].lc) t[k].s=t[ls].s+t[rs].s;
    else t[k].s=t[ls].s+t[rs].s-;
}
void pushdown(int k)
{
    int tmp=t[k].tag;t[k].tag=-;
    if(tmp==- || t[k].l==t[k].r)return;
    t[ls].s=t[rs].s=;
    t[ls].tag=t[rs].tag=tmp;
    t[ls].lc=t[ls].rc=tmp;
    t[rs].lc=t[rs].rc=tmp;
}
void change(int k,int L,int R,int c)
{
    pushdown(k);
    int l=t[k].l,r=t[k].r;
    if(l==L && r==R)
    {
        t[k].lc=t[k].rc=c;
        t[k].s=;t[k].tag=c;
        return;
    }
    if(mid>=R) change(ls,L,R,c);
    else if(mid<L) change(rs,L,R,c);
    else change(ls,L,mid,c),change(rs,mid+,R,c);
    pushup(k);
}
int ask(int k,int L,int R)
{
    pushdown(k);
    int l=t[k].l,r=t[k].r;
    if(l==L && r==R) return t[k].s;
    if(mid>=R) return ask(ls,L,R);
    else if(mid<L) return ask(rs,L,R);
    else
    {
        int tmp=;
        if(t[ls].rc^t[rs].lc) tmp=;
        return ask(ls,L,mid)+ask(rs,mid+,R)-tmp;
    }
}
int getcol(int k,int x)
{
    pushdown(k);
    int l=t[k].l,r=t[k].r;
    if(l==r) return t[k].lc;
    if(x<=mid) return getcol(ls,x);
    else return getcol(rs,x);
}
int solvesum(int x,int f)
{
    int sum=;
    while(bl[x]!=bl[f])
    {
        sum+=ask(,pos[bl[x]],pos[x]);
        if(getcol(,pos[bl[x]])==getcol(,pos[fa[bl[x]][]])) sum--;
        x=fa[bl[x]][]; 
    }
    sum+=ask(,pos[f],pos[x]);
    return sum;
}
void solvechange(int x,int f,int c)
{
    while(bl[x]!=bl[f])
    {
        change(,pos[bl[x]],pos[x],c);
        x=fa[bl[x]][]; 
    }
    change(,pos[f],pos[x],c);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=;i<=n;i++) scanf("%d",&v[i]);
    for(int i=;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        insert(x,y);
    }
    int a,b,c;
    dfs1(,);dfs2(,);
    build(,,n);
    for(int i=;i<=n;i++) change(,pos[i],pos[i],v[i]);
    for(int i=;i<=m;i++)
    {
        char ch[];
        scanf("%s",ch);
        if(ch[]=='Q')
        {
            scanf("%d%d",&a,&b);
            int t=lca(a,b);
            printf("%d\n",solvesum(a,t)+solvesum(b,t)-);
        }
        else
        {
            scanf("%d%d%d",&a,&b,&c);
            int t=lca(a,b);
            solvechange(a,t,c);solvechange(b,t,c);
        }
    }
    return ;
}