求助证明一个有关树的直径的结论
  • 板块学术版
  • 楼主王熙文
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/7/28 16:45
  • 上次更新2023/11/3 07:12:24
查看原帖
求助证明一个有关树的直径的结论
353688
王熙文楼主2023/7/28 16:45

定义一个在树上的一个点集的直径为点集中两两之间距离的最大值,直径的两个端点为距离达到最大值的任意一对点。那么两个点集合并后的直径的两个端点为两个点集分别的直径的端点两两组合的最大值的那一对点。

即可以 O(1)\mathcal O(1) 维护合并两个点集后的直径。

没翻到证明结论的题解。

2023/7/28 16:45
加载中...