bzoj 2589 Count on a tree II

树上分块.

只查询树上路径信息时,可以在树上随机撒 $O(\sqrt n)$ 个关键点,复杂度是对的.

查询路径 $(x,y)$ 时,先从 $x,y$ 向上跳到两个最近的关键点,用预处理的这两个点之间的信息加上其余部分得到信息.

先预处理出任意两个关键点路径上的颜色数目.

对于零散部分,需要检查每种颜色是否在两个关键点路径上出现过,若未出现,则需要将它加入贡献.

为了支持查询,需要维护一个可持久化数组,修改有 $O(n)$ 次,查询有 $O(n\sqrt n)$ 次.

可以直接上一个主席树,时间复杂度 $O(n\sqrt n \log n)$ .

由于查询次数较多,可以考虑根号平衡,用可持久化分块做到修改 $O(\sqrt n)$ ,查询 $O(1)$ ,时间复杂度 $O(n\sqrt n)$ .