【数据结构】[BZOJ4771] 七彩树【无实现】

Description

给出一棵n个点的树,每个点有颜色
多次询问以点x为根的子树中距离不超过d的点中不同颜色种类数

强制在线
n,m<=500000

Solution

先考虑如果没有d的限制怎么做

将相同颜色的点拉出来,在他们的位置+1,在他们的lca-1
直接在DFS序上查询即可

有了D的限制以后,我们将所有点按照深度从小到大一个个插入,用主席树维护,其中线段树维护的是DFS序,每次相当于激活一些点,查询直接主席树区间求和即可

时间复杂度 O(NlogN)

相关文章
相关标签/搜索