本文的 lca 仅探讨无修改有根树（？）上的 lca 相关的求法。

有一个有 $n$ 个点的有根树，你要在树上进行 $q$ 次查询，每次查询两点间的 lca。

暴力跳

时间复杂度 $O(nq)$，空间复杂度 $O(n)$，可以在线，非常简单，可以维护一些路径上的信息。

倍增求 lca

预处理时空复杂度 $O(n\log n)$，查询单次 $O(\log n)$，可以在线，可以维护一些可合并的，具有结合律的信息，好写。

斜二倍增求 lca

预处理时空 $O(n)$，查询单次 $O(\log n)$，可以在线，可以维护一些可合并的，具有结合律的信息，比较好写，思想稍微比较难。

树剖求 lca

应该和斜二倍增差不多（？），但需要如果维护信息的话需要额外开线段树（？），这里因为跳链是一个前缀可以预处理，所以也是单次 $O(\log n)$ 的，可拓展性很强，并且查询期望跑得很快。

dfn 序/欧拉序求 lca

预处理时空 $O(n\log n)$，可以在线，单次查询 $O(1)$，可以利用树上差分维护一些信息，好写。

如果用跑得比较快的 st 表，如 +-1 st 表，预处理时空均线性，查询 $O(1)$，不太好写，可以在线，瓶颈在于路径信息需要可差分。

tarjan 求 lca

如果用通常的并查集的话，时间复杂度 $O(\min(n,q)\alpha(n)+q+n)$（大概？），空间线性，需要离线，可以维护可合并的，具有结合律的信息，挺好写的。