静态树上数颜色的问题总结

· · 个人记录

问题1： 给你一棵树，每个点有一个颜色，q 次询问，每次询问一颗子树某种颜色的出现次数。

下面默认 n,q 同阶。

巨大暴力：

预处理每个点维护每种颜色的出现次数。

时间复杂度O(n^2)

dsu-on-tree：

典中典板子题，离线做一下就完了

时间复杂度 O(n\log n)

问题2： 给你一棵树，每个点有一个颜色，q 次询问，每次询问一颗子树中颜色的出现次数 \ge k 的颜色个数。（CF375D）

巨大暴力：

预处理每个点维护每种颜色的出现次数，询问时枚举颜色。

时间复杂度 O(n^2)

能不能好一点呢？

可是你会启发式合并啊。

然后呢？怎么统计？

智商不够数据结构来凑，套个树状数组就好了。

时间复杂度 O(n \log^2 n)

能不能再好一点呢？

智商够了，不用树状数组了。

考虑算答案的过程，发现就是在做树状数组的前缀+1，只要在对出现次数+1的过程中进行答案单点的+1就行了。

时间复杂度 O(n \log n)。

能不能再优秀一点呢？

dsu-on-tree 做法是离线的，如果强制在线？

还是跑启发式合并。

可以考虑先把这个破问题变复杂一点，开一颗线段树维护答案。做类似主席树类的东西，每次单点修改（递归）的时候直接新复制一个点做修改。

时间复杂度 O(n \log^2 n)。