如何证明无边权的树上离一个点的最远点一定取在直径两个端点之一

🔧 关键定义

• 树的 直径：树中最远的两点之间的距离，设为 $d$，其两个端点记为 $s, t$，满足 $\text{dist}(s, t) = d$。
• $f(u)$：表示点 $u$ 到其他所有点的最远距离（即 $\max_{v} \text{dist}(u, v)$）。

🧠 直观理解

🧾 形式化证明

• 树为 $T = (V, E)$，无边权，边长为 1。
• 取树的直径两个端点为 $s, t$，满足 $\text{dist}(s, t)$ 最大。

🧩 目标

🧠 证明思路（基于 BFS 与三角不等式）

1. 对任意点 $u$，从 $u$ 开始做一次 BFS，找到最远点 $v$。
2. 从 $v$ 再做一次 BFS，找到它的最远点 $w$。则路径 $v \to w$ 是树的一条直径路径。

• $v$ 是 $u$ 的最远点；
• $v \to w$ 是直径路径；
• $v$ 是某条直径的端点。

✅ 举例说明

1 - 2 - 3 - 4 - 5 - 6
            |
            7

• 树的直径是从 1 到 6，长度为 5。
• 任意节点（如 3、4、7）的最远点一定是 1 或 6（直径端点之一）。

🔚 总结

在无边权的树上，任意点的最远点一定是某条直径的端点。

• 两次 BFS 求直径；
• 树的重心判定；
• 树上最长路径分析等。

树上，要使所有点到 u 的最长路最短，u 为什么一定是直径中点？直径中点有几个？

1. 记号与定义

• 树为 $T=(V,E)$，无边权。
• 直径端点记为 $s,t$，且
  $$D \;=\;\mathrm{dist}(s,t)$$
  是树的直径长度。
• 对任意节点 $u$，定义其 eccentricity
  $$e(u)\;=\;\max_{v\in V}\mathrm{dist}(u,v).$$
• 我们要选取一个节点 $u^*$ 使得
  $$e(u^*) \;=\;\min_{u\in V} e(u).$$

2. 为什么最优 $u^*$ 在直径路径上

1. 任何节点的最远点必在 $\{s,t\}$： 上一问已证明，对任意 $u$，
   $$e(u) =\max_{v\in V}\mathrm{dist}(u,v) =\max\bigl(\mathrm{dist}(u,s),\,\mathrm{dist}(u,t)\bigr).$$
2. 因此，
   $$e(u) =\max\bigl(\mathrm{dist}(u,s),\,\mathrm{dist}(u,t)\bigr) \;=\;\text{在路径 }s\!\to\!t\text{ 上测量到端点的最大值}.$$
3. 要让这个最大值尽可能小，自然将 $u$ 放在路径 $s\!\to\!t$ 上，且尽量 “居中”——也就是距离 $s$ 与 $t$ 的距离都不要太大。

3. 中点的具体位置

• 若 $D$ 为偶数，令 $k = D/2$，则唯一本节点
  $$v_k$$
  即为唯一的中点，此时
  $$\mathrm{dist}(v_k,\,s) =\mathrm{dist}(v_k,\,t) =\tfrac{D}{2}, \quad e(v_k)=\tfrac{D}{2}.$$
• 若 $D$ 为奇数，令 $k = \lfloor D/2\rfloor$，则有 两个相邻节点
  $$v_k,\;v_{k+1}$$
  都可以使得
  $$\max\bigl(\mathrm{dist}(v_i,s),\,\mathrm{dist}(v_i,t)\bigr) =\Bigl\lceil \tfrac{D}{2}\Bigr\rceil =k+1, \quad i=k\text{ 或 }k+1.$$
  这两个节点都是最优解。

4. 结论

1. 最优节点 $u^*$ 必在直径路径 $\overline{st}$ 的中点上。
2. 中点的个数：
   • 若直径长度 $D$ 为偶数，恰有 1 个中点；
   • 若 $D$ 为奇数，恰有 2 个中点（它们互为邻居）。

这也正是“树的中心”（tree center）的定义：要使所有点到中心的最大距离最小，中心正好是直径的中点，且至多两个。