题解 P2486 【[SDOI2011]染色】

2018-10-14 15:04:38


这是一篇树剖+珂朵莉树的题解。

首先显然是要树剖了。此题大约有一半的操作为珂朵莉树的区间赋值,可以考虑珂朵莉树骗分。(然后一不小心就A了)另一部分的操作也很好搞。

具体实现看代码:

#include<cctype>
#include<cstdio>
#include<set>
#include<algorithm>

inline int Read()
{
    int x=0;char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
    {
        x=x*10+(c^48);
        c=getchar();
    }
    return x;
}

const int maxn=200000+10;
int n,m;
int son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],size[maxn],top[maxn],w[maxn],wt[maxn];

struct Edge
{
    int to,next;
}edge[maxn];
int head[maxn],ecnt;

void Add_edge(int u,int v)
{
    edge[++ecnt]=(Edge){v,head[u]};
    head[u]=ecnt;
    edge[++ecnt]=(Edge){u,head[v]};
    head[v]=ecnt;
}

struct node
{
    int l,r;
    mutable int v;
    node(int L,int R=-1,int V=0):l(L),r(R),v(V){}
    bool operator<(const node& o) const
    {
        return l < o.l;
    }
};
//这样的一个节点表示[l,r]内的所有数都是v。

typedef node Ret;
Ret operator + (Ret l,Ret r)
{
    return Ret(l.l?l.l:r.l,r.r?r.r:l.r,l.v+r.v-(l.r==r.l));
}
//这样的一个Ret表示左边颜色为l,右边颜色为r,共有v段颜色。

using std::set;
set<node> s;
#define IT set<node>::iterator

//split(pos)操作是指将原来含有pos位置的节点分成两部分:[l,pos−1]和[pos,r]。
IT split(int pos)
{
    IT it=s.lower_bound(node(pos));
    if(it!=s.end()&&it->l==pos) return it;
    --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;
}

//区间赋值,把l和r+1进行split,再把[l,r]合成一个节点。
void assign(int l,int r,int val=0)
{
    IT itr=split(r+1),itl=split(l);
    s.erase(itl,itr);
    s.insert(node(l,r,val));
}

void build(int l,int r)
{
    int cnt=1,last=wt[l];
    for(int i=l+1;i<=r;++i)
    {
        if(wt[i]!=last)
        {
            s.insert(node(i-cnt,i-1,last));
            cnt=1;
            last=wt[i];
        }
        else
        {
            ++cnt;
        }
    }
    s.insert(node(r+1-cnt,r,last));
    s.insert(node(r+1,r+3,0));
}

Ret query(int l,int r)
{
    Ret ans=Ret(0);
    IT itr=split(r+1),itl=split(l);
    for(;itl!=itr;++itl)
    {
        ans=ans+Ret(itl->v,itl->v,1);
    }
    return ans;
}

int qRange(int x,int y)
{
    Ret lans=Ret(0),rans=Ret(0);
    //lans表示x一侧的结果,rans表示y一侧的结果
    while(top[x]!=top[y])
    {
        if(dep[top[x]]>dep[top[y]])
        {
            lans=query(id[top[x]],id[x])+lans;
            x=fa[top[x]];
        }
        else
        {
            rans=query(id[top[y]],id[y])+rans;
            y=fa[top[y]];
        }
    }
    if(dep[x]>dep[y])
    {
        lans=query(id[y],id[x])+lans;
    }
    else
    {
        rans=query(id[x],id[y])+rans;
    }
    std::swap(lans.l,lans.r);
    return (lans+rans).v;
}

void updRange(int x,int y,int k)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
            std::swap(x,y);
        assign(id[top[x]],id[x],k);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
        std::swap(x,y);
    assign(id[x],id[y],k);
}

//树剖基操
void dfs1(int x,int f,int deep)
{
    dep[x]=deep;
    fa[x]=f;
    size[x]=1;
    int maxson=-1;
    for(int i=head[x];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==f)
            continue;
        dfs1(v,x,deep+1);
        size[x]+=size[v];
        if(size[v]>maxson)
        {
            son[x]=v;
            maxson=size[v];
        }
    }
}

void dfs2(int x,int topf)
{
    id[x]=++cnt;
    wt[cnt]=w[x];
    top[x]=topf;
    if(!son[x])
        return;
    dfs2(son[x],topf);
    for(int i=head[x];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v!=fa[x]&&v!=son[x])
            dfs2(v,v);
    }
}

int main()
{
    n=Read(),m=Read();
    for(int i=1;i<=n;i++)
        w[i]=Read();
    for(int i=1;i<n;i++)
    {
        int a=Read(),b=Read();
        Add_edge(a,b);
    }
    dfs1(1,0,1);
    dfs2(1,1);
    build(1,n);
    char opt[5];
    while(m--)
    {
        int x,y,z;
        scanf("%s",opt);
        if(opt[0]=='C')
        {
            x=Read(),y=Read(),z=Read();
            updRange(x,y,z);
        }
        else
        {
            x=Read(),y=Read();
            printf("%d\n",qRange(x,y));
        }
    }
    return 0;
}