【树链剖分】染色

1. 将节点 a 到节点 b 的路径上的所有点（包括 a 和 b）都染成颜色 c。
2. 询问节点 a 到节点 b 的路径上的颜色段数量。

简单提一下

1. 操作等于从 a->LCA(a,b)->b
2. a->LCA(a,b)->b 路径上的和 线段树维护区间左右两端点的颜色和区间颜色和，合并的时候注意端点是否相同就可以了。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+12;
struct {
  int to,nex;
}edge[N];
struct {
  int pl,pr,sum,lazy;
}tree[N];
int head[N],cnt,nu,id[N],fa[N],deep[N],siz[N],son[N],top[N],n,m;
int a[N],w[N];

void addedge(int u,int v)
{
  ++cnt;
  edge[cnt].to=v;
  edge[cnt].nex=head[u];
  head[u]=cnt;
}

void pushup(int x)
{
  tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
  tree[x].pl=tree[x<<1].pl;
  tree[x].pr=tree[x<<1|1].pr;
  if( tree[x<<1].pr==tree[x<<1|1].pl ) tree[x].sum--;
}

void pushdown(int x)
{
  if( !tree[x].lazy ) return;
  tree[x<<1].lazy=tree[x<<1|1].lazy=tree[x<<1].pl=tree[x<<1].pr=tree[x<<1|1].pl=tree[x<<1|1].pr=tree[x].lazy;
  tree[x<<1].sum=tree[x<<1|1].sum=1;
  tree[x].lazy=0;
}
void update(int x,int l,int r,int L,int R,int v)
{
  if( L<=l and r<=R ) { tree[x].sum=1,tree[x].lazy=v,tree[x].pl=tree[x].pr=v;return; }
  int mid=l+r>>1;
  pushdown(x);
  if( L<=mid ) update( x<<1,l,mid,L,R,v );
  if( R>mid  ) update( x<<1|1,mid+1,r,L,R,v );
  pushup(x);
}
int query(int x,int l,int r,int L,int R)
{
  if( L<=l and r<=R ) return tree[x].sum;
  int mid=l+r>>1;
  pushdown(x);
  int ans=0,p=0;
  if( L<=mid ) ans+=query( x<<1,l,mid,L,R ),p=1;
  if( R>mid  )
  {
  ans+=query( x<<1|1,mid+1,r,L,R );
  if( p and tree[x<<1].pr==tree[x<<1|1].pl ) ans--;

  }
  return ans;
}

void dfs1(int x,int f,int dep)
{
  fa[x]=f;
  deep[x]=dep;

  int maxson=-1;
  siz[x]=1;
  for(int i=head[x];i;i=edge[i].nex)
  {
    int y=edge[i].to;
    if( y==f ) continue;
    dfs1(y,x,dep+1);
    siz[x]+=siz[y];
    if( siz[y]>maxson )
    {
      maxson=siz[y];
      son[x]=y;
    }
  }
}

void dfs2(int x,int topf)
{
  id[x]=++nu;
  w[nu]=a[x];
  top[x]=topf;
  if( !son[x] ) return;
  dfs2(son[x],topf);
  for(int i=head[x];i;i=edge[i].nex)
  {
    int y=edge[i].to;
    if( y==fa[x] || y==son[x] ) continue;
    dfs2(y,y);
  }
}

int getcl(int x,int l,int r,int pos)
{
  if( l==r ) return tree[x].pl;
  int mid=l+r>>1;
  pushdown(x);
  if( pos<=mid ) return getcl(x<<1,l,mid,pos);
  return getcl(x<<1|1,mid+1,r,pos);
}

void toupdate(int u,int v,int k)
{
  while( top[u]!=top[v] )
  {
    if( deep[top[u]]<deep[top[v]] ) swap(u,v);
    update(1,1,n,id[ top[u] ],id[u],k);
    //cout<<query(1,1,n,id[top[u]],id[u])<<endl;
    u=fa[top[u]];
  }
  if( deep[u]>deep[v] ) swap(u,v);
  update(1,1,n,id[u],id[v],k);
  //cout<<id[u]<<" "<<id[v]<<endl;
  return;
}

int getsum(int u,int v)
{
  int ans=0;
  while( top[u]!=top[v] )
  {
    if( deep[top[u]]<deep[top[v]] ) swap(u,v);
    ans+=query( 1,1,n,id[top[u]],id[u] );
    int al,bl;
    al=getcl(1,1,n,id[top[u]]);
    bl=getcl(1,1,n,id[fa[top[u]]]);
    if( al==bl ) ans--;
    //cout<<u<<endl;
    u=fa[top[u]];

  }

  if( deep[u]>deep[v] ) swap(u,v);
  ans+=query(1,1,n,id[u],id[v]);
  //cout<<id[u]<<" "<<id[v]<<endl;
  return ans;
}

void build(int x,int l,int r)
{
  if( l==r )
  {
    tree[x].pl=tree[x].pr=w[l];
    tree[x].sum=1;
    return;
  }
  int mid=l+r>>1;
  build(x<<1,l,mid);
  build(x<<1|1,mid+1,r);
  pushup(x);
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  {
    cin>>a[i];
  }
  int u,v,k;
  for(int i=1;i<=n-1;i++)
  {
    cin>>u>>v;
    addedge(u,v);
    addedge(v,u);
  }
  dfs1(1,1,1);
  dfs2(1,1);
  build(1,1,n);
  char p;
  while(m--)
  {
    cin>>p>>u>>v;
    if( p=='C' )
    {
      cin>>k;
      toupdate(u,v,k);
    }
    else{
      cout<<getsum(u,v)<<endl;

    }

  }

}