题解 P2486 【[SDOI2011]染色】

· · 题解

这道题的做法其实已经很明显了， 树链剖分 + 线段树 ，只是看到区间赋值心血来潮想用 珂朵莉树 水，结果就过了╮(╯▽╰)╭

操作 1 就是 区间推平 ( assign ) ，操作 2 可以像找 最近公共祖先 ( LCA ) 一样一边往上方跳一边统计，由于珂朵莉树的结点存储的是一段值相同的连续区间，我们只需要记录上一次访问的结点的值与当前结点的值比较，若不同则更新并计数。

值得注意的三点：

1.由于我们是统计链上的连续段，所以我们应从深度大的结点往小的枚举。

2.由于我们是从链的两端分别往上跳，所以我们需要分别记录两边上次访问的结点的值。

3.最后处于同一条链上时，需要考虑两端的值相同的情况。

最后放上AC代码：

#include <cstdio>
#include <set>
using std::set;

#define N 100010

struct node
{
    int l,r,v;
    node(int L,int R=-1,int V=0):l(L),r(R),v(V){}
    inline int operator<(const node&x)const{return l<x.l;}
};
set<node>s;
typedef set<node>::iterator IT;

inline IT split(int pos)
{
    IT it(--s.upper_bound(node(pos)));
    if(it->l==pos)
        return it;
    int L(it->l),R(it->r),V(it->v);
    s.erase(it),s.insert(node(L,pos-1,V));
    return s.insert(node(pos,R,V)).first;
}

inline void assign(int l,int r,int v)
{
    IT itr(split(r+1)),itl(split(l));
    s.erase(itl,itr);s.insert(node(l,r,v));
}

int n,m,a[N],x,y,z;
char opt;

int e,bg[N],nx[N<<1],to[N<<1];
inline void link(int u,int v){to[++e]=v,nx[e]=bg[u],bg[u]=e;}

int fa[N],dep[N],siz[N],ws[N];
void dfs1(int now,int f)
{
    fa[now]=f,dep[now]=dep[f]+1,siz[now]=1;
    int mx(-1);
    for(int i=bg[now];i;i=nx[i])
        if(to[i]!=f)
        {
            dfs1(to[i],now);
            siz[now]+=siz[to[i]];
            if(siz[to[i]]>mx)
                mx=siz[to[i]],ws[now]=to[i];
        }
}

int cnt,top[N],id[N],wt[N];
void dfs2(int now,int tp)
{
    top[now]=tp,id[now]=++cnt,wt[cnt]=a[now];
    if(!ws[now])
        return;
    dfs2(ws[now],tp);
    for(int i=bg[now];i;i=nx[i])
        if(to[i]!=fa[now]&&to[i]!=ws[now])
            dfs2(to[i],to[i]);
}

inline void change(int x,int y,int z)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]>dep[top[y]])
        {
            assign(id[top[x]],id[x],z);
            x=fa[top[x]];
        }
        else
        {
            assign(id[top[y]],id[y],z);
            y=fa[top[y]];
        }
    }
    if(dep[x]>dep[y])
        assign(id[y],id[x],z);
    else
        assign(id[x],id[y],z);
}

inline int query(int x,int y)
{
    int ans(0),lasta(0),lastb(0);
    IT itl,itr;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]>dep[top[y]])
        {
            itr=split(id[x]+1),itl=split(id[top[x]]);
            for(--itr;;--itr)
            {
                if(itr->v!=lasta)
                    lasta=itr->v,++ans;
                if(itr==itl)
                    break;
            }
            x=fa[top[x]];
        }
        else
        {
            itr=split(id[y]+1),itl=split(id[top[y]]);
            for(--itr;;--itr)
            {
                if(itr->v!=lastb)
                    lastb=itr->v,++ans;
                if(itr==itl)
                    break;
            }
            y=fa[top[y]];
        }
    }
    if(dep[x]>dep[y])
    {
        itr=split(id[x]+1),itl=split(id[y]);
        for(--itr;;--itr)
        {
            if(itr->v!=lasta)
                lasta=itr->v,++ans;
            if(itr==itl)
                    break;
        }
    }
    else
    {
        itr=split(id[y]+1),itl=split(id[x]);
        for(--itr;;--itr)
        {
            if(itr->v!=lastb)
                lastb=itr->v,++ans;
            if(itr==itl)
                    break;
        }
    }
    return ans-(lasta==lastb);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",a+i);
    for(int i=1;i<n;++i)
    {
        scanf("%d%d",&x,&y);
        link(x,y),link(y,x);
    }
    dfs1(1,0);
    dfs2(1,1);
    for(int i=1;i<=n;++i)
        s.insert(node(i,i,wt[i]));
    while(m--)
    {
        scanf("\n%c%d%d",&opt,&x,&y);
        if(opt=='C')
        {
            scanf("%d",&z);
            change(x,y,z);
        }
        else
            printf("%d\n",query(x,y));
    }
    return 0;
}