樹狀圖分析 (APCS 2017-10 高級) 的題解

前置知識

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

  • 樹的名詞與儲存：NTUCPC Guide〈樹〉——根、父節點、子節點、葉節點，以及「子樹大小」那段由下往上累加的 DFS；吳邦一《AP325》第 3 章的 P-3-1「樹的高度與根（bottom-up）」正是本題，用的是「葉子先出場」的佇列做法（教材 PDF 第 76～80 頁；Python 版第 3 章）。
  • 遞迴：NTUCPC Guide〈遞迴〉（終止條件＋「假裝函式已經寫好」）。
  • 巢狀 vector：語法書 10.3（每個節點的子節點數量不一樣）。

簡潔題意

一棵 \(n\) 個節點的有根樹（編號 \(1 \sim n\)），輸入第 \(i\) 行列出節點 \(i\) 的所有子節點。節點的高度 \(h(v)\)＝它到自己底下最遠葉節點的邊數（葉節點是 \(0\)）。輸出根的編號，以及所有節點高度的總和 \(H(T)\)（\(n \le 10^5\)）。

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

  • 子題組 1（\(10\) 分）：\(1 \le n \le 4\)，每個節點至多 \(3\) 個子節點，除了根以外都是葉節點。
  • 子題組 2（\(30\) 分）：\(1 \le n \le 1000\)，每個節點至多 \(3\) 個子節點。
  • 子題組 3（\(30\) 分）：\(1 \le n \le 10^5\)，每個節點至多 \(3\) 個子節點。
  • 子題組 4（\(30\) 分）：\(1 \le n \le 10^5\)，子節點數量無限制。

先拿下 10 分：找根，而且高度總和只有兩種可能

根＝唯一沒有父節點的節點。 讀第 \(i\) 行時，每個被列出的子節點都「有父節點了」，記在一個陣列裡；讀完掃一遍，沒被記到的那個就是根——根不一定是 \(1\) 號（範例 1 的根是 \(5\)、範例 2 是 \(4\)）。

子題組 1 保證除了根以外全是葉節點：\(n = 1\) 時根自己就是葉節點、總和 \(0\)；否則只有根的高度是 \(1\)、其他都 \(0\)，總和 \(1\)。

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

int main() {
    int n;
    cin >> n;
    vector<bool> hasParent(n + 1, false);
    for (int i = 1; i <= n; i++) {
        int cnt;
        cin >> cnt;
        for (int j = 0; j < cnt; j++) {
            int child;
            cin >> child;
            hasParent[child] = true;       // child 有父節點了（就是 i）
        }
    }
    int root = 1;
    while (hasParent[root]) root++;        // 唯一沒有父節點的就是根

    cout << root << '\n';
    if (n == 1) cout << 0 << '\n';         // 子題組 1：只有根的高度可能是 1
    else cout << 1 << '\n';
    return 0;
}

兩個範例的樹都不只兩層，第二行會 WA——這是正常的，逐筆給分之下子題組 1 的 \(10\) 分穩穩到手。

從 10 分到 40 分：照定義遞迴

題目的提示已經把遞迴式寫好：葉節點 \(h = 0\)，其他節點 \(h(v) = \max(\text{子節點的 } h) + 1\)。把每個節點的子節點存進 vector<vector<int>>，寫一個 height(v)：先對每個子節點呼叫自己、取最大值加一；順手把每個節點的高度加進總和。從根呼叫一次，整棵樹就算完。

圖 1：範例 2 的樹，每個節點標上高度；一個節點的高度要等它所有孩子算完才知道，總和 11 
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> children;      // children[v]：v 的所有子節點
long long total = 0;               // 高度總和

// 回傳 v 的高度，順便把 v 的高度加進 total
int height(int v) {
    int h = 0;                     // 葉節點：沒有子節點，迴圈不會跑，h 留在 0
    for (int c : children[v])
        h = max(h, height(c) + 1);
    total += h;
    return h;
}

int main() {
    int n;
    cin >> n;
    children.assign(n + 1, vector<int>());
    vector<bool> hasParent(n + 1, false);
    for (int i = 1; i <= n; i++) {
        int cnt;
        cin >> cnt;
        children[i].resize(cnt);
        for (int j = 0; j < cnt; j++) {
            cin >> children[i][j];
            hasParent[children[i][j]] = true;
        }
    }
    int root = 1;
    while (hasParent[root]) root++;

    height(root);
    cout << root << '\n' << total << '\n';
    return 0;
}

