又要拿出典中典的结论了:my blog中。
经典套路删边变加边,然后合并注意到第二层 max 相当于点集的直径啊,套用上述结论,于是合并的时候直接合并直径,大概有个并查集的 α\alphaα?当做线性的吧。
然后 O(n)−O(1) lcaO(n)-O(1)\ lcaO(n)−O(1) lca 是为了求两点 disdisdis,实现时一般为 O(nlogn)−O(1)O(n\log n)-O(1)O(nlogn)−O(1),参考魏老师博客中的 lca 的六种求法(直接搜即可)