线段树区间合并就挺麻烦了，再套个树链就更加鬼畜，不过除了代码量大就没什么其他的了。。

一些细节：线段树每个结点用结构体保存，pushup等合并函数改成返回一个结构体，这样好写一些

struct Seg{    int lc,rc,tot;    Seg(){lc=rc=-1;tot=0;}};Seg seg[maxn<<2];int lazy[maxn<<2];Seg pushup(Seg a,Seg b){    if(!a.tot)return b;    if(!b.tot)return a;    Seg res;    res.lc=a.lc,res.rc=b.rc;    res.tot=a.tot+b.tot;    if(a.rc==b.lc)res.tot--;    return res;}

向上爬时更新操作不用变，但是询问操作需要改变

同样有一些值得注意的地方：向上爬的两条链是有顺序的，合并时顺序不能搞反，也不能像普通树链剖分那样直接swap

int Query(int x,int y){    Seg A,B;    while(top[x]!=top[y]){        if(d[top[x]]
     
      id[y])        A=pushup(query(id[y],id[x],1,n,1),A);    else         B=pushup(query(id[x],id[y],1,n,1),B);    if(A.lc==B.lc)return A.tot+B.tot-1;    else return A.tot+B.tot;}
     

最后是完整代码

#include
      
       using namespace std;#define maxn 100005struct Edge{
    int to,nxt;}edge[maxn<<1];int c[maxn],head[maxn],tot,n;int f[maxn],son[maxn],d[maxn],size[maxn];int cnt,id[maxn],rk[maxn],top[maxn];void dfs1(int x,int pre,int deep){    size[x]=1,d[x]=deep;    for(int i=head[x];i!=-1;i=edge[i].nxt){        int y=edge[i].to;        if(y==pre)continue;        f[y]=x;dfs1(y,x,deep+1);size[x]+=size[y];        if(size[son[x]]
       
        >1;    build(lson);build(rson);    seg[rt]=pushup(seg[rt<<1],seg[rt<<1|1]);}void update(int L,int R,int c,int l,int r,int rt){    if(L<=l && R>=r){        lazy[rt]=c;seg[rt].lc=seg[rt].rc=c;        seg[rt].tot=1;return;    }    pushdown(rt);    int m=l+r>>1;    if(L<=m)update(L,R,c,lson);    if(R>m)update(L,R,c,rson);    seg[rt]=pushup(seg[rt<<1],seg[rt<<1|1]);}Seg query(int L,int R,int l,int r,int rt){    if(L<=l && R>=r)return seg[rt];    pushdown(rt);    int m=l+r>>1;    Seg res;    if(L<=m)res=pushup(res,query(L,R,lson));    if(R>m)res=pushup(res,query(L,R,rson));    return res;}void Update(int x,int y,int c){    while(top[x]!=top[y]){        if(d[top[x]]
        
         id[y])swap(x,y);    update(id[x],id[y],c,1,n,1);}int Query(int x,int y){    Seg A,B;    while(top[x]!=top[y]){        if(d[top[x]]
         
          id[y])        A=pushup(query(id[y],id[x],1,n,1),A);    else         B=pushup(query(id[x],id[y],1,n,1),B);    if(A.lc==B.lc)return A.tot+B.tot-1;    else return A.tot+B.tot;}void init(){    memset(head,-1,sizeof head);    memset(lazy,-1,sizeof lazy);    tot=0;}void addedge(int u,int v){    edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++;}int main(){    init();int q;    cin>>n>>q;    for(int i=1;i<=n;i++)cin>>c[i];    for(int i=1;i
          
           >x>>y;        addedge(x,y);addedge(y,x);    }    cnt=0;dfs1(1,0,1),dfs2(1,1);    build(1,n,1);    char op[2];int x,y,z;    while(q--){        scanf("%s",op);        if(op[0]=='Q'){scanf("%d%d",&x,&y);            cout<
           
            <<'\n';} if(op[0]=='C'){scanf("%d%d%d",&x,&y,&z);Update(x,y,z);} } }