一个不切实际的想法(LCA)
  • 板块灌水区
  • 楼主大眼仔Happy
  • 当前回复19
  • 已保存回复22
  • 发布时间2023/10/23 21:22
  • 上次更新2023/11/2 11:39:32
查看原帖
一个不切实际的想法(LCA)
537046
大眼仔Happy楼主2023/10/23 21:22

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

这里不讨论用 Tarjan 的 O(n) 离线做法

2023/10/23 21:22
加载中...