@ zjy1412
树剖求$LCA$：$O(n \log ^2 n)$
倍增求$LCA$：$O(n \log n)$
by GK0328 @ 2020-09-20 07:22:46
@[zjy1412](/user/102709)
by GK0328 @ 2020-09-20 07:23:24
$Tarjan$求$LCA$多好啊，$O(n)$，代码也短
by GK0328 @ 2020-09-20 07:24:56
@[GK0328](/user/10341) 没有线段树也会多一个log吗？
by zjy1412 @ 2020-09-20 07:25:05
@[zjy1412](/user/102709) 哦，我傻了
~~评测机波动?~~
~~数据专业卡树剖?~~
by GK0328 @ 2020-09-20 07:27:12
@[GK0328](/user/10341) 您怕不是没学过树剖……
by SamariumPhosphide @ 2020-09-20 07:27:16
@[GK0328](/user/10341) 这都能卡的吗。。。
by zjy1412 @ 2020-09-20 07:28:29
树剖求 `LCA` 不是$O(\log n)$的吗？
根据树剖重链的性质，每次向上走轻边时对应节点数至少乘2（否则这里就不会是轻边了），因此一个节点走到根节点最多走 $\log n$ 条轻边。
树剖求 `LCA` 单次询问复杂度最大情况为询问的两个点都要走到根，因此复杂度为 $O(\log n)$。
一般来说树剖求 `LCA` 比倍增求 `LCA` 常数小。
（所以这可能是一个玄学……）
by ZigZagKmp @ 2020-09-20 07:38:54
@[zjy1412](/user/102709) 卡得常数大一点吧
by GK0328 @ 2020-09-20 07:39:37
@[fürtän](/user/319914) 从来没写过树剖求$LCA$~~,因为一直以为是$O(n \log^2 n)$~~，~~今天仔细考虑一下才发现不对劲~~
菜死了
by GK0328 @ 2020-09-20 07:43:19