树的直径

一、树的直径的定义：最长的一条链。

二、求法
1．两次bfs（或者dfs）求树的直径
优点：可以求出路径。
缺点：时间复杂度O(2*N)， 在负权边中无法使用。

方法：先从任意一点出发，找离它最远的点P，再从点P出发，找离它最远的点Q，P到Q的距离就是树的直径。

代码：

inline void dfs(int u, int f, int & tar)
{
	int v;
	for(int e = hd[u]; e; e = nt[e])
	    if((v = to[e]) ^ f)
	    {
	    	dis[v] = dis[u] + w[e];
	    	if(dis[v] > dis[tar]) tar = v;
	    	dfs(v, u, tar);
		}
}

dfs(1, 0, p);
dis[p] = 0;
dfs(p, 0, q);

2、树型DP求树的直径
优点：可以求出以当前节点为根时的最长链，支持边为负权，时间复杂度O(N)。
缺点：不能求出最长链的路径。

方法：对于每个节点我们要记录两个值：
\(f_{1_i}\) 表示以i为根的子树中，i到叶子结点距离的最大值
\(f_{2_i}\) 表示以i为根的子树中，i到叶子结点距离的次大值
对于一个节点，它到叶子结点距离的最大值和次大致所经过的路径肯定是不一样的
若j是i的儿子，那么（下面的 \(w_{i,j}\) 表示i到j的路径长度）：
（1）若 \(f_{1_i}\) < \(f_{1_j}\) + \(w_{i,j}\) ， \(f_{2_i}\) = \(f_{1_i}\) ， \(f_{1_i}\) = \(f_{1_j}\) + \(w_{i,j}\) ；
（2）否则，若 \(f_{2_i}\) < \(f_{1_j}\) + \(w_{i,j}\) ， \(f_{2_i}\) = \(f_{1_j}\) + \(w_{i,j}\) ；
理解：这样做就是，先看能否更新最大值，若能，它的次大值就是原先的最大值，再更新它的最大值；若不能，就看能不能更新次大值，若能，就更新，不能就不管它
这样的话，最后的答案 \(ans = max\) {\(f_{1_i} + f_{2_i}\)}

代码：

inline void dp(int u, int fa)            
{ 
    int v;
  	for(int e = hd[u]; e; e = nt[e])     
  		if((v = to[e]) ^ fa)
 		{    
    		dp(v, u);                  
    		if(f1[u] < f1[v] + w[e])      
    		{ 
      			f2[u] = f1[u];             
      			f1[u] = f1[v] + w[e];        
    		}	 
    		else if(f2[u] < f1[v] + w[e])    
            	f2[u] = f1[v] + w[e];
			//依次更新最大、次大，不能就不管它 
    		ans = max(ans, f1[u] + f2[u]);    
  		} 
}