概念#
樹直徑就是指樹上最遠的點對的距離，更仔細的說，假設有一個函式 \(dist(x, y)\) 代表節點 \(x\) 與節點 \(y\) 的簡單路徑距離，那數直徑就可以這樣表示：
\(max_{1 \leq v, u \leq n} dist(u, v)\)
以這張圖為例：
可以看到 1 和 2 的簡單路徑長度為 3，然後 3 到 4 的簡單路徑程度為 2，而我們要找的樹直徑是 2 到 4 這條距離為 4 的最長路徑。
實作方式#
樹直徑的實作方式其實不只一種，而其中簡單的做法就是透過兩次 DFS，那要怎麼透過 DFS 找到樹直徑呢？
具體來說，我們需要執行以下兩個步驟：
- 從任意點開始做 DFS 並找到最遠的那個點 \(x\)
- 接著把 \(x\) 當起點繼續做一次 DFS 找到距離點 \(x\) 最遠的點 \(y\)
如此一來，\(x\) 與 \(y\) 的句離就是樹直徑了！
void dfs(int v, int d = 0) {
vis[v] = true;
// 如果深度超過目前最大深度就更新
if (d > maxdeep) {
// 把最遠的點記錄在 deep 變數中
deep = v;
maxdeep = d;
}
for (auto e : tree[v]) {
if (vis[e]) continue;
vis[e] = true;
dfs(e, d + 1);
}
}
int main() {
dfs(1); // 第一次從任意點開始找到最遠的點
memset(vis, 0, sizeof(vis));
maxdeep = -1;
dfs(deep); // 第二次從最遠的點開始找到另外一個最遠的點
cout << maxdeep << endl; // 最後 maxdeep 就是樹直徑
}
雖然可能看似沒什麼用，不過這是非常經典的問題，APCS 檢定中也曾經直接出現過樹直徑的裸題！
