树的直径

树的直径

树的直径即是树中相距最远的两个点的距离。相距最远指的是两点间的最短路径的距离最远。

算直径有两种方法

DFS

• 任取起点，先做一次DFS，找到距离最远的点，这个点一定是直径的一部分。
• 从这个点开始再做一次DFS，找到离它最远的点，这两个点就组成了直径

树上DP

假设f1[x],f2[x]分别是x到其子树的叶子节点距离的最大值和次大值。j是i的直接后继，则有：

• 如果f1[i] < f1[j] + w[i, j]则f2 [ i ] = f1 [ i ]，f1 [ i ] = f1 [ j ] + w [ i ][ j ]
• 否则，若 f2 [ i ] < f1 [ j ] + w [ i ][ j ]，则f2 [ i ] = f1 [ j ] + w [ i ][ j ]；

最后，直径就是 $max(f1[i]+f2[i])$

核心代码

void dp(int x,int father)
{
	int i,j;
	for(i=first[x];i;i=next[i])
	{
		j=v[i];
		if(j==father)
		  continue;
		dp(j,x);
		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]);
	}
}