树的直径实例讲解

首先先介绍一下什么是树的直径，树的直径，又称树的最长链，定义为一棵树上最远的两个节点的路径，即树上一条不重复经过某一条边的最长的路径。树的直径也可以代指这条路径的长度，总的来说树的直径就是树中所有最短路经距离的最大值。

求树的直径有两种比较常用的方法：一种是通过两次搜索（bfs和dfs均可），另一种就是通过树形dp来求了。接下来会对两种方法都进行讲解。

先来介绍一下用两次深搜来求树的直径：

先从图上任意一点，搜索整棵树，找到距离该点最远的点，再用距离该点最远的点搜索一次，即可得到树的直径。

现在来给出证明：

图像说明，两个椭圆形代表抽象子树，使得结论具有一般性：

由直径的定义我们可以知道由直径的一个端点搜索出的最大距离一定是直径的长度，那么我们现在就要证明由图中随机的一个点搜索出来的最远点一定是直径的一个端点，下面主要用反证法来证明。

以下图形均假设e1 e2为直径两端点

第一种情况，我们一开始所选取的点在直径上

我们一开始选定的点是e0，假如通过e0搜到的距离最远的点是e3，则说明

d（e0，o）+d（o，e3）>= d（e0，o）+d（o，e2），等价于

d（o，e3）>= d（o，e2）则 d（e1，o）+d（o，e3）>= d（e1，o）+d（o，e2）这与e1，e2是直径的两个端点矛盾，故不成立

第二种情况：我们一开始所选取的点不在直径上，且e0与e3与直径不相交，设直径上的o点与e0，e3路径上的e4点相交

则d（e0，e4）+ d（e4，e3）>= d（e0，e4）+ d（e4，o）+d（o，e2）

等价于 d（e4，e3）>= d（e4，o）+d（o，e2）

则d（e1，o）+  d（o，e4）+ d（e4，e3）>=d（e1，o）+ d（o，e2）

这与e1，e2是直径的两个端点矛盾，故不成立

最后一种情况：我们一开始所选取的点不在直径上，且e0与e3与直径相交，不妨设交点为o

则d（e0，o）+d（o，e3）>= d（e0，o）+d（o，e2），等价于

d（o，e3）>= d（o，e2）则 d（e1，o）+d（o，e3）>= d（e1，o）+d（o，e2）

这与e1，e2是直径的两个端点矛盾，故不成立

希望大家好好理解这个图，在以后的很多关于树的直径的题目中的结论证明方法都类似于上面的证明方法。

核心代码：

void dfs(int x,int father)
{
	for(int i=h[x];i!=-1;i=ne[i])//用链式前向星存树
	{
		int j=e[i];
		if(j==father) continue;//树是一种有向无环图，只要搜索过程中不返回父亲节点即可保证不会重复遍历同一个点。
		d[j]=d[x]+w[i];//更新每个点到起始点的距离（在树中任意两点的距离是唯一的）
		dfs(j,x);//继续搜索下一个节点
	}
}

ll ans=-1;
	for(int i=1;i<=n;i++)
		if(d[i]>ans)
		{
			ans=d[i];
			e=i;记录与搜索点距离最远的点
		}

下面我来介绍一下树形dp来求树的直径：

不难想到，距离直径上的一个点最远的点和次远的点一定是直径的两个顶点，所以我们只要能找到距离每一个点的最远距离和次远距离不就能找到树的直径了么，但是有一点需要注意，就是距离一个点的最远距离和次远距离不能与重合部分。下面我来对具体实现方面展开说明。

我们需要开两个数组F1[]和F2[]分别记录到某个点的最远距离和次远距离，这样我们最后把每个点的两个数组相加取个最大值就可以找到树的直径了。

核心代码：

void dp(int x,int father)
{
	for(int i=h[x];i!=-1;i=ne[i])链式前向星存树
	{
		int j=e[i];
		if(j==father) continue;//防止原路返回
		dp(j,x);//dp过程应该是由叶节点开始的，也就是说先递归到叶节点再开始进行状态转移
		if(f1[x]<f1[j]+w[i])//如果子节点的最大距离+子节点与父节点之间边的权重大于父节点的最大距离，那么父节点的最大距离和次大距离都要得到相应更新
		{
			f2[x]=f1[x];
			f1[x]=f1[j]+w[i];
		}
		else if(f2[x]<f1[j]+w[i])//若子节点的最大距离+子节点与父节点之间边的权重小于父节点的最大距离，再判断与父节点的次大距离的关系
			f2[x]=f1[j]+w[i];
		ans=max(ans,f1[x]+f2[x]);//在搜索过程中找到树的直径
	}
}