求 LCA 的 Tarjan 算法

这是一个复杂度为 $O(n+q)$ 的离线求 LCA 算法

用 dfs 进行遍历并打 tag

假设遍历到 $u$，则已回溯的节点标为 $2$，遍历到但未回溯的节点（即 $u$ 和 $u$ 的祖先）标 $1$，其余为 $0$

现在假设 $u$ 的子树处理完毕，考虑 $u$ 的处理

询问节点为 $(u, v)$

此时，若 $\mathrm{tag}_v = 2$，则可以保证 $v$ 向根走遇到的第一个 $\mathrm{tag} = 1$ 的节点即为 $\mathrm{LCA}(u,v)$，可以用反证法证明

若向根走遇到的第一个 $\mathrm{tag} = 1$ 的节点，记为 $w$，$w \not = \mathrm{LCA}(u,v)$

记 $\mathrm{LCA}(u,v)$ 为 $p$

显然 $p$ 在 $u$ 到根的路径上

若 $p$ 在 $w$ 下方，则 $\mathrm{tag}_p \not= 1$，但是 $p$ 又为 $u$ 的祖先，$\mathrm{tag}=1$

矛盾

若 $p$ 在 $w$ 上方，根据算法可得 $w$ 为 $v$ 的 祖先，又 $\mathrm{tag}_w = 1$ 得 $w$ 为 $u$ 的祖先，所以 $w$ 必为 $u$ 和 $v$ 的公共祖先，但是 $p$ 是 $w$ 的祖先

矛盾

证毕

下面的程序复杂度应该没有问题，但是要卡一下常，吸一口氧才能过