https://www.lydsy.com/JudgeOnline/problem.php?id=2243

Description
给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），
如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。

一道很不错的题。
思路：首先考虑序列上如何维护区间颜色段数，经过思考，发现用线段树，加上维护区间左端点颜色和右端点颜色就行了，合并区间时，如果左区间右端点颜色与右区间左端点颜色相同，那么这个区间颜色 = = =左区间段数 + + +右区间段数 − 1 -1 −1，否则区间颜色 = = =左区间段数 + + +右区间段数。
再考虑树上要怎么维护，我们树剖用u和v往上跳到lca的过程中，维护lca在u这面的上一个计算区间末尾颜色是last1，v这面的上一个计算区间末尾颜色是last2，与序列类似，如果这两个区间相邻位置颜色相同，那么总颜色数-1即可。

#include<bits/stdc++.h>
using namespace std;
#define maxn (100000+100)

int n,m,dfs_clock;
int sz[maxn],fa[maxn],deep[maxn],son[maxn],top[maxn],w[maxn],id[maxn],id2[maxn],ver_w[maxn];
vector<int> G[maxn]; 
int ql,qr,val,setv[maxn*4],sumv[maxn*4],lo[maxn*4],ro[maxn*4],_sum;

void dfs1(int u,int f)
{
    fa[u]=f;
    deep[u]=deep[f]+1;
    sz[u]=1;
    int maxx=0;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v==f)continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(sz[v]>maxx){son[u]=v;maxx=sz[v];}
    }
}

void dfs2(int u,int up)
{
    id[u]=id2[u]=++dfs_clock;
    top[u]=up;
    if(son[u]){dfs2(son[u],up);id2[u]=id2[son[u]];}
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v==son[u]||v==fa[u])continue;
        dfs2(v,v);
        id2[u]=id2[v];
    }
}

void build(int o,int l,int r)
{
    if(l==r)
    {
        setv[o]=w[l];
        sumv[o]=1;
        lo[o]=ro[o]=w[l];
    }
    else
    {
        int mid=(l+r)/2;
        build(o*2,l,mid);
        build(o*2+1,mid+1,r);
        setv[o]=-1;
        lo[o]=lo[o*2];
        ro[o]=ro[o*2+1];
        sumv[o]=sumv[o*2]+sumv[o*2+1];
        if(ro[o*2]==lo[o*2+1])sumv[o]--;
    }   
}

void pushdown(int o)
{
    if(setv[o]>=0)
    {
        setv[o*2]=setv[o*2+1]=setv[o];
        setv[o]=-1;
    }
}

void maintain(int o,int l,int r)
{
    if(setv[o]>=0)
    {
        sumv[o]=1;
        lo[o]=ro[o]=setv[o];
    }
    else
    {
        sumv[o]=sumv[o*2]+sumv[o*2+1];
        if(ro[o*2]==lo[o*2+1])sumv[o]--;
        lo[o]=lo[o*2];
        ro[o]=ro[o*2+1];
    } 
}

void update(int o,int l,int r)
{
    if(ql<=l&&qr>=r)setv[o]=val;
    else
    {
        int mid=(l+r)/2;
        pushdown(o);
        if(ql<=mid)update(o*2,l,mid); else maintain(o*2,l,mid);
        if(qr>mid)update(o*2+1,mid+1,r); else maintain(o*2+1,mid+1,r);
    }
    maintain(o,l,r); 
}

void query(int o,int l,int r)
{
    if(setv[o]>=0)_sum+=1;
    else if(ql<=l&&qr>=r)_sum+=sumv[o];
    else
    {
        int mid=(l+r)/2;
        if(ql<=mid)query(o*2,l,mid);
        if(qr>mid)query(o*2+1,mid+1,r);
        if(ql<=mid&&qr>mid&&ro[o*2]==lo[o*2+1])_sum--;
    }
}

int qcolor(int o,int l,int r,int p)
{
    if(setv[o]>=0)return setv[o];
    else if(l==p)return lo[o];
    else
    {
        int mid=(l+r)/2;
        if(p<=mid)return qcolor(o*2,l,mid,p);
        else return qcolor(o*2+1,mid+1,r,p);
    }
}

int Query(int u,int v)
{
    int last1=-1,last2=-1;
    _sum=0;
    int tp1=top[u],tp2=top[v];
    while(tp1!=tp2)
    {
        if(deep[tp1]<deep[tp2]){swap(tp1,tp2);swap(u,v);swap(last1,last2);}
        ql=id[tp1],qr=id[u];
        query(1,1,n);
        if(qcolor(1,1,n,qr)==last1)_sum--;
        last1=qcolor(1,1,n,ql);
        u=fa[tp1];
        tp1=top[u];
    }
    if(deep[u]>deep[v]){swap(u,v);swap(last1,last2);}
    ql=id[u],qr=id[v];
    query(1,1,n);   
    if(qcolor(1,1,n,ql)==last1)_sum--;
    if(qcolor(1,1,n,qr)==last2)_sum--;
    return _sum;
}

void Update(int u,int v,int z)
{
    int tp1=top[u],tp2=top[v];
    while(tp1!=tp2)
    {
        if(deep[tp1]<deep[tp2]){swap(tp1,tp2);swap(u,v);}
        ql=id[tp1],qr=id[u],val=z;
        update(1,1,n);
        u=fa[tp1];
        tp1=top[u];
    }
    if(deep[u]>deep[v])swap(u,v);
    ql=id[u],qr=id[v],val=z;
    update(1,1,n);
}

int main()
{
    //freopen("input.in","r",stdin);
    char op[10]; 
    int x,y,z;
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",&ver_w[i]);
    for(int i=2;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs1(1,0);
    dfs2(1,1);
    for(int i=1;i<=n;i++)w[id[i]]=ver_w[i];
    build(1,1,n);   
    for(int i=1;i<=m;i++)
    {
        scanf("%s%d%d",op,&x,&y);
        if(op[0]=='Q')
        {
            printf("%d\n",Query(x,y));
        }
        else
        {
            scanf("%d",&z);
            Update(x,y,z);
        }       
    }
    return 0;
}