# DFS/BFS 兩次找樹直徑與其證明

## 問題描述

給一棵 [樹](https://zh.wikipedia.org/zh-tw/樹_(圖論))，每條邊都有權重，定義一條路徑的長度為該路徑上每條邊的權重和。

樹上的任何最長長度的簡單路徑都是此樹的直徑。

現在請你找到此樹上的任意一條直徑。

## 演算法

任選一點(令其為 $x$)出發，做一次 DFS 或 BFS 找到樹上離 $x$ 最遠的點 $y$，可證明點 $y$ 一定是某條直徑到其中一個端點，所以再從點 $y$ 出發做一次 DFS/BFS 找到離點 $y$ 最遠的點 $z$，那麼點 $y$ 和點 $z$ 形成的路徑就是直徑。

## 參考程式碼

可測試題目：[TIOJ1213. 樹論 之 最遠距點對](https://tioj.ck.tp.edu.tw/problems/1213)

1. DFS 的寫法

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int SIZE = 1 << 20;
struct Data{
    int y;
    long long d;
    bool operator<(const Data& b) const {
        return d < b.d;
    }
};
vector<Data> e[SIZE];
int an[SIZE];
// 呼叫 dfs(x, lt, d) 代表從起點 DFS 後，目前走到點 x，上一個走的點是 lt，且已走過的邊數為 d
// 最終會回傳的 Data 為 {最遠的點的編號, 離起點最遠的點的距離}
Data dfs(int x, int lt, long long dis) {
    Data result = {x, dis};
    for(auto node: e[x]) {
        if(node.y == lt) continue;
        result = max(result, dfs(node.y, x, node.d + dis));
    }
    return result;
}
int main() {
    int n;
    cin >> n;
    for(int i = 1; i < n; i++) {
        int x, y, v;
        cin >> x >> y >> v;
        e[x].push_back({y, v});
        e[y].push_back({x, v});
    }
    int y = dfs(1, 1, 0).y;
    cout << dfs(y, y, 0).d << '\n';
}

2. BFS 的寫法：

#include <bits/stdc++.h>
using namespace std;

/* ------------ 常數與型別 ------------ */
const int MAX_N = 100'001;
// n ≤ 100 000（CSES 的限制），多開 1 個位置方便 1‑based index
struct Edge {
    int to;
    int w;
}; // to：鄰點編號，w：邊權
struct Data {       // 用來回傳「最遠點」資訊
    int id;         // 點編號
    long long dist; // 與起點距離
};

vector<Edge> G[MAX_N];    // 無向樹的鄰接串列
long long distArr[MAX_N]; // BFS 途中儲存距離
int parentArr[MAX_N];     // BFS 時的父節點（避免回頭）
/* ----------------------------------- */

/* --------------------- 單源 BFS：回傳離 start 最遠的點 --------------------
 * 由於樹中任兩節點之間的路徑唯一，只要「走到鄰點時把邊權加進去」，
 * 就能正確算出距離；整體複雜度 O(n)。
 */
Data bfs(int start, int n) {
    queue<int> que;
    /* 初始化起點 */
    fill(distArr + 1, distArr + n + 1, -1); // -1 代表尚未造訪
    que.push(start);
    distArr[start] = 0;
    parentArr[start] = 0;

    Data farthest{start, 0};

    while (!que.empty()) {
        int u = que.front();
        que.pop();

        for (const auto &e : G[u]) {
            int v = e.to;
            if (v == parentArr[u]) continue; // 不回頭
            parentArr[v] = u;
            distArr[v] = distArr[u] + e.w;
            que.push(v);

            /* 即時更新目前最遠點 */
            if (distArr[v] > farthest.dist)
                farthest = {v, distArr[v]};
        }
    }
    return farthest;
}

/* ----------------------------- 主程式 ----------------------------- */
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    // 讀取多組測資；當 n 為 0 時代表輸入結束
    while (cin >> n && n) {
        for (int i = 1; i <= n; i++) G[i].clear(); // 每組測資都必須重新初始化
        for (int i = 1; i < n; ++i) {
            int a, b, w;
            cin >> a >> b >> w;
            G[a].push_back({b, w});
            G[b].push_back({a, w});
        }

        /* 第一次 BFS：任取 1 為根，找出最遠點 u */
        int u = bfs(1, n).id;
        /* 第二次 BFS：由 u 出發，最遠距離即為樹的直徑 */
        long long diameter = bfs(u, n).dist;

        cout << diameter << '\n';
    }
    return 0;
}

## 證明

定義 $P(x, y)$ 代表以點 $x$ 和點 $y$ 為端點的簡單路徑，$dis(x, y)$ 為 $P(x, y)$ 的長度。

我們只需證明，對於任一個點 $x$ 當作此樹的樹根，那麼距離點 $x$ 最遠的任一個葉子一定是某條直徑的端點即可。

使用反證法，令其中一個距離 $x$ 最遠的葉子為 $y$，假設 $y$ 並非任何一條直徑的端點。並假設 $P(u, v)$ 是某條直徑的兩個端點，那麼有以下兩種情況：


1. $P(u, v)$ 和 $P(x, y)$ 至少有一個交點：
在此種情況時，令 $c$ 是它們的交點中，離 $x$ 最遠的點， $P(u, c)$ 和 $P(v, c)$ 一定有其中一條是完全在點 $c$ 的子樹裡，不妨假設是 $P(v, c)$ 在點 $c$ 的子樹裡，那麼 $dis(v, c) \le dis(v, y)$ 必成立(因為 $y$ 是距離 $x$ 最遠的葉子)，也就是說，把 $P(u, v)$ 中 $P(c, v)$ 的部分取代為 $P(c, y)$，所得到的 $P(u, y)$ 必滿足 $dis(u, y) \ge dis(u, v)$，所以 $P(u, y)$ 也會是直徑，和假設矛盾。
2. $P(u, v)$ 和 $P(x, y)$ 沒有交點：
令 $c$ 為 $u$ 和 $v$ 的 LCA，也就是 $P(u, v)$ 中距離 $x$ 最近的點，類似於上一種，$dis(c, y) \ge dis(c, v)$ 必成立，所以 $dis(u, y) \ge dis(u, v)$，所以 $P(u, y)$ 也會是直徑，和假設矛盾。

在由於在兩種情況都矛盾，所以 $y$ 必定是某條直徑的端點。

## 參考資料

[SA 流 C++ 競程修煉心法](https://hackmd.io/@sa072686/cp/%2F%40sa072686%2FBJ_IFasdS)