自動分裝 題解｜APCS 2020 年 1 月高級 第 4 題

前置知識

這題是「二元樹上的模擬」，關鍵是每個分流器要記住底下的總重量，下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：

• 樹、子樹、用遞迴算每棵子樹的資訊：NTUCPC Guide〈樹〉——「子樹大小」那段的寫法（走完每個孩子，把孩子的資訊傳回父親）就是本題算總重量的方法，而且那一頁的習題「機關設計」就是本題；吳邦一《AP325》第 8 章的 P-8-5 就是本題（教材 PDF 第 299～302 頁），從「要做哪三件事」講起。
• 遞迴：NTUCPC Guide〈遞迴〉——會寫「自己呼叫自己、在葉子停下來」的函式就夠。
• vector：n 讀進來才知道要多大，用 vector 開。

簡潔題意

一棵以 \(1\) 為根的二元樹：\(1\) 到 \(n - 1\) 是分流器（各有左、右兩個孩子），\(n\) 到 \(2n - 1\) 是容器（葉子），容器一開始各有重量。依序送入 \(m\) 件物品：每件從根出發，在每個分流器比較左子樹所有容器的總重量與右子樹所有容器的總重量，往輕的那邊走、相同往左，到達容器後把重量加進去。輸出每件物品落入的容器編號（\(1 \le n \le 10^5\)，\(1 \le m \le 100\)，所有重量總和不超過 \(10^9\)；分流器的描述行不保證照編號順序）。（APCS 逐筆給分。）

讀樹：照編號存孩子，n = 1 時根本身就是容器

每一行「分流器 \(v\)、左孩子、右孩子」直接存進 leftChild[v]、rightChild[v]，行的順序無所謂（範例 2 的行就是亂的）。容器只有重量沒有孩子，所以 leftChild、rightChild 開到 \(n\) 就夠；重量表 total 開到 \(2n\)，容器的那格一開始就是讀進來的重量。\(n = 1\) 時沒有分流器行要讀，根 \(1\) 就是唯一的容器（\(n = 1\)，容器編號 \(1\) 到 \(1\)），每件物品都落在 \(1\)。

每個分流器記住「底下的總重量」，算一次、之後邊走邊更新

分流器比的是底下所有容器的總重量，每次走到一個分流器就重新把子樹加總一遍太慢：\(10^5\) 個分流器排成一條鏈時，一件物品要走 \(10^5\) 站、每站加總 \(O(n)\)，本站實測這種鏈狀測資要 \(25\) 秒。

改成先算好：total[v] 定義成「\(v\) 底下所有容器的總重量」，容器的 total 就是自己的重量，分流器的 total ＝ 左孩子的 total ＋ 右孩子的 total。從根呼叫一次遞迴，走完整棵樹就全部算好，\(O(n)\)。圖 1 是範例 2 算好的樣子：根的 \(38\) 是 \(20 + 18\)，分流器 5 的 \(18\) 是 \(9 + 9\)。

送一件物品時從根往下走，每站比較 total[左孩子] 與 total[右孩子]。物品最後一定落在這一站底下，所以路線上每一站的 total 都要加上這件物品的重量，不只容器那一格——下一件物品在這些站比較時才會看到正確的數字。在同一站先加自己、再比較孩子也沒關係：比較的是兩個孩子的 total，自己的 total 不參與。圖 1 的第一件物品（重量 \(2\)）落在容器 8，路線 \(1, 5, 6, 8\) 各加 \(2\)；第二件物品（重量 \(3\)）到根時左右變成 \(20\) 對 \(20\)，相同往左。

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

int n, m;
vector<int> leftChild, rightChild, total;   // total[v]：v 底下所有容器目前的總重量（容器本身＝自己的重量）

int fill(int v) {                            // 算出 v 的子樹總重量，順便把子樹裡每個分流器都填好
    if (v >= n) return total[v];             // 編號 n ～ 2n-1 是容器，重量就是讀進來的值
    total[v] = fill(leftChild[v]) + fill(rightChild[v]);
    return total[v];
}

int main() {
    cin >> n >> m;
    leftChild.assign(n, 0);
    rightChild.assign(n, 0);
    total.assign(2 * n, 0);
    for (int i = n; i < 2 * n; i++) cin >> total[i];
    vector<int> item(m);
    for (int j = 0; j < m; j++) cin >> item[j];
    for (int k = 0; k < n - 1; k++) {        // n - 1 行分流器，順序不一定，照編號存就好
        int v, l, r;
        cin >> v >> l >> r;
        leftChild[v] = l;
        rightChild[v] = r;
    }
    fill(1);                                 // 從根開始，一次算好所有分流器的總重量

    for (int j = 0; j < m; j++) {
        int v = 1;
        while (v < n) {                      // 還在分流器上
            total[v] += item[j];             // 物品一定會落在 v 底下：先把 v 的總重量加上
            if (total[leftChild[v]] <= total[rightChild[v]]) v = leftChild[v];   // 相同往左
            else v = rightChild[v];
        }
        total[v] += item[j];                 // 到達容器
        cout << v << (j + 1 < m ? ' ' : '\n');
    }
    return 0;
}

所有重量總和不超過 \(10^9\)，total 用 int 就夠。每件物品最多走樹高那麼多站，鏈狀的樹是 \(10^5\) 站、\(100\) 件共 \(10^7\) 步，加上一次 \(O(n)\) 的初始化，剛才那筆 \(25\) 秒的測資本站實測 \(0.07\) 秒。fill 的遞迴深度也等於樹高，鏈狀的樹會疊到 \(10^5\) 層，本站的堆疊空間夠用。

測過再交：範例沒有「n = 1」與「相同往左」的連鎖

兩個範例蓋到了亂序的分流器行（範例 2）與左右相同往左（範例 1 第一件）。沒蓋到：\(n = 1\)、很深的樹、重量頂到 \(10^9\)、以及更新總重量之後才出現的平手。

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