首頁 教學 演算法

# 前言

這是這個系列的最後一章。這一單元提到的東西跟上一單元 1-9 基本圖論演算法 差不多，像是 DFS 跟 BFS 這單元也一樣繼續都會用到，題目的類型寫起來會發現有很多類似的地方，不過這單元的題目有些會結合更前面的單元像是貪心法，動態規劃這些，題目都會結合起來不過我認為難度還是專門的動態規劃比較難，如果上一單元學得還可以這一單元也不需要太過擔心。

儲存樹的資料結構基本上用 vector 會是一個很好的選擇，樹上演算法 APCS 的範圍內我感覺大部分的題目用 DFS 寫都會蠻直覺的，如果不熟悉 DFS 的人建議多多練習，不會用 DFS 很多題目都會卡住。

# 樹的基本觀念複習

       1                    8
    /  |  \               /   \
   2   3   4              9    12
  / \ / \                / \
 5  6 7  8              10  11
  • 樹 (tree) 的定義：一個連通且無環路的圖；一個連通圖且 n(點數)=m(邊數)+1 ，如上圖；一個無環路的圖且 n=m+1
  • 一個圖上不只一棵樹就可以叫做森林 (forest)，如上圖
  • 樹上的點的名稱：
    • 根 (root)：例如點 (1,8)
    • 樹葉 (leaf)：也稱外節點 (external node)，沒有孩子的點例如點 (5,6,7,4)
    • 中間節點 (internal node)：例如點 (2,3)
    • 祖先 (ancestor)：每個點沿著 parent 往上一路走，都會走到 root，中間碰到的點都是它的祖先

這些名詞在 1-9 已經介紹過一次，這裡再複習一遍是因為接下來的演算法會頻繁用到「parent」「child」「深度」這些概念。

# DFS

# 例題：石窟探險（APCS）

有一組探險隊要去一個樹狀結構的石窟內探險，該石窟內有 n 個石室，第 i 個石室有一個編號 Ai，若 Ai 為偶數則會有 2 條分支 (左分支和右分支)，若 Ai 為奇數則有 3 條分支 (左分支、中分支和右分支)。

探險隊想要紀錄這個石窟的結構，每次只要第一次走到一個新的石室，就會將該石室的編號記錄在紙上，並由左到右依序走訪該石室的分支們，若走到一條死路則會在紙上紀錄一個數字 0，若該石室已經走完所有分支則退回到上一石室，走訪完整個石窟後在紙上得到上一個數字序列。

探險隊回到基地後忘記計算了這個石窟內所有相鄰的石室編號相差取絕對值的總和，請幫助探險隊從紙上的序列推算出該數值。

輸入一個整數個數不超過 1e6 的整數序列，石室的編號不超過 1e5，並保證造出來的樹深度不超過 40。

輸出說明：輸出一個整數代表這個石窟內所有相鄰的石室編號相差取絕對值的總和，答案大小有可能會超過 2^31。

範例輸入 #1 範例輸出 #1
2 6 0 8 14 0 0 0 10 0 4 0 0 26
範例輸入 #2 範例輸出 #2
5 2 10 0 0 0 8 0 0 17 0 0 0 26

範例輸入一說明： |2-6| + |6-8| + |8-14| + |2-10| + |10-4| = 26

如果不想寫成遞迴形式可以用 stack 來寫，不過我覺得遞迴比較簡潔好看。 dfs() 這個函數的定義是呼叫他之後輸入的 n 為當前的 root 然後回傳以這點為 root 然後依據題目的要求算出的答案。按照要求如果是 2 就會有兩個分支所以：

for(int i=0,temp;i<2;i++){
    temp=dfs();
    if(temp==0) continue;
    else ans+=abs(temp-n);
}

這邊回圈內會跑兩次呼叫兩次這個函數，記得寫遞迴一定都會有終止條件。這一行就是終止條件： if(n==0) return 0; 。如果程式一直在跑都沒輸出結果很有可能就是終止條件沒有設好，這邊要特別注意。

#include <bits/stdc++.h>
using namespace std;
long long ans;
int dfs(){
    int n;
    cin>>n;
    if(n==0) return 0;
    if(n%2==0){
        for(int i=0,temp;i<2;i++){
            temp=dfs();
            if(temp==0) continue;
            else ans+=abs(temp-n);
        }
    }else{
        for(int i=0,temp;i<3;i++){
            temp=dfs();
            if(temp==0) continue;
            else ans+=abs(temp-n);
        }
    }
    return n;
}
int main(){
    dfs();
    cout<<ans;
}

