星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

题解 P2486 【[SDOI2011]染色】

posted on 2018-04-13 10:48:55 | under 题解 |

这题目我去年看的时候想用LCT,然后没写出来。

再次看这道题怒来一发树剖。

参考初学线段树时统计颜色的某道题,将区间左右端点颜色记录,上推时如果边界颜色相同就让个数-1。

注意每个地方都要下推。统计答案时注意边界颜色相同也要减1。查询跳链时注意与父亲颜色相同也要减1。此外我的线段树貌似跟其他人的写法有些不同?

P.S. $\rm namespace$ 大法非常好,调代码利器。就是容易让代码变长

#include<bits/stdc++.h>
#define neko 200010
#define meko 200010
#define chkmin(a,b) ((a)<(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
#define travel(i,u,v) for(register int i=head[u],v=e[i].v;i;i=e[i].next,v=e[i].v)
int n,m,t,Root;
typedef int arr[neko];
arr head,dep,siz,fa,son,w,ord,top,col;
int Sum[neko<<2],Led[neko<<2],Red[neko<<2],Pnt[neko<<2];
struct node
{
    int v,next;
}e[meko<<1];
void add(int x,int y)
{
    e[++t].v=y;
    e[t].next=head[x];
    head[x]=t;
}
namespace Seg_Tree
{
    #define mid ((l+r)>>1)
    #define ori tagl,tagr
    #define lson root<<1,l,mid
    #define rson root<<1|1,mid+1,r
    void pushup(int root)
    {
        Sum[root]=Sum[root<<1]+Sum[root<<1|1];
        if(Red[root<<1]==Led[root<<1|1])--Sum[root];
        Led[root]=Led[root<<1],Red[root]=Red[root<<1|1];
    }
    void pushdown(int root)
    {
        if(Pnt[root])
        {
            Sum[root<<1]=Sum[root<<1|1]=1;
            Led[root<<1]=Led[root<<1|1]=Red[root<<1]=Red[root<<1|1]=Pnt[root];
            Pnt[root<<1]=Pnt[root<<1|1]=Pnt[root];
            Pnt[root]=0;
        }
    }
    void build(int root,int l,int r)
    {
        if(l==r){Led[root]=Red[root]=col[ord[l]],Sum[root]=1;return;}
        build(lson);
        build(rson);
        pushup(root);
    }
    void update(int root,int l,int r,int tagl,int tagr,int x)
    {
        if(l>=tagl&&r<=tagr){Pnt[root]=x,Led[root]=Red[root]=x,Sum[root]=1;return;} 
        pushdown(root);
        if(tagl<=mid)update(lson,ori,x);
        if(tagr>mid)update(rson,ori,x);
        pushup(root);
    }
    int query(int root,int l,int r,int tagl,int tagr)
    {
        if(l>=tagl&&r<=tagr)return Sum[root];
        pushdown(root);
        int tmp=0;
        if(tagl<=mid)tmp+=query(lson,ori);
        if(tagr>mid)tmp+=query(rson,ori);
        if(tagl<=mid&&tagr>mid&&Red[root<<1]==Led[root<<1|1])--tmp;
        return tmp;
    }
    int confirm(int root,int l,int r,int tag)
    {
        if(l==r)return Led[root];
        pushdown(root);
        if(tag<=mid)return confirm(lson,tag);
        else return confirm(rson,tag);
    }
}
namespace Siz_Subdivision
{
    using namespace std;
    using namespace Seg_Tree;
    int cnt;
    void dfs(int u)
    {
        dep[u]=dep[fa[u]]+1;
        siz[u]=1;
        travel(i,u,v)
        {
            if(v!=fa[u])
            {
                fa[v]=u;
                dfs(v);
                siz[u]+=siz[v];
                if(!son[u]||siz[v]>siz[son[u]])son[u]=v; 
            } 
        }
    }
    void dfs2(int u)
    {
        w[u]=++cnt;
        ord[cnt]=u;
        if(son[fa[u]]==u)top[u]=top[fa[u]];
        else top[u]=u;
        if(son[u])dfs2(son[u]);
        travel(i,u,v)if(v!=fa[u]&&v!=son[u])dfs2(v);
    }
    void pathu(int l,int r,int x)
    {
        while(top[l]!=top[r])
        {
            if(dep[top[l]]<dep[top[r]])swap(l,r);
            update(1,1,n,w[top[l]],w[l],x);
            l=fa[top[l]];
        }if(dep[l]>dep[r])swap(l,r);
        update(1,1,n,w[l],w[r],x);
    }
    int pathq(int l,int r)
    {
        int sum=0,alp,bet;
        while(top[l]!=top[r])
        {
            if(dep[top[l]]<dep[top[r]])swap(l,r);
            sum+=query(1,1,n,w[top[l]],w[l]);
            alp=confirm(1,1,n,w[top[l]]),bet=confirm(1,1,n,w[fa[top[l]]]);
            if(alp==bet)--sum;
            l=fa[top[l]];
        }if(dep[l]>dep[r])swap(l,r);
        sum+=query(1,1,n,w[l],w[r]);
        return sum;
    }
}
int main()
{
    using namespace Siz_Subdivision;
    int x,y,z;char opt[30];
    scanf("%d%d",&n,&m),Root=chkmin(5,n);
    f(i,1,n)scanf("%d",&col[i]);
    f(i,1,n-1)scanf("%d%d",&x,&y),add(x,y),add(y,x);
    dfs(Root),dfs2(Root);Seg_Tree::build(1,1,n);
    f(i,1,m)
    {
        getchar();
        scanf("%s%d%d",opt,&x,&y);
        if(opt[0]=='C')scanf("%d",&z),pathu(x,y,z);
        else printf("%d\n",pathq(x,y));
    }return 0;
}