HDR002B 病毒

发布于 2021-09-20  908 次阅读


题目链接

题意

给出一个 $n$ 个点的树,然后有 $q$ 次询问,每次询问给出一个大小为 $k_i$ 的点集,问树上是否存在一个点使得该点到点集中任意一点的距离均相同。

$n \le 10^6,~1 \le 5 \times 10^5,~\sum k_i \le 10^6$

分析

令我们要找的这个点到点集中任意一个点的距离为 $dist$,根据性质不难发现,若存在解,则点集中的最远点对(即从点集中取出不相同两个点能得到的最远距离)的长度必然为 $dist \times 2$。

证明如下。令最远点对为 $(x,~y)$,则我们先将 $x$ 和 $y$ 加入图中,然后依次加入点集中的其他点。在只加入 $x$ 和 $y$ 时当前答案点为它们之间的链的中点 $z$。在加入点集中的其他点时,如果要让答案点离开 $z$ 到达其他点,只有可能新加入的点到 $z$ 的距离大于 $z$ 与 $x,~y$ 之间的距离。但是由于 $(x,~y)$ 为最远点对,所以无法找到这样的点能使得答案点离开 $z$。因此如果存在答案则答案一定为 $z$。

因此对于给出的点集,我们只需要用求直径的方式先求出点集中的最远点对,并将最远点对之间的链上的中点拿出作为答案,并检验点集中其他点到答案点的距离是否都相同。如果都满足条件,则此点即为我们要求的答案点;如果存在点不满足条件或是最远点对之间的距离为奇数,则无解。

时间复杂度 $O(\sum k \times \log n)$,可能存在轻度卡常。

代码

View on GitHub


我缓慢吐出一串啊吧啊吧并不再想说话