這題示範了一個很簡潔的技巧：直接把 cin 放在遞迴函式裡，讓讀取輸入的順序跟遞迴走訪的順序一致 —— 這正是 1-2 遞迴 例題一（合成函數）用過的手法，在樹的走訪裡同樣好用：不需要真的先讀完整個序列再建樹，遞迴的過程本身就自然完成了建樹跟走訪。

# BFS

# 例題：樹狀圖的距離總和（AP325）

輸入一個樹狀圖，請計算所有點到所有點的距離總和。本題假設編號 1 是根節點。

輸入格式：第一行是正整數 n，代表點數，點以 1~n 編號，第二行有 n-1 個正整數， p(2), p(3), …,p(n) ，依序是編號 2~ 編號 n 各點的 parent，第三行有 n-1 個正整數，依序代表 i 從 2 到 n，邊 (i,p (i)) 的長度。n 不超過 1e5，每條邊長度是不超過 1000 的正整數。

輸出：各點到各點的距離總和。請注意 i 到 j 與 j 到 i 都要納入總和，如範例。

範例一輸入 範例一輸出
4
1 2 3
10 20 30		 400
範例二輸入 範例二輸出
5
1 1 1 2
20 20 30 30		 880

範例二說明：

          1
       20/ \20
        2   4
     30/  \30
    (30)   3
    5

先來看點 1 到其他點的距離：點 1 到點 (2,4) 都是 20 到點 (3) 是 30 到點 (5) 是 50 所以加起來是 20+30+20+50=120。點二到其他點的距離：20+50+40+30=140，我按照點由小大到打的順序寫距離。點三到其他點的距離：30+50+50+80=210。點四到其他點的距離：20+40+50+70=180。點五到其他點的距離：50+30+80+70=230。總和 120+140+210+180+230=880。

# 解題思路

這題是 ** 換根 DP（re-rooting）** 的經典應用：如果每個點各自跑一次 BFS/DFS 算「這個點到所有其他點的距離」，總複雜度會是 O(n^2) ，n 到 1e5 時無法接受。換根 DP 的精神是：先花 O(n) 算出根節點到所有點的距離總和，再利用「相鄰兩點的答案之間有簡單的轉換關係」，一次遞迴把所有點的答案都推出來。

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int n,w[N],num[N]={0};
long long total=0,dis_son[N]={0},dis[N]={0};
vector<int> child[N];
void dfs(int p){//O(n)
    for(auto e:child[p]){
        int u=e;
        dfs(u);
        dis_son[p]+=dis_son[u]+num[u]*w[u];
        num[p]+=num[u];
    }
    num[p]++;
}
void dfs_dis(int p){//O(n)
    for(auto e:child[p]){
        int u=e;
        dis[u]=dis[p]-(num[u]*w[u])+(n-num[u])*w[u];
        total+=dis[u];
        dfs_dis(e);
    }
}
queue<int> q;
void bfs_dis(){// 算總和的時候 bfs 程式碼
    while(!q.empty()){
        int p=q.front();
        q.pop();
        for(auto t:child[p]){
            int u=t;
            q.push(u);
            dis[u]=dis[p]-( num[u]*w[u])+(n-num[u])*w[u];
            total+=dis[u];
        }
    }
}
int main(){
    cin>>n;
    for(int i=2,temp;i<=n;i++){
        cin>>temp;
        child[temp].push_back(i);
    }
    for(int i=2;i<=n;i++)
        cin>>w[i];
    dfs(1);
    dis[1]=dis_son[1];
    dfs_dis(1);
    // q.push(1);
    // bfs_dis();
    cout<<total+dis_son[1];
}

這一題我主要還是用了 DFS 不過算總合的地方我附上了用 BFS 的寫法。先來看每個陣列的定義：

  • dis_son[i] ：第 i 點的所有小孩的距離總和，所以 dis_son[1] 等於 1 到所有點的距離總和，以範例一為例 dis_son[1]=100
  • dis[i] ：第 i 點到所有點的距離總和，所以 dis[1]=dis_son[1]
  • num[i] ：點 i 的 parent 到點 i 這條邊走過的次數，這個走過的次數是根據 1 這個點為 root 走到所有點其中走過這條邊的次數
  • total ：所有點到所有點的距離

拿範例二來說明幾行重要的程式：

dis_son[p]+=dis_son[u]+num[u]*w[u];

