树的直径

树的直径，即树中距离最远的两个节点的距离。

求解方法

选取树中的任意一个节点，计算距离它最远的节点（使用DFS或者BFS），然后以这个最远的节点为根计算距离它最远的节点。这段距离即为树的直径，根和此最远的点便是两个端点。

简单证明

其实只要证明：以任意点为根节点，距离此根节点最远的节点必定是树的直径中的一个端点。

证明了这个，那么上面提到的算法就很容易证明了，获取第一个端点，然后以此端点为根的最远端点就是另外一个端点。

首先规定从r开始的最远距离节点为u，证明u为树的直径的一个端点，可以使用反证法证明，假设存在另外两个节点s,t，构成了树的直径。

1. st的路径和ru不相交：

   在这种情况下，存在\(dis(u,s)+dis(s,t) > dis(s,t)\)，所以st并不是最长的，和假设相矛盾，st这种情况下不存在

2. st的路径和ru相交于点v：

   此时s,u都是以a为根的子树上的节点，因为u为距离a最远的结点所以可得： \[ dis(a,y)+dis(y,u) > dis(a,y)+dis(y,s) \\ 即：dis(u,y) < dis(s,y) \] 同样表示s,t并不是最长的，而是u,t

综上，u必定为树的直径的一个端点。

关于树的直径的更多性质可参考：博客园 树的直径及其性质与证明