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

Description

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

强制在线
n,m<=500000

Solution

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

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

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

时间复杂度 O(NlogN)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!