建造堡壘 題解｜APCS 2026 年 11 月高級 第 1 題

前置知識

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

• 樹的儲存與 DFS：NTUCPC Guide〈圖論基礎〉的鄰接串列，以及 NTUCPC Guide〈樹〉的「來爬樹」「子樹大小」——dfs(s, par) 用參數記住從哪裡來、不走回頭路，走完一個孩子就把孩子的結果交回父節點；吳邦一《AP325》第 8 章 8.2 講同樣的東西（教材 PDF 第 269～284 頁；Python 版第 8 章（I））。
• DP 的狀態要記住會影響下一步的事（子題組 1 用）：NTUCPC Guide〈狀態與轉移〉的例題一「小心狀態陷阱」——只記「跑完前 \(i\) 段的最高分」不夠，要把「第 \(i\) 段有沒有加速」也放進狀態。
• 樹上的 DP：NTUCPC Guide〈樹的應用〉「樹上匹配問題」的開頭——把每棵子樹當成一個小問題，想清楚孩子的答案怎麼和父節點合併；《AP325》第 8 章的 P-8-11「公司派對」把每個點分成「選它」與「不選它」兩種情況，各算一個最佳值，本題用的就是這個架構（教材 PDF 第 300～303 頁；Python 版第 8 章（III）；站上題目 ap325p811）。同一章的習題 Q-8-10「竊聽間諜網」就是本題花費全部是 \(1\) 的版本（教材 PDF 第 299～300 頁；站上題目 ap325q810）。

簡潔題意

\(n\) 個城市（編號 \(1 \sim n\)）由 \(n - 1\) 條雙向道路連成一棵樹，在城市 \(i\) 建堡壘的花費是 \(C_i\)。選一些城市建堡壘，讓每一條道路至少有一端建了堡壘，求最少的總花費（\(2 \le n \le 2 \times 10^5\)，每個 \(C_i\) 都是 \(0\) 到 \(10^4\) 的整數；道路的先後順序、每行 \(u\) 和 \(v\) 誰先寫都沒有任何保證）。

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

• 子題組 1（\(40\) 分）：每個城市至多連接兩條道路。
• 子題組 2（\(60\) 分）：無額外限制。

先拿下 40 分：沿著鏈走一遍，每個城市記兩個數

子題組 1 的每個城市至多連兩條道路，\(n\) 個城市又靠 \(n - 1\) 條道路全部連通——畫出來就是一條鏈。可是鏈不一定照編號排（範例 2 的鏈依序是城市 \(3\)、\(6\)、\(1\)、\(5\)、\(2\)、\(4\)），要先沿著道路把順序排出來：只連一條道路的城市是鏈的一端，從它出發，每一步走向「不是剛剛來的那個」鄰居，走到另一端為止。

排好順序之後，由前往後一個一個決定建不建。限制是「相鄰的兩個城市不能都不建」，所以決定一個城市時，前面只有一件事會影響它：前一個城市有沒有建——沒建的話，這一個非建不可。每走到一個城市就記兩個數：

• f0：這個城市不建時，走過的道路全部顧好的最少花費；
• f1：這個城市建時，走過的道路全部顧好的最少花費。

走到下一個城市 \(x\)：

• \(x\) 不建：前一個城市一定要建，新的 f0 就是舊的 f1；
• \(x\) 建：前一個建不建都可以、挑省的，新的 f1 是舊的 f0、f1 比較小的那個再加上 \(C_x\)。

第一個城市的 f0 是 \(0\)、f1 是它的花費；走到最後一個城市，f0、f1 比較小的那個就是答案。範例 2 照這樣走一遍：

「不建」那一欄永遠是上一列的「建」；最後一列取比較小的 \(5\)，就是答案。

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

const int MAX_N = 200005;
vector<int> adj[MAX_N];                 // adj[u]：和城市 u 有道路相連的城市
int C[MAX_N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> C[i];
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);            // 道路沒有方向，兩端都記
        adj[v].push_back(u);
    }

    int start = 1;
    while (adj[start].size() != 1) start++;    // 只連一條道路的城市就是鏈的一端

    vector<int> order;                  // 沿著鏈排好的城市
    int prev = 0, cur = start;
    while (cur != 0) {
        order.push_back(cur);
        int next = 0;                   // 走到另一端就沒有下一站，留在 0
        for (int w : adj[cur])
            if (w != prev) next = w;    // 不走回頭路
        prev = cur;
        cur = next;
    }

    int f0 = 0, f1 = C[order[0]];       // 第一個城市不建／建
    for (int i = 1; i < (int)order.size(); i++) {
        int x = order[i];
        int g0 = f1;                    // x 不建：前一個城市一定要建
        int g1 = min(f0, f1) + C[x];    // x 建：前一個建不建都可以，挑省的
        f0 = g0;
        f1 = g1;
    }
    cout << min(f0, f1) << '\n';
    return 0;
}

沿著鏈走一遍、每個城市算一次，\(O(n)\)。範例 1 不是鏈，這份程式交上去範例 1 會 WA——這是正常的，逐筆給分之下子題組 1 的 \(40\) 分穩穩到手。

從 40 分到 100 分：每個城市一樣記兩個數，從葉子往根算

一般的樹排不成一排，可是「建、不建分開算」的想法照樣能用。先看看為什麼更簡單的貪心不行：每條道路各自挑便宜的一端，或是把城市分成兩組（相鄰的兩個城市一定不同組）、只建便宜的那一組——範例 1 兩種做法都挑到城市 \(1\)、\(3\)、\(5\)、\(6\)、\(7\)，花費 \(12\)，答案卻是 \(10\)。最佳解建的城市 \(2\) 比它的鄰居 \(5\)、\(1\) 都貴，可是建它一個就顧好道路 \(2\)–\(5\) 和 \(2\)–\(1\)，比建城市 \(5\)、\(1\) 兩個加起來的 \(7\) 便宜；而且城市 \(2\)、\(6\) 相鄰，兩個都建了。一個城市划不划算，要看它的鄰居怎麼選，所以「建」與「不建」兩種情況都要留著，留給上一層再決定。

