Problem

Description

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

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

2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。

请你写一个程序依次完成这m个操作。

Input

第一行包含2个整数n和m，分别表示节点数和操作数；

第二行包含n个正整数表示n个节点的初始颜色

下面 行每行包含两个整数x和y，表示x和y之间有一条无向边。

下面 行每行描述一个操作：

“C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c；

“Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。

Output

对于每个询问操作，输出一行答案。

Sample Input

6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5

Sample Output

3
1
2

HINT

$n,m \leq 10^5 $

$col\leq10^9$

Solution

Analysis

建立树链（重链）剖分和线段树。

线段树维护三个信息：答案，左颜色，右颜色即可。

Attention

合并两个树上路径可以先找,然后即为答案

Code

//Code by Enderturtle
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define repe(i,a) for(register int i=head[a];i;i=e[i].nxt)
#define il inline
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)
typedef long long ll;
using namespace std;
il int read(){
    int x=0;bool f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=0;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return f?x:-x;
}
/*----- head end -----*/
int n,m;
const int N=1e5+10;
struct Edge{
    int v,nxt;
} e[N<<1];int head[N],tot;
il void add(int u,int v){
    e[++tot]=(Edge){v,head[u]};
    head[u]=tot;
}
int dep[N],son[N],sz[N],top[N],fa[N];
il void dfs1(int u,int f){
    fa[u]=f;dep[u]=dep[f]+1;sz[u]=1;
    repe(i,u){
        int v=e[i].v;
        if(v==f) continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[u]]) son[u]=v;
    }
}
int in[N],a[N],col[N],dfs_clock;
il void dfs2(int u,int topf){
    in[u]=++dfs_clock;top[u]=topf;
    a[dfs_clock]=col[u];
    if(!son[u]) return;
    dfs2(son[u],topf);
    repe(i,u){
        int v=e[i].v;
        if(v==fa[u] || v==son[u]) continue;
        dfs2(v,v);
    }
}
il int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    return (dep[u]>dep[v])?v:u;
}
/*-------------*/
struct node{
    int sum;
    int l_col,r_col;
} t[N<<2];
int lazy[N<<2];
#define ls (o<<1)
#define rs ((o<<1)|1)
il void up(int o){
    t[o].sum=t[ls].sum+t[rs].sum-(t[ls].r_col==t[rs].l_col);
    t[o].l_col=t[ls].l_col;
    t[o].r_col=t[rs].r_col;
}
il void push_down(int o){
    if(!lazy[o]) return;
    t[ls].sum=t[rs].sum=1;
    t[ls].l_col=t[ls].r_col=t[rs].l_col=t[rs].r_col=lazy[o];
    lazy[ls]=lazy[rs]=lazy[o];
    lazy[o]=0;
}
il void build(int o,int l,int r){
    if(l==r){
        t[o].sum=1;
        t[o].l_col=t[o].r_col=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);build(rs,mid+1,r);
    up(o);
}
il node query(int o,int l,int r,int L,int R){
    if(l==L && r==R)
        return t[o];
    push_down(o);
    int mid=(L+R)>>1;
    node lson,rson,res;
    lson.sum=lson.l_col=lson.r_col=0;
    rson.sum=rson.l_col=rson.r_col=0;
    if(l<=mid) lson=query(ls,l,min(mid,r),L,mid);
    if(r>mid) rson=query(rs,max(l,mid+1),r,mid+1,R);
    res.sum=lson.sum+rson.sum-(lson.r_col==rson.l_col);
    if(lson.l_col!=0){
        res.l_col=lson.l_col;
    }else res=rson;
    if(rson.r_col!=0){
        res.r_col=rson.r_col;
    }else res=lson;
    return res;
}
il void update(int o,int l,int r,int L,int R,int change){
    if(l==L && r==R){
        t[o].sum=1;
        t[o].l_col=t[o].r_col=change;
        lazy[o]=change;
        return;
    }
    push_down(o);
    int mid=(L+R)>>1;
    if(l<=mid) update(ls,l,min(mid,r),L,mid,change);
    if(r>mid) update(rs,max(l,mid+1),r,mid+1,R,change);
    up(o);
}
/*----------------*/
il int query_col(int u,int c){
    node res;
    res.l_col=res.sum=res.r_col=0;
    while(top[u]!=top[c]){
        node tmp=query(1,in[top[u]],in[u],1,n);
        if(res.r_col==0)
            res=tmp;
        else{
            res.sum+=(tmp.sum-(tmp.r_col==res.l_col));
            res.l_col=tmp.l_col;
        }
        u=fa[top[u]];
    }
    node tmp=query(1,in[c],in[u],1,n);
    if(res.r_col==0) res=tmp;
    else res.sum+=(tmp.sum-(tmp.r_col==res.l_col));
    return res.sum;
}

il void update_dis(int u,int c,int change){
    while(top[u]!=top[c]){
        update(1,in[top[u]],in[u],1,n,change);
        u=fa[top[u]];
    }
    update(1,in[c],in[u],1,n,change);
}

int main(){
    n=read();m=read();
    rep(i,1,n) col[i]=read();
    rep(i,2,n){
        int u=read(),v=read();
        add(u,v);
        add(v,u);
    }
    dfs1(1,1);
    dfs2(1,1);
    build(1,1,n);
    while(m--){
        char opt[2];scanf("%s",opt);
        if(opt[0]=='C'){
            int u=read(),v=read(),change=read();
            int c=lca(u,v);
            update_dis(u,c,change);
            update_dis(v,c,change);
        }else{
            int u=read(),v=read();
            int c=lca(u,v);
            printf("%d\n",query_col(u,c)+query_col(v,c)-1);
        }
    }
    return 0;
}

一个好奇的人