求证树中任意顶点的最远路径终点必为树直径的两个端点之一

首先明确前提：我们讨论的结构是无环连通的树，s-t是树的直径（即整棵树中长度最长的简单路径），需证明任意节点w出发的最长简单路径，终点一定是s或t中的一个。
我们分两种场景分别用反证法推导：

• 场景1：w位于s-t的直径路径上
  假设从w出发的最长路径终点为u，且u既不是s也不是t，那么路径长度满足 d(w,u) > max(d(w,s), d(w,t))。
  此时计算s到u的路径长度：d(s,u) = d(s,w) + d(w,u) > d(s,w) + d(w,t) = d(s,t)，这和s-t是树直径的前提矛盾，假设不成立，因此该场景下最长路径终点必然是s或t。
• 场景2：w不在s-t的直径路径上
  因为树是连通无环的，w到s-t路径存在唯一的最近交点x，即w到s-t上任意点的路径都要经过x。
  依然用反证法：假设从w出发的最长路径终点为u，且u既不是s也不是t。此时d(w,u)必然大于max(d(w,s), d(w,t))，否则最长路径终点就会是s或t。
  我们把长度展开：
  d(w,s) = d(w,x) + d(x,s)
d(w,t) = d(w,x) + d(x,t)
  不管w-u路径是否和s-t相交，都可以推导得到：d(x,u) > max(d(x,s), d(x,t))
  此时计算s到u的路径长度：d(s,u) = d(s,x) + d(x,u) > d(s,x) + d(x,t) = d(s,t)，这就得到了一条比直径更长的路径，和s-t是直径的前提矛盾，假设不成立。
  因此该场景下，最长路径的终点依然只能是s或t。

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