offline · union-find · α(n)

Tarjan 离线：一遍 DFS 配并查集

前两条路都是在线的：预处理一次，此后任何时刻来一个询问都能立刻回答。本页这条路放弃了这一点，换来更小的常数。

1 · 离线的定义与它的约束

离线（offline）指算法在开跑前就要拿到全部询问。它不是「慢一点」的意思，而是一条使用约束：询问集合必须事先确定，且答案不保证按提问顺序产出。

放弃在线换到的是：不必为「任意时刻的任意询问」准备通用结构，只需按一个对算法方便的顺序把这些具体询问逐一解决。Tarjan 选的顺序是 DFS 的回溯次序。

代价有两条，都很具体。第一， $q$ 个询问要先存下来，空间 $O(q)$ 。第二，某个询问可能要等到 DFS 快走完时才有答案，无法「问一个答一个」。若某个询问的内容依赖前一个询问的答案（交互式场景），这条路直接排除。

2 · 算法

树上做一次 DFS。每个节点维护两样东西：一个并查集，和一个 $\text{ancestor}$ 标记。

dfs(v):
  makeSet(v); ancestor[find(v)] = v
  for each child c of v:
      dfs(c)
      union(v, c)
      ancestor[find(v)] = v        # 合并后代表元可能变了，标记要写回 v
  black[v] = true
  for each query (v, w):
      if black[w]:  answer = ancestor[find(w)]

并查集只用来回答一个问题：「 $w$ 现在被归到哪棵已完成的子树里」。合并本身不带信息， $\text{ancestor}$ 才带——每次把孩子并进父亲之后，都要把整个集合的标记改回父亲。

图 2-1 · Tarjan 离线 LCA 的逐步执行：节点下方的 ↑X 是它所在并查集集合当前的 ancestor，询问表随 DFS 推进陆续填上答案。可单步前后移动。

演示树上共 43 步：13 次进入、12 次合并、5 次回答、13 次离开。

3 · 不变量

定理 3.1 DFS 处理到节点 $v$ 且 $v$ 已染黑时，对任何已染黑的 $w$ ， $\text{ancestor}[\text{find}(w)] = \text{LCA}(v, w)$ 。

证明设 $z = \text{LCA}(v, w)$ 。 $w$ 已染黑说明 $w$ 的整棵子树在 $v$ 之前处理完；由 DFS 的次序， $w$ 落在 $z$ 的某棵已完成的子树里（若 $w = z$ 则 $w$ 自成一格）。

考察 $w$ 所在集合的演化。 $w$ 完成时它与自己的子树合成一个集合，标记是 $w$ ；此后每次它的某级祖先 $p$ 处理完一个孩子，就把那个孩子的整棵子树并进 $p$ 并把标记改成 $p$ 。这个过程沿 $w$ 到根的路径逐级向上，但只在祖先已经处理完对应孩子时才发生。

$z$ 恰是这条链上最后一个「已经把含 $w$ 的那棵子树合并进来」的节点： $z$ 的那棵子树先于 $v$ 完成，所以合并已发生，标记写成了 $z$ ；而 $z$ 再往上的祖先此刻还停在「正在处理含 $v$ 的那棵子树」，尚未合并，标记还没轮到它们。 $\blacksquare$

一个询问 $(u, v)$ 在两个端点里较晚染黑的那一次被回答。所以答案的产出次序由树形决定，与提问次序无关。

4 · 合并时机

上面的伪代码里，union(v, c) 写在 dfs(c) 之后、循环之内。这个位置是唯一正确的位置。

本系列的引擎第一版把它挪到了循环外：先递归完全部孩子，再一次性把所有孩子并进 $v$ 。看上去只是把同一批合并推迟了一点，实测直接错。三节点的树 $0 \to \{1, 2\}$ ，询问 $(1, 2)$ 得到的答案是 1 而不是 0——处理到节点 2 时，节点 1 的子树还没并进 0， $\text{find}(1)$ 仍是 1 自己，标记也还是 1。

问题的根源是定理 3.1 的证明里那句「只在祖先已经处理完对应孩子时才发生」。把合并推迟到全部孩子跑完，就制造了一段时间窗口：后一个孩子的子树在处理询问，而前一个孩子的子树还没并上来。这一段窗口里的每一个跨兄弟询问都会读到过期的标记。

警示 · 迭代式改写尤其容易踩这个坑。递归版本里 union 天然写在 dfs(c) 返回之后；改成显式栈之后，「孩子刚返回」这个时刻要靠栈顶的子节点下标来识别，一不留神就写成了「所有孩子都返回之后」。本系列的迭代实现用 if (i === 0) 进入 else 合并第 i-1 个孩子 来定位这一时刻。

5 · 代价

并查集用了按秩合并加路径压缩，全部操作的摊还代价是 $O(\alpha(n))$ ， $\alpha$ 是反 Ackermann 函数。它的增长慢到在任何现实规模上都可以当常数看，这一点本系列的实测数字给得很直白：

$n = q$	指针跳数总计	每单位 $(n+q)$
1000	2918	1.459
100000	300455	1.502
1000000	3006739	1.503

规模涨三个数量级，单位代价从 1.459 挪到 1.503。并查集的具体机制见并查集，本页只用它的两个操作。

图 5-1 · 提问顺序与回答顺序的错位，以及答案在 DFS 进度上的分布。可改树规模与询问数观察最后一个答案出现的位置。

分工也就清楚了。全部询问事先已知，Tarjan 的总量最小；要求边问边答，就回到树上倍增或欧拉序 RMQ。

6 · 参考文献

Tarjan, R. E. (1979). Applications of path compression on balanced trees. Journal of the ACM, 26(4), 690–715.
Gabow, H. N., & Tarjan, R. E. (1985). A linear-time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences, 30(2), 209–221.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed., Problem 21-3). MIT Press.