Luogu5311 [Ynoi2011] 成都七中

发表于 分类于 ， ， 阅读次数：

题意：给出一棵 个点的树，每个点有一种颜色。

有 次询问，每次求将编号为 的点保留，点 所在连通块的颜色数。

允许离线，，时限 。

首先建立点分树。

将询问挂在 所在联通块在点分树中的最浅点上，这样就转化成了有根问题。 （很像猫树分治）

这一步有点学问，需要找到 的点分树祖先中，与 连通的最浅点。而点分树并没有什么好的单调性质。

某个点在联通块中当且仅当到当前根的路径上的点在 内。

不难想到给每个点记录到根路径的最大编号 和最小编号 ,那么可以贡献(连通)的充要条件就是 。

开始时，我们把询问挂在点 上。

由于本题允许离线，一边点分治，一边查看分治块内挂着的（未回答过的）询问是否能与重心连通，若连通则拿下来处理。（不需要显式地建立点分树，正如猫树分治不需要显式建立猫树）

下面来处理一个分治块的所有询问。

可以把所有点先按照 排序，用时间轴消去一维，然后就是这样的问题 :

  • 加入二元组 。

  • 查询满足 的本质不同的 有多少个。

不难发现某个 能够贡献的充要条件是 。

所以只用给每种颜色维护 的最小值即可，开个桶就是。

前缀求和使用树状数组。

综上我们就以 的复杂度完成了本题。