求助：证明树中三个最远节点必有两个在直径上及算法正确性验证

问题定义 #

目标是在树中找到三个节点(a, b, c)，让三条路径的并集{P(a,b) ∪ P(b,c) ∪ P(a,c)}包含的边数最多——换句话说，就是找到能撑起最大规模最小子树的三个节点。这里P(x,y)指x和y之间的唯一简单路径的边集合。

你的算法步骤 #

• 找到树的直径端点(a, b)
• 删除直径上的所有边，把原树拆成若干互不相交的子树
• 以直径上每个节点为根做DFS，找到子树里的最深节点c
• 返回三元组(a, b, c)

正确性证明的瓶颈问题 #

你提到的“最优三元组必有两个节点在直径上”这个结论不成立，可以用反例直接推翻：

构造一棵简单树：直径是u-c-v（共2条边），节点c额外连三个子节点x、y、z，每个子节点再各连一个叶节点x1、y1、z1。此时最优三元组是(x1, y1, z1)，它们的两两路径并集包含6条边；而按你的算法得到的(u, v, x1)，并集仅包含4条边，显然前者更优。

这说明你的算法只能覆盖部分最优情况，无法保证全局最优。

正确的最优解思路 #

先明确一个关键等价关系：三条路径的并集边数 = 三个节点两两距离之和 / 2。因为树中路径唯一，每条边在两两路径中最多被计算两次，除以2就是实际的唯一边数。所以问题等价于最大化三个节点的两两距离之和。

最优解的构造需要考虑两类情况，取其中的最大值：

1. 包含直径端点的情况：就是你的算法所处理的场景——取直径的两个端点，加上到直径距离最大的节点。此时两两距离之和为2L + 2h_max，对应的并集边数是L + h_max（L是直径长度，h_max是节点到直径的最大距离）。
2. 单点辐射的情况：找到树中的某个节点p，取p的多个子树里的最深节点。比如p有k个互不相交的子树，取其中最深的m个（m≤3），它们的两两距离之和等于这些子树深度之和的2倍。比如前面的反例中，节点c的三个子树最深节点的深度都是2，两两距离之和是12，对应并集边数6，远大于直径相关的情况。

所以完整的最优算法需要同时计算这两类情况的最大值，再选择对应的三元组。

内容的提问来源于stack exchange，提问作者Bialy_kaloryfer