传送门:牛客

题目描述:

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

如果光是线段上的操作的话,本题和这道题的维护方法类似.因为需要维护区间内连续颜色段的数量,所以对于区间合并来说,我们需要知道区间的左右颜色,这样才能进行合并

假设一个区间内的颜色段贡献使用sumsumsum来记录,左右端开始的颜色块为lc,rclc,rclc,rc那么对于两个区间进行合并成一个区间的过程来说,此时假如左区间的右端颜色等于右区间的左端颜色的话,那么此时我们合并的颜色块应为sum1+sum2−1sum1+sum2-1sum1+sum2−1,因为此时中间部分的那一个颜色是连续的.如果光是线段上的操作的话,至此算是已经结束了

但是因为本题是树上的操作,所以此时我们需要进行树链剖分操作将树形结构转化为线性结构然后使用线段树进行维护.但是与其他的树链剖分题不同的是,本题还存在一个问题

众所周知的是,在树链剖分后的查询时左右两个节点分别往上跳,然后累计每一次跳跃的区间贡献.那么对于本题来说,我们每一次跳跃的区间仍然可能存在`左右端点颜色连续的情况,所以此时我们需要解决这一问题.我们可以记录下来每一次跳跃的左右端点颜色,更为详细来说,对于右节点往左跳,需要比对之前的左端点,对于左节点往右跳,需要比对之前的右端点颜色.其实可以发现当我们的两个节点到达同一个重链之前我们的两个节点的编号都是一直在减少的,也就是说此时我们都是右节点往左跳的情况.但是对于我们达到同一个重链的时候,此时我们需要进行累计的是整段的连续区间,所以此时我们需要判断该区间的两个端点(可以认为,此时我们同时进行了左右节点的跳跃)

代码量较大,需要注意实现过程中的细节问题

下面是具体的代码部分:

#include 
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 102000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int fa[maxn],max_son[maxn],Size[maxn],dep[maxn];
vectoredge[maxn];
void dfs1(int u,int per_u) {Size[u]=1;for(int i=0;iint v=edge[u][i];if(v==per_u) continue;dep[v]=dep[u]+1;dfs1(v,u);Size[u]+=Size[v];fa[v]=u;if(Size[v]>Size[max_son[u]]) {max_son[u]=v;}}
}
int top[maxn],id[maxn],rev[maxn],tot=0;
void dfs2(int u,int t) {top[u]=t;id[u]=++tot;rev[tot]=u;if(!max_son[u]) return ;dfs2(max_son[u],t);for(int i=0;iint v=edge[u][i];if(v==fa[u]||v==max_son[u]) continue;dfs2(v,v);}
} /*=============================================================*/struct Segment_tree{int l,r,lc,rc,sum,lazy;
}tree[maxn*4];int w[maxn];
Segment_tree operator + (Segment_tree l,Segment_tree r) {Segment_tree u;u.l=l.l;u.r=r.r;u.lc=l.lc;u.rc=r.rc;u.sum=l.sum+r.sum;u.lazy=0;if(l.rc==r.lc) u.sum--;return u;
}
void build(int l,int r,int rt) {tree[rt].l=l;tree[rt].r=r;if(l==r) {tree[rt].lc=tree[rt].rc=w[rev[l]];tree[rt].sum=1;return ;}int mid=(l+r)>>1;build(lson);build(rson);tree[rt]=tree[ls]+tree[rs];
}
void change(int rt,int val) {tree[rt].sum=1;tree[rt].lazy=val;tree[rt].lc=tree[rt].rc=val;
}
void pushdown(int rt) {change(ls,tree[rt].lazy);change(rs,tree[rt].lazy);tree[rt].lazy=0;
}
void update(int l,int r,int rt,int val) {if(tree[rt].l==l&&tree[rt].r==r) {change(rt,val);return ;}if(tree[rt].lazy) pushdown(rt);int mid=(tree[rt].l+tree[rt].r)>>1;if(r<=mid) update(l,r,ls,val);else if(l>mid) update(l,r,rs,val);else update(l,mid,ls,val),update(mid+1,r,rs,val);tree[rt]=tree[ls]+tree[rs];
}
void add(int u,int v,int val) {while(top[u]!=top[v]) {if(dep[top[u]]dep[v]) swap(u,v);update(id[u],id[v],1,val);
}
int ans_sum;
int listrc,listlc;
Segment_tree query(int l,int r,int rt,int L,int R) {if(tree[rt].l==l&&tree[rt].r==r) {if(l==L) listlc=tree[rt].lc;if(r==R) listrc=tree[rt].rc;return tree[rt];}if(tree[rt].lazy) pushdown(rt);int mid=(tree[rt].l+tree[rt].r)>>1;if(r<=mid) return query(l,r,ls,L,R);else if(l>mid) return query(l,r,rs,L,R);else return query(l,mid,ls,L,R)+query(mid+1,r,rs,L,R);
}
int pos1,pos2;
void ask(int u,int v) {pos1=pos2=0;while(top[u]!=top[v]) {if(dep[top[u]]dep[v]) swap(u,v),swap(pos1,pos2);ans_sum+=query(id[u],id[v],1,id[u],id[v]).sum;if(pos1==listlc) ans_sum--;if(pos2==listrc) ans_sum--;
}
int n,m;
int main() {n=read();m=read();for(int i=1;i<=n;i++) w[i]=read();for(int i=1;i<=n-1;i++){int u=read(),v=read();edge[u].push_back(v);edge[v].push_back(u);}dfs1(1,0);dfs2(1,1);build(1,tot,1);char opt[10];for(int i=1;i<=m;i++) {scanf("%s",opt);if(opt[0]=='Q') {int u=read(),v=read();ans_sum=0;ask(u,v);printf("%d\n",ans_sum);}else {int u=read(),v=read(),val=read();add(u,v,val);}}return 0;
}