由遞迴得知在計算 dis_son[p] 時， w[u] 這一條邊會走 num[u] 這麼多次，圖中的點 (5,3,4) 葉節點在 num 陣列裡都是 1 而 (2) 是 2 因為點 (1) 走到點 (2) 跟點 (5) 個會經過一次這條邊。

dis[u]=dis[p]-(num[u]*w[u])+(n-num[u])*w[u];

先注意看這一行所在的函式是先執行這一行才進行遞迴的， dis[u] 這一點到所有點的距離，這裡要對照著上面的圖看，假如現在的 u=2 所以 p=1，那換成中文敘述就是點 (1) 到所有點的距離減掉點 (1) 到點 (2) 中間這條邊，注意這裡減掉不只是減 1 次，要觀察點 (1) 到所有點中會經過這條邊幾次，然後再加上這一點往上到所有點會經過幾次，因為原本的 num 陣列是根據點 (1) 來儲存的所以是由上往下，現在是要看這點往上所以這行才會這樣寫，可以發現這行可以再畫減，不過這樣的可讀性我覺得比較好也比較方便來說明。

這個公式的核心洞察是：當我們把「根」從 p 換到相鄰的子節點 u 時，樹上所有點到 u 的距離，相對於到 p 的距離，只有「跨越 (p,u) 這條邊」的方向會改變 —— 原本走這條邊「靠近」的點（u 的子樹內，共 num[u] 個點）現在距離變近了 w[u] ，原本「遠離」的點（子樹外，共 n-num[u] 個點）現在距離變遠了 w[u] 。這就是「換根」名稱的由來，也是樹上 DP 一個非常重要的套路，能把 O(n^2) 的暴力（每個點各跑一次 BFS）降到 O(n) 。

# 例題：病毒演化（APCS，樹上 DP 綜合應用）

在資訊科學上，RNA 病毒可以看成一個由 A、U、G、C 這四種字母構成的字串。病毒演化中，某些字元可能變異成其他字元，例如將 AAUGG 中的第 3 個位置的 U 換成 C，則得到 AACGG，變異可能發生在多個位置。有個實驗團隊取得了某種 RNA 病毒的數個 RNA 片段樣本，並且掌握到這些樣本演化的親緣關係，用（樣本編號，親代編號，RNA 字串）的格式記錄，其中「樣本編號」與「親代編號」為兩個整數，若兩數字相同，則該樣本即為演化的源頭。

例如：(1, 1, AAAA) (2, 1, GCAA) 表示樣本 1 的 RNA 字串為 AAAA，樣本 2 為 GCAA，且樣本 2 是由樣本 1 在兩個位置發生變異演化而來，樣本 1 為演化的源頭。

然而，字串中每個位置的字元無法確定，實驗團隊以 @ 來表示這些字元，換言之，可能為 A、U、G、C 中任何一個。請注意，一個字串中可能有多個 @，並非代表這些位置的字元是相同的。例如 A@C@ 可能是任何第一個字元為 A 且第三個字元為 C 的字串，像是 ACCU 或 AACC。團隊猜測演化過程發生的變異總數會盡可能的少。請你利用親緣關係，來計算最小的變異總數量。

輸入格式：第一行有兩個正整數 n 與 m，表示共有 n 個樣本，由 1 至 n 編號；每個樣本之 RNA 字串長度均為 m，其中 n ≤ 1000 且 m ≤ 80。接下來 n 行，每行包含以空白間隔的兩個整數 i 與 j 以及一個 RNA 字串 si，對應一個樣本（i,j,si），si 由 A、U、G、C 與 @ 五種字元所組成。若 i=j=1，則該樣本即為演化的源頭，源頭以外樣本皆恰有一個親代。

輸出：輸出最小可能的變異總數。

範例一輸入 範例一輸出
2 3
1 1 AAC
2 1 A@@		 0
範例二輸入 範例二輸出
6 1
1 1 @
2 1 @
3 1 C
4 1 C
5 2 A
6 2 A		 1

# 解題思路

這類型的題目是我相對不擅長的類型，所以我在這本講義的結尾放上這一題。這一題我是採用 top-down 的寫法，這類型的題目用 top-down 會好寫很多，再來根據題目變化是單個字元的事情，所以就是判斷只要判斷一個字元就好，最後用個迴圈全部跑一次把變化量加總起來就可以了，這種題目可能會想說要如何去判斷什麼時候變化，想了一下之後想不到貪心的寫法就果斷用 dp 了，通常不確定該用什麼寫法的時候觀察一下測資大小會有很大的幫助。

