BZOJ原题地址

洛谷原题地址

思路

树上路径修改,当然是选择树链剖分这种没有思维含量的暴力了啊。。。
颜色段的问题,考虑用线段树来维护。每个节点储存区间的颜色段数以及左右端点的颜色种类。当我们要把两个区间的信息合并的时候,只需要判断一下端点处颜色来决定要不要将颜色段数减一就行了。。。
我的写法的一个问题是,在路径查询的时候,因为我们得到的是一个“人”字形的路径,需要分别储存左边和右边的信息,加上最后在同一条重链上得到的区间信息,一共有三个区间需要合并。

如图,询问$X$到$Y$的路径上的颜色段时,我们先分别将$X$和$Y$移动到了$A$和$B$,同时记录了$X$经过的路径上的信息$lres$,和$Y$经过的路径上的信息$rres$。最后,我们获得了位于同一条重链上的$A$,$B$之间的信息$res$。
由于树链剖分的性质,我们知道区间的左端点深度更小,所以$lres$,$rres$,$res$在上图状态下的左端点分别为$A$,$B$和$B$,所以在合并的时候,需要交换一下$rres$的左右端点信息。

代码实现