口胡下基于 O(1) lca的线性(大概吧)做法
查看原帖
口胡下基于 O(1) lca的线性(大概吧)做法
365021
masterhuang楼主2024/3/9 20:10

又要拿出典中典的结论了:my blog中。

经典套路删边变加边,然后合并注意到第二层 max 相当于点集的直径啊,套用上述结论,于是合并的时候直接合并直径,大概有个并查集的 α\alpha?当做线性的吧。

然后 O(n)−O(1) lcaO(n)-O(1)\ lca 是为了求两点 disdis,实现时一般为 O(nlog⁡n)−O(1)O(n\log n)-O(1),参考魏老师博客中的 lca 的六种求法(直接搜即可)

2024/3/9 20:10
加载中...