AC. 梦想

frank_c1

[BZOJ 4771] 七彩树

发布于2017年03月11日 | 暂无评论 | 618阅读 | 线段树合并

题意简述

给定一棵n个点的有根树,编号依次为1n,其中1号点是根节点。

每个节点都被染上了某一种颜色,其中第i个节点的颜色为c_i。如果c_i=c_j,那么我们认为点i和点j拥有相同的颜色。定义depth_ii节点与根节点的距离,为了方便起见,你可以认为树上相邻的两个点之间的距离为1。站在这棵色彩斑斓的树前面,你将面临m个问题。

每个问题包含两个整数xd,表示询问x子树里且depth不超过depth_x+d的所有点中出现了多少种本质不同的颜色。

强制在线。

1 \le T \le 500, 1 \le n, m \le 10 ^ 5, 1 \le c_i, x, d \le n, \sum{n}, \sum{m} \le 5 \times 10 ^ 5

算法讨论

感觉我的做法有些暴力啊,而且有点奇怪?

我们发现问题是强制在线的,并且没有修改。

而询问的是一段连续信息,虽然不同以往,这次是在子树中的连续深度。

这启发我们使用一些可持久化数据结构维护。

不妨对于每一个点,建立一棵线段树,颜色作为键值,维护颜色在子树中出现的最小深度。

这样建是必要的,但是我们很难统计答案。考虑到对于一个询问x,d,我们关注的是有多少个颜色对应的最小深度\le d。不妨再同步建立一棵最小深度作为键值,维护代表了多少个颜色的线段树。

在更新第一棵线段树的同时,顺便维护第二棵的信息。而由于涉及的是子树信息,我们只需要可持久化地线段树合并即可。

预处理时间复杂度O(n \log n),询问总复杂度O(m \log n),空间复杂度O(n \log n)