[SDOI2011]染色 题解

题目大意：

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

　　1、将节点a到节点b路径上所有点都染成颜色c；

　　2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段）

思路:

　　树剖之后，维护其两端的颜色、答案和标记即可。

代码：

#include<cstdio>

#include<iostream>

#define N 100001

using namespace std;

int n,m,cnt,dfn,vis[N],head[N],to[N<<],next[N<<],deep[N],size[N],top[N],id[N],v[N],pa[N],lazy[N<<],lc[N<<],rc[N<<],sum[N<<];

void ins(int x,int y)

{

     to[++cnt]=y,next[cnt]=head[x],head[x]=cnt;

}

void dfs1(int x)

{

    size[x]=vis[x]=;

    for (int i=head[x];i;i=next[i])

        if (!vis[to[i]])

        {

            deep[to[i]]=deep[x]+;

            pa[to[i]]=x;

            dfs1(to[i]);

            size[x]+=size[to[i]];

        }

}

void dfs2(int x,int chain)

{

    int k=,i;

    id[x]=++dfn;

    top[x]=chain;

    for (i=head[x];i;i=next[i])

        if (deep[to[i]]>deep[x] && size[to[i]]>size[k]) k=to[i];

    if (!k) return;

    dfs2(k,chain);

    for (i=head[x];i;i=next[i])

        if (deep[to[i]]>deep[x] && to[i]!=k) dfs2(to[i],to[i]);

}

void build(int l,int r,int cur)

{

    sum[cur]=,lazy[cur]=-;

    if(l==r)return;

    int mid=l+r>>;

    build(l,mid,cur<<),build(mid+,r,cur<<|);

}

void update(int k)

{

    lc[k]=lc[k<<],rc[k]=rc[k<<|];

    if (rc[k<<]^lc[k<<|]) sum[k]=sum[k<<]+sum[k<<|];

    else sum[k]=sum[k<<]+sum[k<<|]-;

}

void pushdown(int l,int r,int k)

{

    int tmp=lazy[k]; lazy[k]=-;

    if (tmp==- || l==r) return;

    sum[k<<]=sum[k<<|]=;

    lazy[k<<]=lazy[k<<|]=tmp;

    lc[k<<]=rc[k<<]=tmp;

    lc[k<<|]=rc[k<<|]=tmp;

}

void change(int L,int R,int l,int r,int cur,int val)

{

    if (l==L && r==R) { lc[cur]=rc[cur]=val; sum[cur]=; lazy[cur]=val; return; }

    int mid=L+R>>; pushdown(L,R,cur);

    if (r<=mid) change(L,mid,l,r,cur<<,val);

    else if (l>mid) change(mid+,R,l,r,cur<<|,val);

         else change(L,mid,l,mid,cur<<,val),change(mid+,R,mid+,r,cur<<|,val);

    update(cur);

}

int ask(int L,int R,int l,int r,int cur)

{

    if (l==L && r==R) return sum[cur];

    int mid=L+R>>; pushdown(L,R,cur);

    if (r<=mid) return ask(L,mid,l,r,cur<<);

    else if (l>mid) return ask(mid+,R,l,r,cur<<|);

         else

         {

              int tmp=;

              if (rc[cur<<]^lc[cur<<|]) tmp=;

              return ask(L,mid,l,mid,cur<<)+ask(mid+,R,mid+,r,cur<<|)-tmp;

         }

}

int getc(int l,int r,int cur,int x)

{

    if (l==r) return lc[cur];

    int mid=l+r>>; pushdown(l,r,cur);

    if (x<=mid) return getc(l,mid,cur<<,x);

    else return getc(mid+,r,cur<<|,x);

}

int solvesum(int x,int y)

{

    int sum=;

    for (;top[x]!=top[y];x=pa[top[x]])

    {

        if (deep[top[x]]<deep[top[y]]) swap(x,y);

        sum+=ask(,n,id[top[x]],id[x],);

        if (getc(,n,,id[top[x]])==getc(,n,,id[pa[top[x]]])) sum--;

    }

    if (deep[x]>deep[y]) swap(x,y);

    return sum+=ask(,n,id[x],id[y],);

}

void solvechange(int x,int y,int val)

{

    for (;top[x]!=top[y];x=pa[top[x]])

    {

        if (deep[top[x]]<deep[top[y]]) swap(x,y);

        change(,n,id[top[x]],id[x],,val);

    }

    if (deep[x]>deep[y]) swap(x,y);

    change(,n,id[x],id[y],,val);

}

int main()

{

    int i,a,b,c;

    scanf("%d%d",&n,&m);

    for(i=;i<=n;i++)scanf("%d",&v[i]);

    for(i=;i<n;i++) scanf("%d%d",&a,&b),ins(a,b),ins(b,a);

    dfs1(),dfs2(,),build(,n,);

    for(i=;i<=n;i++) change(,n,id[i],id[i],,v[i]);

    for(i=;i<=m;i++)

    {

        char ch[];

        scanf("%s",ch);

        if(ch[]=='Q')

        {

            scanf("%d%d",&a,&b);

            printf("%d\n",solvesum(a,b));

        }

        else

        {

            scanf("%d%d%d",&a,&b,&c);

            solvechange(a,b,c);

        }

    }

    return ;

}