rt,以前一开始学习到了 O(logn)O(\log n)O(logn) 的倍增 LCA,然后现在又学习到了树剖,说 LCA 也可以用树剖写。现蒟蒻有个不切实际的想法,就是先做一遍树剖(其实应该是把树先剖开)将 top[] 当做“父亲”这样倍增,时间复杂度是否更优?
top[]
这里不讨论用 Tarjan 的 O(n) 离线做法