学习博客：https://www.cnblogs.com/ywjblog/p/9254997.html

树的直径
给定一棵树，树中每条边都有一个权值，树中两点之间的距离定义为连接两点的路径边权之和。树中最远的两个节点之间的距离被称为树的直径，连接这两点的路径被称为树的最长链。后者通常也可称为直径，即直径是一个?
数值概念，也可代指一条路径
树的直径通常有两种求法，时间复杂度均为O(n)。我们假设树以N个点N-1条边的无向图形式给出，并存储在邻接表中。

第一种是dp求法，在这里我只介绍bfs求法：

两次BFS（DFS）求树的直径
通过两次BFS或者两次DFS也可以求树的直径，并且更容易计算出直径上的具体节点
详细地说，这个做法包含两步：
1.从任意节点出发，通过BFS和DFS对树进行一次遍历，求出与出发点距离最远的节点记为p
2.从节点p出发，通过BFS或DFS再进行一次遍历，求出与p距离最远的节点，记为q。
从p到q的路径就是树的一条直径。因为p一定是直径的一端，否则总能找到一条更长的链，与直径的定义矛盾。显然地脑洞一下即可。p为直径的一端，那么自然的，与p最远的q就是直径的另一端。
在第2步的遍历中，可以记录下来每个点第一次被访问的前驱节点。最后从q递归到p，即可得到直径的具体方案

下面看一道例题：

题目链接：https://ac.nowcoder.com/acm/contest/884/A

链接：https://ac.nowcoder.com/acm/contest/884/A
来源：牛客网