洛谷 P2486 [SDOI2011]染色 题解【树链剖分】【线段树】

点击量：211

    感觉树剖挺好用的

目录

题目描述

给定一棵有n个节点的无根树和m个操作，操作有2类：

1. 将节点a到节点b路径上所有点都染成颜色c;
2. 询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段）,如“112221”由3段组成：“11”,“222”和“1”。

请你写一个程序依次完成这m个操作。

输入格式

第一行包含2个整数n和m，分别表示节点数和操作数;

第二行包含n个正整数表示n个节点的初始颜色。

下面n-1行每行包含两个整数x和y，表示x和y之间有一条无向边。

下面n行每行描述一个操作：
“C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c；

“Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。

 

输出格式

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

 

样例输入

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

样例输出

3
1
2

提示

题解：

    很多人都把这个题当作树剖的入门题，不过这个题细节挺多，其他实现都和树剖板子差不多。首先构造出树的dfs序，然后把一开始读入的数据重新按照按照dfs序放进线段树中。注意一定不要把读入的数据当作dfs序了。

    线段树区间统计时如果要合并区间，注意两区间相邻位置是否相等，如果相等要减去一个。而树剖是很多段区间合并起来，因此每次跳上去要记录当前top的颜色。如果当前查询的区间两端与它相邻的两端颜色相同，同样要把相同的端减去1。

    这个题主要考的还是树剖，其次是它的一些细节，就是在向上跳的过程中，信息处理不要混乱。数据梯度不明显，一般除了100就是0分，调试要耐心。

Code：

#include<cstdio>
#include<cstring>
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define Mid (t[k].r+t[k].l>>1)
struct node
{
    int l,r,L,R,v,lazy;
    node(int l,int r,int c1,int c2)
    {
        this->l=l;
        this->r=r;
        L=c1;
        R=c2;
        v=1;
        lazy=0;
    }
    node(){}
}t[400000];
int a[101000];
void build(int k,int l,int r)
{
    t[k]=node(l,r,a[l],a[r]);
    if(l==r)
        return;
    build(ls,l,mid);
    build(rs,mid+1,r);
    t[k].v=t[ls].v+t[rs].v-(t[ls].R==t[rs].L);
}
void pushdown(int k)
{
    if(!t[k].lazy||t[k].l==t[k].r)
    {
        t[k].lazy=0;
        return;
    }
    int c=t[k].lazy;
    t[k].lazy=0;
    t[ls].lazy=c;
    t[ls].L=c;
    t[ls].R=c;
    t[ls].v=1;
    t[rs].lazy=c;
    t[rs].L=c;
    t[rs].R=c;
    t[rs].v=1;
    return;
}
void change(int k,int l,int r,int x)
{
    if(l==t[k].l&&r==t[k].r)
    {
        t[k].v=1;
        t[k].L=x;
        t[k].R=x;
        t[k].lazy=x;
        return;
    }
    pushdown(k);
    if(r<=Mid)
        change(ls,l,r,x);
    else if(l>Mid)
        change(rs,l,r,x);
    else
    {
        change(ls,l,Mid,x);
        change(rs,Mid+1,r,x);
    }
    t[k].L=t[ls].L;
    t[k].R=t[rs].R;
    t[k].v=t[ls].v+t[rs].v-(t[ls].R==t[rs].L);
    return;
}
int cl,cr,L,R;
int ask(int k,int l,int r)
{
    pushdown(k);
    if(l==L)
        cl=t[k].L;
    if(r==R)
        cr=t[k].R;
    if(t[k].l==l&&t[k].r==r)
        return t[k].v;
    if(r<=Mid)
        return ask(ls,l,r);
    else if(l>Mid)
        return ask(rs,l,r);
    else
        return ask(ls,l,Mid)+ask(rs,Mid+1,r)-(t[ls].R==t[rs].L);
}

struct edge
{
    int n,nxt;
    edge(int n,int nxt)
    {
        this->n=n;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[200000];
int head[100001],ecnt=-1;
void add(int from,int to)
{
    e[++ecnt]=edge(to,head[from]);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to]);
    head[to]=ecnt;
}
int fa[101000],sz[100010],son[100100],top[101000],dfn[110000],d[101000],dcnt=0;
void Dfs(int x)
{
    sz[x]=1;
    son[x]=0;
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].n!=fa[x])
        {
            fa[e[i].n]=x;
            d[e[i].n]=d[x]+1;
            Dfs(e[i].n);
            if(sz[e[i].n]>sz[son[x]])
                son[x]=e[i].n;
            sz[x]+=sz[e[i].n];
        }
}
void dFs(int x,int t)
{
    top[x]=t;
    dfn[x]=++dcnt;
    if(son[x])
        dFs(son[x],t);
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].n!=fa[x]&&e[i].n!=son[x])
            dFs(e[i].n,e[i].n);
}
void modify(int x,int y,int c)
{
    int tx=top[x],ty=top[y];
    while(tx!=ty)
    {
        if(d[tx]<d[ty])
        {
            int qaq=x;
            x=y;
            y=qaq;
            qaq=tx;
            tx=ty;
            ty=qaq;
            /*qaq=cx;
            cx=cy;
            cy=qaq;*/
        }
        change(1,dfn[tx],dfn[x],c);
        x=fa[tx];
        tx=top[x];
    }
    if(d[x]<d[y])
    {
        int qaq=x;
        x=y;
        y=qaq;
    }
    change(1,dfn[y],dfn[x],c);
    return;
}
int query(int x,int y)
{
    int tx=top[x],ty=top[y];
    int cx=0,cy=0;
    int ans=0;
    while(tx!=ty)
    {
        if(d[tx]<d[ty])
        {
            int qaq=x;
            x=y;
            y=qaq;
            qaq=tx;
            tx=ty;
            ty=qaq;
            qaq=cx;
            cx=cy;
            cy=qaq;
        }
        L=dfn[tx],R=dfn[x];
        ans+=ask(1,L,R);
        if(cr==cx)
            ans--;
        cx=cl;
        x=fa[tx];
        tx=top[x];
    }
    if(d[x]<d[y])
    {
        int qaq=x;
        x=y;
        y=qaq;
        qaq=cx;
        cx=cy;
        cy=qaq;
    }
    L=dfn[y],R=dfn[x];
    ans+=ask(1,L,R);
    if(cl==cy)
        ans--;
    if(cr==cx)
        ans--;
    return ans;
}
int C[100010];
int main()
{
    fa[1]=1;
    d[1]=1;
    memset(head,-1,sizeof(head));
    int n,m,u,v,w;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&C[i]);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    Dfs(1);
    dFs(1,1);
    for(int i=1;i<=n;i++)
        a[dfn[i]]=C[i];
    build(1,1,n);
    char Q[10];
    for(int i=1;i<=m;i++)
    {
        scanf("%s",Q);
        if(Q[0]=='C')
        {
            scanf("%d%d%d",&u,&v,&w);
            modify(u,v,w);
        }
        else
        {
            scanf("%d%d",&u,&v);
            printf("%d\n",query(u,v));
        }
    }
    return 0;
}