定义一个在树上的一个点集的直径为点集中两两之间距离的最大值,直径的两个端点为距离达到最大值的任意一对点。那么两个点集合并后的直径的两个端点为两个点集分别的直径的端点两两组合的最大值的那一对点。
即可以 O(1)\mathcal O(1)O(1) 维护合并两个点集后的直径。
没翻到证明结论的题解。