【bzoj2243】【樹鍊剖分】【線段樹】SDOI2011染色

• 題目大意：

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

  1. 将節點A 到節點B路徑上所有點都染成顔色 C

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

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

• 資料範圍：

  

• 題解：

  對樹上的路徑進行操作， 區間覆寫，區間查詢，一瞅就可以樹剖，剖完之後用線段樹維護區間某種顔色出現的個數col，區間左端點顔色lcol，區間右端點顔色rcol

• 合并時滿足：

  p−>col=p−>lch−>col+p−>rch−>col−(p−>lch−>rcol==p−>rch−>lcol)

• 注意延重鍊向上爬的時候也要維護lcol和rcol進行統計答案

  直接上代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define MAXN 100001
using namespace std;
vector<int> e[MAXN];
int n,m;
int dep[MAXN],size[MAXN],hson[MAXN],fa[MAXN];
void dfs1(int u,int f,int d){
    size[u]=,fa[u]=f,dep[u]=d;
    for(vector<int>::iterator it=e[u].begin();it!=e[u].end();it++){
        if(*it==f) continue;
        dfs1(*it,u,d+);
        size[u]+=size[*it];
        if(size[*it]>size[hson[u]]) hson[u]=*it;
    }
}
int cnt[MAXN],top[MAXN],T,bel[MAXN];
void dfs2(int u,int tp){
    bel[T]=u,cnt[u]=T++,top[u]=tp;
    if(hson[u]) dfs2(hson[u],tp);
    for(vector<int>::iterator it=e[u].begin();it!=e[u].end();it++){
        if(*it==hson[u]||*it==fa[u]) continue;
        dfs2(*it,*it);
    }
}
struct node{
    int lnum,rnum,kind,l,r,mid,lzy;
    node *lch,*rch;
    node(){}
    node(int a,int b,int c):l(a),r(b),mid(c){lnum=rnum=kind=lzy=;lch=rch=NULL;}
}*root;
int C[MAXN];
void push_down(node *p){
    p->lch->lzy=p->rch->lzy=p->lzy;
    p->lch->lnum=p->lch->rnum=p->lzy;
    p->lch->kind=;
    p->rch->lnum=p->rch->rnum=p->lzy;
    p->rch->kind=;
    p->lzy=;
}
void push_up(node *p){
    p->kind=p->lch->kind+p->rch->kind;
    if(p->lch->rnum==p->rch->lnum)
        p->kind--;
    p->lnum=p->lch->lnum;
    p->rnum=p->rch->rnum;
}
node *build(int left,int right){
    node *p=new node(left,right,(left+right)>>);
    if(right-left==){
        p->kind=;
        p->lnum=p->rnum=C[bel[left]];
        return p;
    }
    p->lch=build(left,p->mid);
    p->rch=build(p->mid,right);
    push_up(p);
    return p;
}
void change(node *p,int left,int right,int col){
    if(p->l==left&&p->r==right){
        p->kind=,p->lnum=p->rnum=col;
        p->lzy=col;
        return;
    }
    if(p->lzy)
        push_down(p);
    if(right<=p->mid)
        change(p->lch,left,right,col);
    else if(left>=p->mid)
        change(p->rch,left,right,col);
    else{
        change(p->lch,left,p->mid,col);
        change(p->rch,p->mid,right,col);
    }
    push_up(p);
}
struct Q{
    int sum,lcol,rcol;
    Q(int a,int b,int c):sum(a),lcol(b),rcol(c){}
    Q(){}
};
Q query(node *p,int left,int right){
    if(p->l==left&&p->r==right)
        return Q(p->kind,p->lnum,p->rnum);
    if(p->lzy)
        push_down(p);
    if(right<=p->mid)
        return query(p->lch,left,right);
    else if(left>=p->mid)
        return query(p->rch,left,right);
    else{
        Q a=query(p->lch,left,p->mid);
        Q b=query(p->rch,p->mid,right);
        if(a.rcol==b.lcol)
            return Q(a.sum+b.sum-,a.lcol,b.rcol);
        else
            return Q(a.sum+b.sum,a.lcol,b.rcol);
    }
}
void changeans(int u,int v,int c){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        change(root,cnt[top[u]],cnt[u]+,c);
        u=fa[top[u]];
    }
    if(cnt[u]>cnt[v]) swap(u,v);
    change(root,cnt[u],cnt[v]+,c);
}
int getans(int s,int t){
    pair<int,int> u,v;
    u=make_pair(s,);
    v=make_pair(t,);
    int lc[]={-};
    int ans[]={};
    while(top[u.first]!=top[v.first]){
        if(dep[top[u.first]]<dep[top[v.first]]) swap(u,v);
        Q temp=query(root,cnt[top[u.first]],cnt[u.first]+);
        ans[u.second]=ans[u.second]+temp.sum-(lc[u.second]==temp.rcol);
        lc[u.second]=temp.lcol;
        u.first=fa[top[u.first]];
    }
    if(cnt[u.first]>cnt[v.first]) swap(u,v);
    Q te=query(root,cnt[u.first],cnt[v.first]+);
    int anssum=ans[]+ans[]+te.sum-(lc[u.second]==te.lcol)-(lc[v.second]==te.rcol);
    return anssum;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=;i<=n;i++)
        scanf("%d",&C[i]);
    for(int i=;i<n;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        e[a].push_back(b);
        e[b].push_back(a);
    }
    dfs1(,-,);
    dfs2(,);
    root=build(,T);
    for(int i=;i<=m;i++){
        char a[];
        scanf("%s",a);
        if(a[]=='C'){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            changeans(a,b,c);
        }
        else if(a[]=='Q'){
            int a,b;
            scanf("%d%d",&a,&b);
            printf("%d\n",getans(a,b));
        }
    }
    return ;
}