NOI 2021 D1T3 题解

· · 题解

史上最简单 D1T3，也许又是和其他人做法都不同。

显然 SCC 缩点后是一个树，注意构造树的细节：采用 tarjan 算法算出 SCC 后从零入度点 DFS，优先加入编号大的儿子可以保证正确。

$k=1$ 只需分几类讨论。 但是 $k$ 较大时分类讨论显著乏力，我们需要一个更好的刻画。 如果对于 $2\times k$ 个点中的某个点 $p$，满足 $s$ 可以到达 $p$，$p$ 可以到达 $t$，就称它为好点，$s,t$ 也是好点。 结论：一个点可以被经过，当前仅当有一个好点是它的祖先，且有一个好点是它的后代。 证明：考虑 $s$ 到它再到 $t$ 的路径，它上面和下面都会有一个好点。 所以我们只需要找出好点，然后用一个类似虚树构造的东西（但如果栈为空就不统计当前贡献），就可以轻松算出答案。 $k=2$ 时的好点可以分类讨论（情况数比直接分类少了一个数量级），$k>2$ 时也可以用 $O(k^2)$ 的做法求出，更好的办法没有仔细思考过。 使用 $O(1)$ LCA，时间复杂度为 $O(n\log n+q)$。