带权并查集,在保证并查集的根节点为原图根节点时对于每个并查集根节点维护它到子树内最远的节点的距离,并对于每个点,维护它到它并查集上父亲的距离,记得在路径压缩上维护这个。

强推我的洛谷博客(或者说文章区)

如果渲染格式有问题,去我的洛谷博客