1395. 树的直径

给一棵树,求它的直径。

图中所有最短路径的最大值即为「直径」。

  • 对任意一个结点做 DFS 求出最远的结点,到达的结点一定是直径 的一端。
  • 以这个结点为根结点再做 DFS 到达另一个最远结点,到达的结点 一定是直径的另一端。

输入

第一行一个整数 n \ (1 \leq n \leq 2 \times 10^5) ,结点数量。

接下来 n-1 行,每行两个整数 u,v \ (1 \leq u,v \leq n),表示 uv 之间有一条边。

输出

一个数,表示树的直径。

样例

标准输入 复制文本
3
3 2
2 1
标准输出 复制文本
2
标准输入 复制文本
1
标准输出 复制文本
0
登录以提交代码。
单点时限 1 秒
内存限制 256 MB
提交 114
通过 59