每個節點恰好被呼叫一次、每條邊恰好走一次，\(O(n)\)。但 \(n = 10^5\) 的樹可能是一條鏈（每個節點只有一個子節點），遞迴就會疊到 \(10^5\) 層：本站的堆疊沒有上限，這份程式其實子題組 3、4 也會過；檢定現場的環境沒人保證，所以下面給一個不靠遞迴的版本。

從 40 分到 100 分：先排好順序，再倒著算

遞迴真正做的事只有一件：算一個節點之前，先把它的子節點都算完。不用遞迴也能辦到——從根開始用一個佇列把節點「父節點在前、子節點在後」排成一排（就是 BFS 的拜訪順序），然後倒著走這一排：輪到某個節點時，它的子節點都已經排在後面、早就算完了。

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

int main() {
    int n;
    cin >> n;
    vector<vector<int>> children(n + 1);
    vector<bool> hasParent(n + 1, false);
    for (int i = 1; i <= n; i++) {
        int cnt;
        cin >> cnt;
        children[i].resize(cnt);
        for (int j = 0; j < cnt; j++) {
            cin >> children[i][j];
            hasParent[children[i][j]] = true;
        }
    }
    int root = 1;
    while (hasParent[root]) root++;

    vector<int> order;                     // 父節點一定排在子節點前面
    order.push_back(root);
    for (int i = 0; i < (int)order.size(); i++)   // 邊走邊把子節點接到後面
        for (int c : children[order[i]])
            order.push_back(c);

    vector<int> h(n + 1, 0);
    long long total = 0;
    for (int i = n - 1; i >= 0; i--) {     // 倒著走：子節點都算完了才輪到父節點
        int v = order[i];
        for (int c : children[v])
            h[v] = max(h[v], h[c] + 1);
        total += h[v];
    }
    cout << root << '\n' << total << '\n';
    return 0;
}

一樣是 \(O(n)\)，沒有任何遞迴。總和要用 long long：\(10^5\) 個節點排成一條鏈時，高度是 \(0, 1, 2, \ldots, 99999\)，總和約 \(5 \times 10^9\)，int 裝不下。

測過再交：範例的根都是「中間的編號」、樹都不深

兩個範例的根是 \(5\) 和 \(4\)，樹高只有 \(2\) 和 \(4\)。沒蓋到的：根是 \(1\) 號或 \(n\) 號、\(n = 1\)、一條長鏈（高度總和爆 int）、一個節點有很多子節點。

輸入 正確輸出 這一筆在測什麼
1 ／ 0 1 ／ 0 只有一個節點：既是根也是葉，總和 \(0\)（子題組 1 版就能驗）
3 ／ 0 ／ 0 ／ 2 1 2 3 ／ 1 根是最後一號：找根不能預設 \(1\) 號（子題組 1 版就能驗）
4 ／ 1 2 ／ 1 3 ／ 1 4 ／ 0 1 ／ 6 一條鏈 \(1 \to 2 \to 3 \to 4\)：高度 \(3 + 2 + 1 + 0\)
5 ／ 4 2 3 4 5 ／ 0 ／ 0 ／ 0 ／ 0 1 ／ 1 一個節點有四個子節點（子題組 4 才有）：高度只看最深的，不是數子節點
用程式造：\(n = 10^5\) 的一條鏈 1 ／ 4999950000 總和超過 int 的 \(2147483647\)

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

常犯錯誤
  • 預設 \(1\) 號是根：範例 1 印 1、範例 2 印 1，而且從錯的根出發算不到整棵樹。
  • 算成「到根的深度」總和：高度是往下看、深度是往上看——範例 1 印 10、範例 2 印 19。
  • 高度總和用 int：兩個範例都過、\(n \le 1000\) 也都過，長鏈測資溢位印負數或亂數。
  • 每個節點各自往下重算一次子樹（沒有把子節點的高度存起來）：鏈上變成 \(O(n^2)\)，\(n = 10^5\) 的鏈 TLE。
  • 子節點陣列只開固定 \(3\) 格（子題組 1 到 3 的限制）：子題組 4 的節點有更多子節點，寫到陣列外面。
  • 高度初值設 \(1\) 再取最大：葉節點變成 \(1\)、全部多算一層——範例 1 印 11。