关于合并最远点对信息
  • 板块学术版
  • 楼主CloudyKai
  • 当前回复1
  • 已保存回复3
  • 发布时间2024/7/29 20:27
  • 上次更新2024/7/29 21:30:12
查看原帖
关于合并最远点对信息
301777
CloudyKai楼主2024/7/29 20:27

众所周知,对于形如 “给定一棵树,初始每个点有一种颜色,每次操作将两个颜色的点集合并,问合并后这个点集内最远点对距离” 这样的问题,我们只需要对每个点集维护一组最远点对;而两个点集合并时,合并后的答案一定存在于这至多 4 个点之间的 6 组点对中。

那么,具体如何解决这个操作?我必须要依此比对 6 组关系吗?

对于可能的一种简化流程:在原有两个点的基础上,重复两次加入一个新点,对 3 组点对取最佳答案,这种流程是对的吗?如果错的话,有没有反例呢?

2024/7/29 20:27
加载中...