树上分块.
只查询树上路径信息时,可以在树上随机撒 $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)$ .