#include<bits/stdc++.h>
using namespace std;
#define N 1005
#define INF 1147483647//2^31-1-10^9
#define T 5
vector<int> v[N];
int n,m,root,dp[N][5],ans;
string s[N];//{'@',0} 負責記錄變化最少的結果
map<char,int> mp={{'@',0},{'A',1},{'U',2},{'C',3},{'G',4}};
//A、U、C、G
void Virus(int f,int pos){
    int b=mp[s[f][pos]];// 紀錄符號
    if(v[f].empty()){
        if(s[f][pos]=='@') return;
        for(int i=1;i<T;i++)
            dp[f][i]=INF;
        dp[f][0]=dp[f][b]=0;
        return;
    }
    for(auto e:v[f])
        Virus(e,pos);
    if(s[f][pos]=='@'){// 因為是 @所以每種變化都計算一遍
        for(int i=1;i<T;i++)
            for(auto e:v[f])
                dp[f][i]+=min(dp[e][0]+1,dp[e][i]);
        dp[f][0]=min(min(dp[f][1],dp[f][2]),min(dp[f][3],dp[f][4]));
    }else{
        for(int i=1;i<T;i++) dp[f][i]=INF;
        dp[f][b]=0;
        for(auto e:v[f])
            dp[f][b]+=min(dp[e][0]+1,dp[e][b]);// 一樣的不用加 1
        dp[f][0]=dp[f][b];
    }
}
int main(){
    cin>>n>>m;
    for(int i=0,a,b;i<n;i++){
        cin>>a>>b;
        cin>>s[a];
        if(a==b) root=a;
        else v[b].push_back(a);
    }
    for(int i=0;i<m;i++){
        Virus(root,i);
        ans+=dp[root][0];
        memset(dp,0,sizeof(dp));
    }
    cout<<ans;
}

先來看終止條件在葉節點的時候如果為 @ 就可以直接 return，因為只有一個 parent 所以就不用判斷了，再來就是要對 dp 陣列做一些更新，可以看到上面的 map 幫忙把四個字元都對應到了四個數字，而最前面的 dp[f][0] 就代表著最佳解的意思。

繼續往下看如果是 @ 就每個都要計算一遍看變成哪個會比較好最後取最小值，如果不是就是判斷自己的子節點看是要突變還是一樣怎麼選會比較好突變會最少的就是比較 dp 陣列裡的值取最小值。最後提醒在寫遞迴的時候就是要讓等號右邊先出來。

這題整合了這系列前面幾章的技巧：用遞迴走訪樹（本章）、DP 的「選與不選（這裡是選哪個字元）」思維（1-8）、以及用 map 把字元映射到數字方便處理（1-1）。這也說明了為什麼我把樹上演算法放在系列的最後一章 —— 它常常是前面所有章節技巧的綜合考驗。

# 總結

終於打完了，希望我解釋的這些題目有幫助大家理解，我幾乎都是挑 AP325 裡沒有講解的題目，有些題目我想了非常久才寫出來，如果把這些題目都做完了恭喜你，你大概已經了解了 APCS 範圍內的所有觀念，可是這樣還是不夠的，要多刷一些題目，練習自己對題目的反應速度，還練習像是 APCS 裡得第二題這種比較大型麻煩的程式，這種程式雖然不難花時間就寫得出來，不過重點就是要花時間，然而時間是有限的，要練習寫題的速度。

這個系列從 1-1 基本資料結構與 STL 的工具箱開始，走過 1-2 遞迴、1-3 搜尋技巧、1-4 窮舉暴搜與回溯法、1-5 貪心演算法、1-6 掃描線演算法、1-7 分治演算法、1-8 動態規劃、1-9 基本圖論演算法，一路到這一章的樹上演算法。整個系列的骨架沿用我原本《APCS 考前準備》講義的順序，並補上了 AP325（吳邦一教授）跟 2023 CISCON 社群月演算法專題課程裡更完整的觀念說明、複雜度分析與證明方法。

我再次感謝 AP325 的作者吳邦一教授、2023 CISCON 課程的講師們（動態規劃：陳俊安 Colten；貪心：Koying；枚舉：Fishhh；搜尋：高睿）還有網路上的各個電神分享自己的解題經驗，我才有辦法寫出這些困難的題目。

之後會在各章節增加更多練習題 URL，把這份筆記補得更完整。

# 練習題

（之後補上）

更新於 閱讀次數 次