朴素长链剖分求LCA是否可以被卡到 O(n)O(\sqrt n)O(n)?
不用倍增,就跟重链剖分一样的求LCA。
卡的方法就是先造一棵链(假设每个节点都为右儿子),然后每个节点往左边延伸至比这条链长。
这一棵链理论上可以被卡到 O(n)O(\sqrt n)O(n) 个。
如果会被卡,有没有什么优化方法。