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

前端之家收集整理的这篇文章主要介绍了【数据结构】[BZOJ4771] 七彩树【无实现】前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

Description

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

强制在线
n,m<=500000

Solution

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

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

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

时间复杂度 O(NlogN)

原文链接:https://www.f2er.com/datastructure/382226.html

猜你在找的数据结构相关文章