关于一种 dfs 序求 lca 的方法
查看原帖
关于一种 dfs 序求 lca 的方法
783628
wxr_楼主2025/1/16 21:16

考虑 LCA 和 DFS 序的关系,即对于 u,vu,vdfnudfnvdfn_u \le dfn_v)两点找到深度最大的 ff 使得 [dfnu,dfnv][dfnf,dfnf+sizef1][dfn_u, dfn_v] \subseteq [dfn_f, dfn_f + size_f - 1]

这个东西需要离线以做到单 log\log,所以确实没什么用。

https://www.luogu.com.cn/record/198613383

2025/1/16 21:16
加载中...