Level Ancestor 的 O(n)-O(1) 解法瞎写

原文中都是写 $\lg$ 的，我按我自己理解写的 $\log$ 不知道对不对（（

说通俗点就是树上 $k$ 级祖先

前面一些部分就跳过了

首先我们现在最常用的做法是 $O(n\log n) - O(1)$ 的在线做法

具体方法就是长剖，长剖后在链顶处理出向上向下的信息，并求出每一个点的 $2^k$ 级祖先，最后由于一个点 $k$ 级祖先所在链长一定 $\ge k$ ，因此直接跳就是 $O(1)$ 的

我们意识到这东西可以优化

考虑一个点的 $k$ 级祖先就是它子树中某个点的 $k'$ 级祖先，这样说不定可以少求一些东西

考虑以叶子结点为这个 “子树中某个点” ，那么现在就是要 $O(1)$ 求一个叶子的 $k$ 级祖先

看起来没啥优化，但实际上预处理方便了很多

我们发现这道题中倍增数组可以通过维护 dfs栈实现单点 $O(\log n)$ 的复杂度

看起来似乎是意义不明的操作，事实上当我们只需要求叶子时，假设叶子结点个数是 $L$ ，那么预处理复杂度可以降到 $O(L\log n + n)$

但是这玩意儿还是 $O(n\log n)$ 的，不过我们注意到 $L=O({n\over \log n})$ 的时候这东西就是 $O(n)$

~~是不是想起了某个四毛子~~

这部分就是硬核剪枝

想想我们标准 RMQ 是怎么做的？

大范围带 $\log$ 小范围指数级

我们这里也这么干

我们把所有子树大小 $< {\log n\over 4}$ 且父亲结点子树大小 $\ge {\log n\over 4}$ 的子树全部剪下来，剪下来的称为微观树，剩下来的称为宏观树

发现宏观树此时的叶子结点个数是 $O({n\over \log n})$ 的，可以用上面的方法 $O(n)$ 处理

众所周知结点数为 $n$ 的本质不同有根树是 $2^{2n}$ 级别的

因此本质不同的微观树最多 $O(2^{{\log n\over 4}})=O(\sqrt{n})$ 种

考虑每种这里的处理时间是 $O(\log^2 n)$ 的，因此这部分总复杂度是 $O(\sqrt{n}\log^2 n)$

考虑查询

对于宏观树内结点直接查即可

对于一个微观树内结点，如果其 $k$ 级祖先在宏观树内，那么就用宏观树中的对应叶子查，否则直接在微观树内查表，显然都是 $O(1)$ 的

于是得到了一个时空 $O(n)$ 在线 $O(1)$ 查询的算法