把城市 \(1\) 當成根（根挑哪個城市都可以，下面會驗證），每個城市 \(u\) 只看「\(u\) 和它底下的子樹」，算兩個數：

• \(dp_0[u]\)：\(u\) 不建時，子樹裡的道路全部顧好的最少花費；
• \(dp_1[u]\)：\(u\) 建時，子樹裡的道路全部顧好的最少花費。

\(u\) 和它的每個孩子 \(v\) 之間都有一條道路：

• \(u\) 不建：這條道路只剩 \(v\) 能顧，每個孩子都非建不可——\(dp_0[u]\) 是所有孩子的 \(dp_1\) 加起來。
• \(u\) 建：這條道路已經顧好了，孩子建不建都可以、各挑省的——\(dp_1[u]\) 是 \(C_u\) 加上每個孩子的 \(dp_0\)、\(dp_1\) 比較小的那個。

孩子們的子樹之間沒有道路，只靠 \(u\) 連在一起，所以 \(u\) 建不建定了之後，每棵子樹各挑各的最省，加起來就是最省。葉子沒有孩子：\(dp_0 = 0\)、\(dp_1 = C_u\)。根沒有父節點，建不建都可以，答案是根的 \(dp_0[1]\)、\(dp_1[1]\) 比較小的那個。

範例 1 從葉子往根算（圖 1）：「不建」是孩子們的「建」加起來，「建」是自己的花費加上每個孩子挑小的那一個。

答案是 \(\min(10, 12) = 10\)。

圖 1 的綠框是從根往下、照「比較小的那一格」走回去的結果（父節點不建時，孩子只能選「建」）：建堡壘的是城市 \(2\)、\(3\)、\(6\)、\(7\)，正是範例解釋的建法。根挑哪個城市都可以——根只決定從哪裡開始往下看，道路和規則都沒變：換城市 \(6\) 當根重算一次，根的兩個數是 \(14\) 和 \(10\)，答案一樣是 \(10\)。

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

const int MAX_N = 200005;
vector<int> adj[MAX_N];                 // adj[u]：和城市 u 有道路相連的城市
int C[MAX_N];
int dp0[MAX_N], dp1[MAX_N];             // u 不建／建時，u 這棵子樹的最少花費

void dfs(int u, int parent) {
    dp0[u] = 0;
    dp1[u] = C[u];
    for (int v : adj[u]) {
        if (v == parent) continue;      // 父節點不是孩子，不走回頭路
        dfs(v, u);                      // 先把孩子 v 的子樹算完
        dp0[u] += dp1[v];               // u 不建：v 一定要建
        dp1[u] += min(dp0[v], dp1[v]);  // u 建：v 挑省的
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> C[i];
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);            // 道路沒有方向，兩端都記
        adj[v].push_back(u);
    }
    dfs(1, 0);                          // 城市 1 當根；0 不是任何城市，代表沒有父節點
    cout << min(dp0[1], dp1[1]) << '\n';
    return 0;
}

每個城市被 dfs 呼叫一次，每條道路從兩端各看一次，\(O(n)\)；\(n = 2 \times 10^5\) 本站實測不到 \(0.4\) 秒。每個 \(dp_0\)、\(dp_1\) 都不超過全部花費的總和：\(2 \times 10^5\) 個城市、每個最多 \(10^4\)，總和最多 \(2 \times 10^9\)，比 int 的上限 \(2147483647\) 小，int 就夠。不用遞迴的寫法收在下面。

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

const int MAX_N = 200005;
vector<int> adj[MAX_N];                 // adj[u]：和城市 u 有道路相連的城市
int C[MAX_N];
int dp0[MAX_N], dp1[MAX_N];             // u 不建／建時，u 這棵子樹的最少花費
int parentOf[MAX_N];                    // 以城市 1 為根時的父節點（根是 0）

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> C[i];
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> order;                  // BFS 的拜訪順序：父節點一定排在孩子前面
    order.push_back(1);
    for (int i = 0; i < n; i++) {       // 邊走邊把孩子接到後面
        int u = order[i];
        for (int v : adj[u]) {
            if (v == parentOf[u]) continue;
            parentOf[v] = u;
            order.push_back(v);
        }
    }

    for (int u = 1; u <= n; u++) {      // 還沒加上任何孩子：不建是 0、建是自己的花費
        dp0[u] = 0;
        dp1[u] = C[u];
    }
    for (int i = n - 1; i >= 1; i--) {  // 倒著走：孩子都算完了才輪到父節點（order[0] 是根）
        int v = order[i];
        int u = parentOf[v];
        dp0[u] += dp1[v];               // u 不建：v 一定要建
        dp1[u] += min(dp0[v], dp1[v]);  // u 建：v 挑省的
    }
    cout << min(dp0[1], dp1[1]) << '\n';
    return 0;
}

測過再交：有兩種錯法，兩個範例都擋不住

範例 1 是 \(7\) 個城市的樹、範例 2 是 \(6\) 個城市的鏈，答案都不大。沒蓋到的：只有一條道路的 \(n = 2\)、星狀的樹、答案是 \(0\) 或最大的情況，還有兩種兩個範例都會過的錯法（見常犯錯誤）——第 2 列就是專門抓它們的。

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