树的直径及其相关知识

对于一棵树 \(T\)，我们定义 \(T\) 中最长的链为 \(T\) 的直径，显然，直径可以有多条。

如果 \(T\) 中的边权非负，那么 \(\forall u \in T\)，都满足：\(u\) 为起点的最长链的终点一定是某条直径的端点。

还有另一个结论：假设 \(u\) 为起点的最长链的长度为 \(L\)，那么对于任何一条直径的两个端点 \(p\) 和 \(q\)，都必然有 \(\max(dis(u,p),dis(u,q))=L\)。

两个结论可以一起证明：

考虑先随便拉一条直径，然后我们把树变成以这条链为“根”，每个点上挂一个子树的形态。

然后我们可以按长为 \(L\) 的链的端点 \(v\) 的位置分类讨论，容易得到两个结论：

• 如果 \(\max(dis(u,p),dis(u,q))<L\)，那么必然存在比 \(u \to v\) 更长的链，矛盾。
• 如果 \(\max(dis(u,p),dis(v,p))=L\)，那么必然存在一条以 \(v\) 为端点的直径。

若所有边权均正，则所有直径的中点重合于一点。