前置知識

這題是圖論的入門經典，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

• 圖的儲存與 BFS：NTUCPC Guide〈圖論基礎〉——鄰接串列 vector<int> G[MAX_N]、用 BFS 算起點到每個點的距離（距離＝最少邊數）；吳邦一《AP325》第 7 章 7.2 也講同樣的兩件事（教材 PDF 第 222～227 頁；Python 版第 7 章（I））。
• 樹：NTUCPC Guide〈樹〉——樹是沒有環的連通圖，任兩點之間恰有一條路徑，所以 BFS 算出的距離就是那條路徑的邊數。
• 樹直徑：NTUCPC Guide〈樹的應用〉第一節——「最遠點的最遠點」兩次搜尋法，以及為什麼它是對的（證明在那裡，這裡不重講）；《AP325》第 8 章的 P-8-14 正是本題，兩種做法都有（PDF 第 307～310 頁；Python 版第 8 章（III））。

簡潔題意

\(n\) 個家族成員（編號 \(0 \sim n-1\)）、\(n-1\) 條「\(a\) 是 \(b\) 的父母」關係。兩人的距離＝沿著親子關係走過去要經過幾條邊（可以往上也可以往下走）。求所有兩兩之間最大的距離（\(2 \le n \le 10^5\)，輸入保證是一棵樹，祖先不一定是 \(0\)）。

依正確通過的測試資料筆數給分，其中：

• 子題組 1（\(10\) 分）：\(n \le 100\)，祖先至多兩個孩子、其他人至多一個孩子。
• 子題組 2（\(30\) 分）：\(n \le 100\)。
• 子題組 3（\(30\) 分）：\(n \le 2000\)。
• 子題組 4（\(30\) 分）：無額外限制。

把方向忘掉——「\(a\) 是 \(b\) 的父母」只代表 \(a\)、\(b\) 之間有一條邊——這 \(n\) 個人就是一棵 \(n\) 個點的樹，要求的是樹上最遠兩點的距離，也就是樹直徑。

先拿下 10 分：一條鏈的直徑就是 \(n - 1\)

子題組 1 的「祖先至多兩個孩子、其他人至多一個孩子」畫出來就是一條鏈（祖先在鏈的中間或一端）。鏈上最遠的兩個人是兩個端點，距離就是全部的邊數 \(n - 1\)：

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

int main() {
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {     // 子題組 1 保證是一條鏈：關係讀掉就好
        int a, b;
        cin >> a >> b;
    }
    cout << n - 1 << '\n';
    return 0;
}

兩個範例都不是鏈，這份程式交上去範例會 WA——這是正常的，逐筆給分之下子題組 1 的 \(10\) 分穩穩到手。

從 10 分到 70 分：每個人都當一次起點做 BFS

一般的樹要怎麼找最遠的兩個人？最直接的想法：每個人都當一次起點做 BFS，算出他到所有人的距離，取全部的最大值。先把 BFS 寫成一個函式：回傳「離起點最遠的人是誰、距離多少」，等一下滿分解也會直接拿來用。

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

const int MAX_N = 100005;
vector<int> G[MAX_N];              // 鄰接串列：G[u] 是 u 的所有鄰居
int n;

// 從 start 出發做 BFS，回傳 {最遠的人, 距離}
pair<int, int> farthest(int start) {
    vector<int> dist(n, -1);       // -1 代表還沒走到
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    int best = start;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (dist[u] > dist[best]) best = u;
        for (int v : G[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return {best, dist[best]};
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;                 // a 是 b 的父母：方向不重要，兩邊都存
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int ans = 0;
    for (int s = 0; s < n; s++)        // 每個人都當一次起點
        ans = max(ans, farthest(s).second);
    cout << ans << '\n';
    return 0;
}

一次 BFS 走過每條邊兩次、每個點一次，是 \(O(n)\)；做 \(n\) 次就是 \(O(n^2)\)。\(n = 2000\) 時約 \(4 \times 10^6\)，本站實測不到 \(0.1\) 秒；\(n = 10^5\) 就是 \(10^{10}\)，本站實測超過 \(60\) 秒——子題組 4 要換個做法。

從 70 分到 100 分：最遠點的最遠點

樹直徑有個漂亮的性質：從任何一個點出發，離它最遠的那個點，一定是某條直徑的端點。 所以只要兩次 BFS：

1. 隨便挑一個人（例如 \(0\) 號）做 BFS，找到離他最遠的人 \(u\)。
2. 從 \(u\) 再做一次 BFS，這次的最遠距離就是答案。

為什麼第一次找到的 \(u\) 一定是直徑端點，證明請看前置知識裡的〈樹的應用〉；直覺是：如果 \(u\) 不在直徑上，把它接到直徑上的路一定能換掉直徑的某一端而不會變短，否則 \(u\) 就不會是最遠的。上面的 farthest 原封不動，主程式只剩兩行：

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int u = farthest(0).first;         // 第一次：找離 0 號最遠的人 u
    cout << farthest(u).second << '\n';    // 第二次：從 u 出發的最遠距離就是直徑
    return 0;
}

兩次 BFS 各 \(O(n)\)，\(n = 10^5\) 眨眼就完。起點挑誰都可以（\(0\) 號不一定是祖先，沒關係）；「\(a\) 是 \(b\) 的父母」的方向從頭到尾沒用到。

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

const int MAX_N = 100005;
vector<int> G[MAX_N];
int parentOf[MAX_N];               // 以祖先為根時，每個人的父母（根是 -1）
int down1[MAX_N], down2[MAX_N];    // 往下走的最長、次長路（經過不同孩子）

int main() {
    int n;
    cin >> n;
    vector<bool> isChild(n, false);
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
        isChild[b] = true;
    }
    int root = 0;
    while (isChild[root]) root++;  // 唯一不是別人孩子的人就是祖先

    vector<int> order;             // BFS 的拜訪順序：父母一定排在孩子前面
    queue<int> q;
    parentOf[root] = -1;
    q.push(root);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        for (int v : G[u]) {
            if (v != parentOf[u]) {
                parentOf[v] = u;
                q.push(v);
            }
        }
    }

    int ans = 0;
    for (int i = n - 1; i >= 0; i--) {     // 倒著走：孩子都算完了才輪到父母
        int u = order[i];
        ans = max(ans, down1[u] + down2[u]);
        int p = parentOf[u];
        if (p == -1) continue;
        int len = down1[u] + 1;            // 從 p 經過 u 往下走的最長路
        if (len > down1[p]) {
            down2[p] = down1[p];
            down1[p] = len;
        } else if (len > down2[p]) {
            down2[p] = len;
        }
    }
    cout << ans << '\n';
    return 0;
}

測過再交：範例的直徑都太靠近祖先

範例 1 的祖先是 \(7\) 號（不是 \(0\)）、直徑 \(4 \sim 1 \sim 0 \sim 3 \sim 6\) 經過 \(0\) 號；範例 2 的直徑 \(1 \sim 0 \sim 2 \sim 3\) 直接經過祖先。沒蓋到的：最小的 \(n = 2\)、直徑完全不經過祖先、星星形、以及子題組 1 那種鏈。

四筆都親眼看過正確，這題就穩了。