树上任意两节点之间最长的简单路径即为树的「直径」。
显然，一棵树可以有多条直径，他们的长度相等。
可以用两次 DFS 或者树形 DP 的方法在 O(n) 时间求出树的直径。
两次DFS
这是一种非常容易理解的方法
从树上任意一点出发，进行 dfs ，记其所能到达最远的点（即所经路径之和最大）为 k1
再从 k1 点出发进行 dfs ，记其所能到达最远的点（即所经路径之和最大）为 k2
那么 k1 , k2 之间的路径即为树的直径
树形DP
这里介绍树形 DP 方法
首先观察以下图
现在取任意一点，将其所能经过的最长路径与次长路径（与最长路径无公为共边）记录下来，那么
- 如果该点位于直径上，那么两者之和即为路径长
- 如果该点不位于直径上，那么该点的两者之和一定小于直径长
这里从一个点出发所能到达的最长和次长路径的终点 相当于（尝试）碰到 k1, k2两点
为了便于操作，我们定义当 1 为树的根时，将每个节点作为其子树的根，向下所能延伸的最长路径长度为 d1 ，次长路径（与最长路径无公为共边）长度为 d2，那么直径就是对于每一个点，该点 d1 + d2 能取到的值中的最大值。
记f1[]为最长距离,f2[]为次长距离
树形dp求直径
void dp(int x,int fa)
{
for(int i=head[x];i!=-1;i=e[i].next)链式前向星存树
{
int v=e[i].to;
if(v==fa) continue;//防止原路返回
dp(v,x);//dp过程应该是由叶节点开始的，也就是说先递归到叶节点再开始进行状态转移
if(f1[x]<f1[j]+e[i].w)//如果子节点的最大距离+子节点与父节点之间边的权重大于父节点的最大距离，那么父节点的最大距离和次大距离都要得到相应更新
{
f2[x]=f1[x];
f1[x]=f1[j]+e[i].w;
}
else if(f2[x]<f1[j]+e[i].w)//若子节点的最大距离+子节点与父节点之间边的权重小于父节点的最大距离，再判断与父节点的次大距离的关系
f2[x]=f1[j]+e[i].w;
ans=max(ans,f1[x]+f2[x]);//在搜索过程中找到树的直径
}
}