比较简单的 O(n)-O(1) 树上 K 祖先

· · 算法·理论

一个比较简单的 O(n) - O(1) 的在线静态树上 K 祖先。

此算法需要保证：k < dep_{u}，当然 k \ge dep_u 的点本来就不存在，在其他题用的时候可以判一下这个细节。

记 rt 为根，E_i 为欧拉序，令 f_i 表示从 E_i 往上跳 \text{lowbit}(i) 条边后的点，fst_u 表示 u 第一次在欧拉序中出现的位置。

如果 E_i 没有 \text{lowbit}(i) 级祖先，即 dep_{E_i} \le \text{lowbit}(i) 则令 f_i = rt。

这些显然可以 dfs O(n) 预处理。

对于一个查询 u 往上跳 k 步，令：

对于 k \le 1 的情况，直接返回 fa_u 或 u 即可，下面认为 k \ge 2，这说明 \{rt\} \cup son_{rt} 都不会成为 u。

令：p = 2^{\lfloor \log_2 k\rfloor -1},i = fst_u。

令：x = i \bmod (2p),w = i - x + p。

此时 |i - w| = |x - p|，由于 x \in [0,2p)，所以 x - p \in [-p,p)，所以 |x-p | \le p。

利用欧拉序的性质 dis(E_i,E_j) \le |i-j|。

::::success[证明 dis(E_i,E_j) \le |i-j|]

现在假定 i \le j，如果不是就交换 i,j 即可。

显然欧拉序相邻的点在树上相邻，所以有 dis(E_i,E_{i+1}) = 1。

所以存在一条路径：E_i \to E_{i+1} \to E_{i+2} ,\dots, \to E_j，因为所有的路径长度都 \ge 最短路，所以有一些式子：

dis(E_i,E_j) \le \sum_{k = \min(i,j)}^{\max(i,j)-1} dis(E_k,E_{k+1}) = |i-j|

::::

所以 dis(u,E_w) \le p，由于此时 \text{lowbit}(w) = p，令 t = f_w,c = \text{LCA}(u,E_w) 则：

我们可以考虑证一下 w 不会越界。

::::success[证明 w 不会越界]

首先，因为这是欧拉序，所以走到 E_i 至少需要 dep_{E_{i}} -1 步，然后走回根同理，所以：

dep_{E_i} \le i \\ 2n-1 - i \ge dep_{E_i} - 1

其中 2n-1 是欧拉序的长度。

又有：2p \le k < dep_{E_i}，所以从 i 往左或往右不超过 2p 都不越界。

而 p \ge 1，所以 2p-1 \ge p，所以 w 不会越界。

发现：t \ne rt。

这里需要用一下欧拉序的性质：dep_{E_i} \equiv i \pmod 2。

::::success[证明 dep_{E_i} \equiv i \pmod 2]

首先有：d_i = dep_{E_i} - dep_{E_{i-1}} \in \{1,-1\}，令 dep_0 = 0。

我们考虑数学归纳，首先 E_1 = rt,dep_{rt} = 1，所以符合结论。

考虑若 dep_{E_i} \equiv i \pmod 2，我们看看对 i+1 是否成立。

容易发现：(dep_{E_i} -1 ) \bmod 2 = (dep_{E_i} + 2 -1) \bmod2 = (dep_{E_{i}}+1) \bmod 2。

所以：(i+1) \equiv (dep_{E_i}+1) \equiv (dep_{E_i} -1) \pmod 2。

所以：(i+1) \equiv (dep_{E_i} + d_{i+1})=dep_{E_{i+1}} \pmod 2。

证毕！

::::

::::success[证明 t \ne rt]

若 t = rt，则 dep_{E_w} \le p+1。

w = i -x + p =i - (i - \lfloor \frac{i}{2p} \rfloor 2p) + p = p(1 + 2\lfloor \frac{i}{2p} \rfloor) 所以：$dep_{E_w} \le p$，所以有： $$ dep_u = dis(rt,u)+1 \le 1 +dis(u,E_w) + dis(E_w,rt) = dis(u,E_w) + dep_{E_w} \le 2p \le k $$ 又有 $k < dep_u$，但是我们证出来 $dep_u \le k$，所以根本没有这样的 $k$。 :::: 所以 $dep_{E_w} > p$，所以： $$ dis(u,E_w) = dep_u + dep_{E_w} - 2 dep_{c} \le p \\ dep_{E_w} - dep_{t} = p $$ 上下相减得： $$ dep_{u} + dep_t - 2 dep_c \le 0 \\ \therefore dep_t - dep_c \le dep_c - dep_u \le 0 $$ 因为 $t,c$ 都可以通过 $E_w$ 向上跳得到，所以：$t$ 是 $c$ 或 $c$ 的祖先，所以 $t$ 是 $u$ 的祖先！！ 此时：$dis(t,u) \le dis(u,E_w) + dis(E_w,t) \le 2p \le k$，所以 $t$ 不会超过答案！ 考虑长链剖分，我们发现 $t$ 所在的长链的包含的边数 $l$ 满足 $l\ge p$，因为至少能从 $t$ 往下走到 $E_w$。 又有：$k < 2^{\lfloor\log_2 k \rfloor +1}$，所以：$k < 4p \le 4l$，所以我们从 $t$ 再往上跳不超过 $4p \le 4l$ 步，即可得到答案。 所以我们对于每条长链，预处理： - $up_{u,i}$ 表示从链顶 $u$ 往上跳 $i$ 条边的点，$i \in [0,4l_u)$，其中 $l_u$ 表示 $u$ 为链顶的这条长链包含的边数。 - $down_{u,i}$ 表示从链顶 $u$，沿长链往下走 $i$ 条边的点，显然 $i \in [0,l_u]$。 这样，我们直接查 $top_{t}$ 的 $up$ 或 $down$ 即可。 预处理 $up,down$ 显然是 $O(\sum l_u) = O(n)$，因为可以把贡献摊到点上，而一个点只属于一条长链。 所以我们做出来了 $O(n) - O(1)$ 的树上 K 祖先。 代码很好写，就不放了。 # AIGC 感谢 gpt 6 Astra 教会我这个做法。