【藍橋杯】 試題 演演算法提高 樹的直徑 （dfs）

資源限制

時間限制：100ms 記憶體限制：8.0MB

問題描述

樹的直徑

輸入格式

輸入的第一行包含一個整數n，表示樹中的點數。接下來n-1行，每行3個正整數，表示連同的兩點及邊的權值。

輸出格式

輸出1行，包含一個整數，表示樹的直徑。

樣例輸入

7
1 2 1
1 3 1
2 4 1
3 5 1
4 7 1
4 6 1

樣例輸出

5

資料規模和約定

n<10^5

---

思路：

樹的直徑：找相距最遠兩點之間的距離，即為樹的直徑。

從任一點出發，找到距離該點最遠的點 p1， p1 必定為直徑的一個端點。 (跑一遍dfs)

從p1出發，找到距離p1最遠的點p2，p2必定為直徑的另一個端點，所以p1，p2兩點連線是相距最遠的兩點，即為樹的直徑。 （再跑一遍dfs）

---

程式碼：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std; 
const int maxn=1e5+10;

struct node{
	int v,w; 
	node(int a,int b){v=a;w=b;}
};

int n,a,b,c,p1,maxlen=0;
vector<node> g[maxn];  //圖
bool vis[maxn]={false}; //是否走過

void dfs(int u,int dis)
{
	if(dis>maxlen) //更新最遠距離和最遠點
	{
		maxlen=dis;
		p1=u;
	}
	
	for(int i=0;i<g[u].size();i++) 
	{
		int v=g[u][i].v;
		int w=g[u][i].w;
		if(!vis[v]) //沒存取過
		{
			vis[v]=1;
			dfs(v,dis+w);
			vis[v]=0; //回溯
		}
	}
}

int main()
{
	cin>>n;
	for(int i=0;i<n-1;i++)
	{
		cin>>a>>b>>c;
		g[a].push_back(node(b,c));
		g[b].push_back(node(a,c));
	}
	
	vis[1]=1;
	dfs(1,0); //從任一點出發，這裡從1出發
	vis[1]=0;
	
	maxlen=0; // 最遠距離
	
	vis[p1]=1;
	dfs(p1,0); //從p1出發，能最遠距離就是樹的直徑
	vis[p1]=0;
	
	cout<<maxlen;
    return 0;
}