樹直徑

概念

樹直徑就是指樹上最遠的點對的距離，更仔細的說，假設有一個函式 $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 檢定中也曾經直接出現過樹直徑的裸題！