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

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

Description

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

强制在线
n,m<=500000

Solution

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

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

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

时间复杂度 @H_673_23@O(NlogN)

大佬总结

以上是大佬教程为你收集整理的【数据结构】[BZOJ4771] 七彩树【无实现】全部内容，希望文章能够帮你解决【数据结构】[BZOJ4771] 七彩树【无实现】所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。