1. 问题描述

给定一棵树，求树中最长的路径的长度，也就是树的直径；
该树的节点数为 $n$ ，编号为 $0, 1, \cdots, n-1$ ；
定义树中某一个节点 $v$ 的相邻节点为 $g[v]$ ；

2. 求解方法

从 $n$ 个节点中随机选择一个节点，假设为 $f$ ；
在树中找一条以 $f$ 为起点的最长路径；该方法可以用深度优先搜索的方法做（详细描述见下文[4]）；
假设找到的路径的另外一个端点为 $s$ ，那么树中以 $s$ 为起点的最长的路径的长度便是树的直径

3. 证明

假设一颗树如下图所示：

树

再假设，第一个节点选择的是节点 $1$ ，以节点 $1$ 为起点的最长的路径是 $1 \to 2 \to 3 \to 4 \to \cdots \to 6$ 。基于上述假设，要证明上述方法正确，即证明：

节点 $1$ 或 $6$ 是某条最长路径的一个端点。

要证明上述结论，假设某一个节点 $u$ 是树中某一个最长路径的端点，该路径为 $l$ ，有如下结论：

节点 $u$ 不是 $2 \to 3 \to \cdots$ 中的一个（不包括节点 $6$ ）：如果是，那么肯定存在更长的一条路径；
与重叠一边，且重叠部分为靠近节点的那边，证明方法为：
- 如果 $l$ 与 $1 \to 2 \to \cdots \to 6$ 完全不相交，那么 $l$ 可能是 $7 \to \cdots \to 5 \to \cdots \to 8$ 这种路径，此时可以找到比 $l$ 更长的路径。
- 如果 $l$ 与 $1 \to 2 \to \cdots \to 6$ 相交于某一个节点，此时也可以找到比 $l$ 更长的路径。

上述例子可以扩展成一般的情况。因此，上述结论成立，从而上述方法正确。

4. 给定某一个节点求解树中离这个节点最远的节点以及对应路径长度

使用DFS可以解决这个问题。

定义 dfs(v) 的含义为，返回范围以节点 $v$ 为根的子树中距离最远的节点以及对应的长度。

def dfs(v):
  max_dis = 0
  max_node = v
  for u in child(v):
    update_node, update_dis = dfs(u) + 1
    if update > max_dis:
      max_dis = update_dis
      max_node = update_node
  return max_node, max_dis

通过上述递归的方法就可以求出对应的节点，以及具体的距离。