题解 P11988 [JOIST 2025] 宇宙怪盗 / Space Thief

tybbs · 2025-05-16 08:30:32 · 题解

考虑把图定向为一个 DAG。

假如我们已经得到了一个定向使得 s 可以到达 t，考虑怎么确定 s 和 t。我们取出这个 DAG 的拓扑序。对于拓扑序上的一段区间 [l,r]，把除了左右端点都在 [l,r] 内的边都翻转。若 s 依旧可以到达 t，则 s 和 t 都位于 [l,r] 内。运用以上方法可以二分，在 2\log_2 n 次操作内找到 s 和 t。

现在只需要找到一个定向方式使得 s 可以到达 t。容易发现对于这个问题只需要考虑树的情况。

考虑链的情况。可以直接分治，对于同一层的分治中心，添加两个定向方式即可。也只需要 2\log_2 n 此操作。

对于树的情况，容易想到点分治。但如果使用一般的点分治，对于每个分治中心，因为其有多个儿子，需要构造 O(\log n) 个定向，所以总共询问数需要 O(\log^2 n)。

发现如果分治中心恰有 2 个儿子，问题是简单的。所以尝试把所有节点分成两部分，分别视为两棵独立的子树。考虑重心的性质，容易证明存在一种划分子树的方式使得较大的一部分不超过树总节点数的 \frac{2}{3}。具体的，若最大子树超过 \frac{1}{3}，直接单独划出。否则依次加入子树，直到超过 \frac{1}{3}。这样构造的总定向数为 2\log_{\frac{3}{2}}n。

有一个常数优化是在进行确定 s 和 t 的操作时，因为已知 s 和 t 在同一个子树内，所以二分出其中一个后另一个的二分范围可以缩小。这样总的操作次数不会超过 2\log_{\frac{3}{2}}n+\log_2 n，可以通过。

代码实现。