【题解】P6118 [JOI 2019 Final]珍しい都市

· · 题解

首先，定义“点 t 对点 u 有贡献”等价于 t 是 u 的独特的城市。

钦定点 u 为根，令点集 L_u 表示到所有到点 u 距离最远的叶子节点构成的集合，对点 u 有贡献的点一定在 L_u 中所有点到 u 的路径的交上。

注意，路径交上的所有点并不都一定对 u 有贡献。

因此一个想法就是考虑找到随便一个点 v 距离点 u 最远，考察 u,v 两点间的路径上的点。

而考虑离点 u 最远的点，可以选一条直径 s-t，s,t 两个点中一定存在一个点是距离点 u 最远的点。

进而问题就转化成了：给定一个点 rt，以 rt 为根，求出每个点 u 到 rt 路径上所有对点 u 有贡献的点的颜色数。

分别以 s,t 为 rt 求一遍上面的问题即可。

接下来考虑如何去求解上面转化后的问题。

考虑一个在点 u 到根节点路径上的点 p 不会对点 u 产生贡献的充分必要条件：存在一个点 t 使得 t 与 u 的距离等于 p 与 u 的距离，按照点 t 的位置分类讨论：

考虑维护出一个点集 T_u，\forall x\in T_u 满足：

同时考虑点集 S_u，\forall x\in S_u 满足：

并且 S_u\subseteq T_u，删掉 T_u 中所有满足存在一个点 t 在 u 子树内，使得 dist(u,x)=dist(u,t) 的点 x 即可将 T_u “变成” S_u。

考虑 u 的一个儿子 v，想要构造出 T_v，需要对 T_u 进行哪些 “改造”（或者说点集如何变化）。

* 先令 $T_v\gets T_u\cup \{u\}$。 * 删掉 $T_v$ 中所有满足存在一个点 $t$ 满足 $t$ 属于 $v$ 的兄弟的子树中，$dist(u,t) = dist(u,x)$ 的点 $x$。 而 “删掉 $T_v$ 中所有满足存在一个点 $t$ 满足 $t$ 属于 $v$ 的兄弟的子树中，$dist(u,t) = dist(u,x)$ 的点 $x$”，可以转化成 “删掉 $T_v$ 中所有 $dist(u,x) <= \text{v 的所有兄弟子树的最大深度 + 1} $ 的点 $x$。 考虑对该树做长链剖分，令点 $u$ 的长儿子为 $son[u]$，$\mathrm{maxdist(u)}$ 表示 $u$ 子树内距离 $u$ 距离最远的点与 $u$ 的距离，$ts[u]$ 表示 $u$ 的次长儿子，$\mathrm{len(u)}=\mathrm{maxdist(ts[u])}+1$。 注意到，对于 $u$ 的所有非长儿子，在点集 $T_u\cup\{u\}$ 中要删除的点集都一样。 而对于点 $u$ 的长儿子，要删除的点集为 $T_u\cup\{u\}$ 中所有满足 $dist(u,x)\le \mathrm{len(u)}$ 的点 $x$。 考虑在 DFS 的过程中维护点集 $T_u$，在进入子树 $u$ 前，全局维护的信息应为 $T_u$ 的信息。 进入子树 $u$ 后依次进行以下操作： * 删除当前全局维护的点集中所有满足 $dist(u,x)\le \mathrm{len(u)}$ 的点 $x$。 * 在当前全局维护的点集中加入点 $u$。 * 递归长子树。 * 删掉当前全局维护的点集中所有满足 $dist(u,x)\le \mathrm{maxdist(u)}$，当前全局维护的点集为 $S_u$，同时也是对于任意轻儿子 $v$ 的 $T_v$。 * 依次递归轻子树,其中在递归轻子树前需要将点 $u$ 加入全局维护的点集中。 * 如果点 $u$ 在全局维护的点集中，删除点 $u$。 这样操作的合法性： 在递归长子树时，在长子树内进行的 “删除操作”影响到的 $u$ 的祖先，至多影响到 $u$ 的 $\mathrm{maxdist(u)}-2$ 级祖先，而这些点在处理轻子树之前本来就需要被删除。 而在递归非长子树 $v$ 时，只会至多影响 $u$ 的 $\mathrm{maxdist(v)}-1$ 级祖先，而这些祖先一定都被删光光了，因此在处理轻子树时一定不会影响到集合中 $u$ 的祖先。 这样，一个元素至多贡献儿子个数次总复杂的为 $O(n)$。