【题解】染色 (bzoj2243) 树链剖分 -boshi

题意：给定一棵树，每个节点有一个颜色（10⁵ 内个点）。有很多询问操作（10⁵ 内个操作），分别为将两点之间的路径上的点的颜色全部设为 c，以及询问两点之间的路径上有多少子段（子段是一段连续的同色点）。

我都不知道我写了写什么。总之两棵枣树在我昏昏沉沉的脑子里挥之不去。

以下就是代码，如果你不喜欢压行。我也没办法。今天下午我无聊至极于是开始压行。

#include <iostream>
#include <cstdio>
#include <cstring>
#define MX 400008
#define ls (node<<1)
#define rs ((node<<1)|1)
#define mid ((l+r)>>1)
using namespace std;
typedef struct tnode{int l,r,sm,lc,rc,p,n;}trnode;
trnode tree[MX];
int fst[MX],nxt[MX],v[MX],col[MX],lnum,n,m,num;
int siz[MX],top[MX],son[MX],dep[MX],fa[MX],rak[MX],ind[MX];
void addeg(int nu,int nv){nxt[++lnum]=fst[nu],fst[nu]=lnum,v[lnum]=nv;}
void input(){
    int a,b,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&col[i]);
    for(int i=1;i<n;i++)scanf("%d%d",&a,&b),addeg(a,b),addeg(b,a);
}
void psd(int node){
    int c=tree[node].n;
    if(tree[node].p==0||tree[node].l==tree[node].r)return;
    tree[ls].p=tree[rs].p=1;
    tree[ls].n=tree[rs].n=c;
    tree[ls].sm=tree[rs].sm=1;
    tree[ls].lc=tree[rs].lc=tree[ls].rc=tree[rs].rc=c;
    tree[node].p=0;
}
void upd(int node){
    tree[node].sm=tree[ls].sm+tree[rs].sm-(tree[ls].rc==tree[rs].lc);
    tree[node].lc=tree[ls].lc,tree[node].rc=tree[rs].rc;
}
void build(int node,int l,int r){
    tree[node].l=l,tree[node].r=r,tree[node].p=tree[node].n=0;
    if(l==r)tree[node].sm=1,tree[node].lc=col[rak[l]],tree[node].rc=col[rak[r]];
    else build(ls,l,mid),build(rs,mid+1,r),upd(node);
}
void add(int node,int ql,int qr,int x){
    psd(node);
    int l=tree[node].l,r=tree[node].r;
    if(ql<=l&&r<=qr)tree[node].sm=1,tree[node].lc=tree[node].rc=x,tree[node].p=1,tree[node].n=x;
    else if(r<ql||l>qr)return;
    else add(ls,ql,qr,x),add(rs,ql,qr,x),upd(node);
}
int qsm(int node,int ql,int qr){
    psd(node);
    int l=tree[node].l,r=tree[node].r;
    if(ql<=l&&r<=qr)return tree[node].sm;
    if(mid>=qr)return qsm(ls,ql,qr);
    else if(mid<ql)return qsm(rs,ql,qr);
    else return qsm(ls,ql,qr)+qsm(rs,ql,qr)-(tree[ls].rc==tree[rs].lc);
}
int qcl(int node,int p){
    psd(node);
    int l=tree[node].l,r=tree[node].r;
    if(l==r)return tree[node].lc;
    else if(p<=mid)return qcl(ls,p);
    else return qcl(rs,p);
}
void dfs1(int x,int fat,int dp){
    fa[x]=fat,dep[x]=dp,siz[x]=1;
    for(int i=fst[x];i!=-1;i=nxt[i]){
        if(v[i]==fat)continue;
        dfs1(v[i],x,dp+1),siz[x]+=siz[v[i]];
        if(son[x]==-1||siz[v[i]]>siz[son[x]])son[x]=v[i];
    }
}
void dfs2(int x,int tp){
    top[x]=tp,ind[x]=++num,rak[num]=x;
    if(son[x]==-1)return;
    dfs2(son[x],tp);
    for(int i=fst[x];i!=-1;i=nxt[i])if(v[i]!=fa[x]&&v[i]!=son[x])dfs2(v[i],v[i]);
}
void change(int s,int t,int x){
    int fs=top[s],ft=top[t];
    while(fs!=ft){
        if(dep[fs]<dep[ft])swap(s,t),swap(fs,ft);
        add(1,ind[fs],ind[s],x),s=fa[fs],fs=top[s];
    }
    if(dep[s]>dep[t])swap(s,t);
    add(1,ind[s],ind[t],x);
}
int query(int s,int t){
    int fs=top[s],ft=top[t],tot=0,sc=-1,tc=-1;
    while(fs!=ft){
        if(dep[fs]<dep[ft])swap(s,t),swap(fs,ft),swap(sc,tc);
        tot+=qsm(1,ind[fs],ind[s])-(sc==qcl(1,ind[s]));
        sc=qcl(1,ind[fs]),s=fa[fs],fs=top[s];
    }
    if(dep[s]>dep[t])swap(s,t),swap(sc,tc);
    tot+=qsm(1,ind[s],ind[t])-((sc==qcl(1,ind[s]))+(tc==qcl(1,ind[t])));
    return tot;
}
int main(){
    int a,b,c;
    char ch;
    lnum=-1,num=0;
    memset(fst,0xff,sizeof(fst)),memset(son,0xff,sizeof(son));
    input(),dfs1(1,1,1),dfs2(1,1),build(1,1,n);
    for(int i=1;i<=m;i++){
        ch=getchar();
        while(ch!='Q'&&ch!='C')ch=getchar();
        if(ch=='Q')scanf("%d%d",&a,&b),printf("%d\n",query(a,b));
        else scanf("%d%d%d",&a,&b,&c),change(a,b,c);
    }
    return 0;
}