首先先介紹一下什么是樹(shù)的直徑，樹(shù)的直徑，又稱樹(shù)的最長(zhǎng)鏈，定義為一棵樹(shù)上最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)的路徑，即樹(shù)上一條不重復(fù)經(jīng)過(guò)某一條邊的最長(zhǎng)的路徑。樹(shù)的直徑也可以代指這條路徑的長(zhǎng)度，總的來(lái)說(shuō)樹(shù)的直徑就是樹(shù)中所有最短路經(jīng)距離的最大值。

求樹(shù)的直徑有兩種比較常用的方法：一種是通過(guò)兩次搜索（bfs和dfs均可），另一種就是通過(guò)樹(shù)形dp來(lái)求了。接下來(lái)會(huì)對(duì)兩種方法都進(jìn)行講解。

先來(lái)介紹一下用兩次深搜來(lái)求樹(shù)的直徑：

先從圖上任意一點(diǎn)，搜索整棵樹(shù)，找到距離該點(diǎn)最遠(yuǎn)的點(diǎn)，再用距離該點(diǎn)最遠(yuǎn)的點(diǎn)搜索一次，即可得到樹(shù)的直徑。

現(xiàn)在來(lái)給出證明：

圖像說(shuō)明，兩個(gè)橢圓形代表抽象子樹(shù)，使得結(jié)論具有一般性：

由直徑的定義我們可以知道由直徑的一個(gè)端點(diǎn)搜索出的最大距離一定是直徑的長(zhǎng)度，那么我們現(xiàn)在就要證明由圖中隨機(jī)的一個(gè)點(diǎn)搜索出來(lái)的最遠(yuǎn)點(diǎn)一定是直徑的一個(gè)端點(diǎn)，下面主要用反證法來(lái)證明。

以下圖形均假設(shè)e1 e2為直徑兩端點(diǎn)

第一種情況，我們一開(kāi)始所選取的點(diǎn)在直徑上

我們一開(kāi)始選定的點(diǎn)是e0，假如通過(guò)e0搜到的距離最遠(yuǎn)的點(diǎn)是e3，則說(shuō)明

d（e0，o）+d（o，e3）>= d（e0，o）+d（o，e2），等價(jià)于

d（o，e3）>= d（o，e2）則 d（e1，o）+d（o，e3）>= d（e1，o）+d（o，e2）這與e1，e2是直徑的兩個(gè)端點(diǎn)矛盾，故不成立

第二種情況：我們一開(kāi)始所選取的點(diǎn)不在直徑上，且e0與e3與直徑不相交，設(shè)直徑上的o點(diǎn)與e0，e3路徑上的e4點(diǎn)相交

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

等價(jià)于 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是直徑的兩個(gè)端點(diǎn)矛盾，故不成立

最后一種情況：我們一開(kāi)始所選取的點(diǎn)不在直徑上，且e0與e3與直徑相交，不妨設(shè)交點(diǎn)為o

則d（e0，o）+d（o，e3）>= d（e0，o）+d（o，e2），等價(jià)于

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

這與e1，e2是直徑的兩個(gè)端點(diǎn)矛盾，故不成立

希望大家好好理解這個(gè)圖，在以后的很多關(guān)于樹(shù)的直徑的題目中的結(jié)論證明方法都類似于上面的證明方法。

核心代碼：

void dfs(int x,int father)
{
	for(int i=h[x];i!=-1;i=ne[i])//用鏈?zhǔn)角跋蛐谴鏄?shù)
	{
		int j=e[i];
		if(j==father) continue;//樹(shù)是一種有向無(wú)環(huán)圖，只要搜索過(guò)程中不返回父親節(jié)點(diǎn)即可保證不會(huì)重復(fù)遍歷同一個(gè)點(diǎn)。
		d[j]=d[x]+w[i];//更新每個(gè)點(diǎn)到起始點(diǎn)的距離（在樹(shù)中任意兩點(diǎn)的距離是唯一的）
		dfs(j,x);//繼續(xù)搜索下一個(gè)節(jié)點(diǎn)
	}
}

ll ans=-1;
	for(int i=1;i<=n;i++)
		if(d[i]>ans)
		{
			ans=d[i];
			e=i;記錄與搜索點(diǎn)距離最遠(yuǎn)的點(diǎn)
		}

下面我來(lái)介紹一下樹(shù)形dp來(lái)求樹(shù)的直徑：

不難想到，距離直徑上的一個(gè)點(diǎn)最遠(yuǎn)的點(diǎn)和次遠(yuǎn)的點(diǎn)一定是直徑的兩個(gè)頂點(diǎn)，所以我們只要能找到距離每一個(gè)點(diǎn)的最遠(yuǎn)距離和次遠(yuǎn)距離不就能找到樹(shù)的直徑了么，但是有一點(diǎn)需要注意，就是距離一個(gè)點(diǎn)的最遠(yuǎn)距離和次遠(yuǎn)距離不能與重合部分。下面我來(lái)對(duì)具體實(shí)現(xiàn)方面展開(kāi)說(shuō)明。

我們需要開(kāi)兩個(gè)數(shù)組F1[]和F2[]分別記錄到某個(gè)點(diǎn)的最遠(yuǎn)距離和次遠(yuǎn)距離，這樣我們最后把每個(gè)點(diǎn)的兩個(gè)數(shù)組相加取個(gè)最大值就可以找到樹(shù)的直徑了。

核心代碼：

void dp(int x,int father)
{
	for(int i=h[x];i!=-1;i=ne[i])鏈?zhǔn)角跋蛐谴鏄?shù)
	{
		int j=e[i];
		if(j==father) continue;//防止原路返回
		dp(j,x);//dp過(guò)程應(yīng)該是由葉節(jié)點(diǎn)開(kāi)始的，也就是說(shuō)先遞歸到葉節(jié)點(diǎn)再開(kāi)始進(jìn)行狀態(tài)轉(zhuǎn)移
		if(f1[x]<f1[j]+w[i])//如果子節(jié)點(diǎn)的最大距離+子節(jié)點(diǎn)與父節(jié)點(diǎn)之間邊的權(quán)重大于父節(jié)點(diǎn)的最大距離，那么父節(jié)點(diǎn)的最大距離和次大距離都要得到相應(yīng)更新
		{
			f2[x]=f1[x];
			f1[x]=f1[j]+w[i];
		}
		else if(f2[x]<f1[j]+w[i])//若子節(jié)點(diǎn)的最大距離+子節(jié)點(diǎn)與父節(jié)點(diǎn)之間邊的權(quán)重小于父節(jié)點(diǎn)的最大距離，再判斷與父節(jié)點(diǎn)的次大距離的關(guān)系
			f2[x]=f1[j]+w[i];
		ans=max(ans,f1[x]+f2[x]);//在搜索過(guò)程中找到樹(shù)的直徑
	}
}