---
tags: CSES題解
---

CSES Problem Set — Tree Diameter 題解
===

題目
---
給一顆有$n$個節點的樹。
定義樹的直徑為，樹中任兩點的最大距離，你的任務是找出這棵樹的直徑。

### 輸入
第一行輸入包含一個整數$n$ : 節點的數量。這些節點編號為$1,2,\ldots,n$。
接下來有$n-1$描述邊。每一行包含兩個整數$a$和$b$ : 點$a$和$b$間有一條邊。

### 輸出
輸出一個整數 : 樹的直徑。

想法 1 :兩次DFS
---
從任一點``DFS``後，距離他最遠點必是樹直徑的一端([詳細證明在這](https://codeforces.com/blog/entry/101271))，再從最遠的這個點``DFS``找到另一個最遠的點就是樹的直徑。

***此方法只適用在邊權皆為正的情況下***
此題邊權皆為+1，因此適用

範例程式碼
---

#include<bits/stdc++.h>
#define int long long
using namespace std;
int cnt=1;
vector<int> Head(200500,0);
vector<int> Next(400500);
vector<int> To(400500);
void addEdge(int u,int v){
    Next[cnt]=Head[u];
    To[cnt]=v;
    Head[u]=cnt++;
}
/*************鍊式前向星建圖****************/

int farn;
int maxd=-1;
void dfs(int n,int par,int d){
	if(d>maxd){ //更新最遠點
		maxd=d;
		farn=n;
	}
	for(int e=Head[n];e;e=Next[e]){
        int x=To[e];
		if(x!=par){
			dfs(x,n,d+1);
		}
	}
}
signed main(){
	int n;
	cin>>n;
	for(int i=0;i<n-1;i++){
		int a,b;
		cin>>a>>b;
		addEdge(a,b);
        addEdge(b,a);
	}
	dfs(1,0,0); //找到直徑一端
	maxd=-1;
	dfs(farn,0,0); //從一端找到直徑
	cout<<maxd<<'\n';
	return 0;
}

想法 2 : 樹形dp
---
如果題目給的樹有負邊權，上述方法就無法正確找出樹的直徑，只能透過其他方法來找直徑，最常見的方法是dp。

我們需要兩個狀態陣列``dist``和``ans``:前者表示一點**開始往下走**的最大距離，後者表示以此點為根節點的子樹的最大距離。

對於一點$x$，先設定``dist[x]``和``ans[x]``為$0$，遞迴完一顆子樹$u$時，**先更新**``ans[x]=max(ans[x],ans[v],dist[x]+dist[u]+x到u的邊權)``
(dist[x]是另一條往下路徑的最大距離，由該路徑通過$x$點再由$u$往下最大距離和原先ans[x]、子節點ans[u]比較取大)，

再更新 ``dist[x]=max(dist[x],dist[u]+x到u的邊權)``，

最後答案就會是根節點的ans。

***ans和dist的更新順序很重要***
相反的話可能會計算到重覆路徑。

範例程式碼
---

#include<bits/stdc++.h>
#define int long long
using namespace std;
int cnt=1;
vector<int> Head(200500,0);
vector<int> Next(400500);
vector<int> To(400500);
vector<int> dist(200500,0);
vector<int> ans(200500,0);
void addEdge(int u,int v){
    Next[cnt]=Head[u];
    To[cnt]=v;
    Head[u]=cnt++;
}
/*************鍊式前向星建圖****************/

void dfs(int n,int par){
	for(int e=Head[n];e;e=Next[e]){
        int v=To[e];
        if(v!=par){
            dfs(v,n);
            //先更新ans
            ans[n]=max({ans[v],ans[n],dist[n]+dist[v]+1});
            //再更新dist
            dist[n]=max(dist[n],dist[v]+1);
        }
    }
}
signed main(){
	int n;
	cin>>n;
	for(int i=0;i<n-1;i++){
		int a,b;
		cin>>a>>b;
		addEdge(a,b);
        addEdge(b,a);
	}
    dfs(1,1);
    cout<<ans[1]<<'\n';
	return 0;
}