<style> .markdown-body table{ display: unset; } </style> # APCS實作題2017年10月第3題：樹狀圖分析 (Tree Analyses) > 第1版：2023年6月15日 > 第2版：2024年11月23日 > 作者：王一哲 > 題目來源：[106年10月28日實作題第3題](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2018/12/1061028APCSImplementation.pdf) > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=c463) <br /> ## 題目 ### 問題描述 本題是關於有根樹(rooted tree)。在一棵 n 個節點的有根樹中，每個節點都是以 1 ~ n 的不同數字來編號，描述一棵有根樹必須定義節點與節點之間的親子關係。一棵有根樹恰有一個節點沒有父節點(parent)，此節點被稱為根節點(root)，除了根節點以外的每一個節點都恰有一個父節點，而每個節點被稱為是它父節點的子節點(child)，有些節點沒有子節點，這些節點稱為葉節點(leaf)。在當有根樹只有一個節點時，這個節點既是根節點同時也是葉節點。 在圖形表示上，我們將父節點畫在子節點之上，中間畫一條邊(edge)連結。例如，圖一中表示的是一棵 9 個節點的有根樹，其中，節點 1 為節點 6 的父節點，而節點 6 為節點 1 的子節點；又 5、3 與 8 都是 2 的子節點。節點 4 沒有父節點，所以節點 4 是根節點；而 6、9、3 與 8 都是葉節點。 <img height="50%" width="50%" src="https://i.imgur.com/rwJg8H7.png" style="display: block; margin-left: auto; margin-right: auto;"/> <br /> 樹狀圖中的兩個節點 $u$ 和 $v$ 之間的距離 $d(u,v)$ 定義為兩節點之間邊的數量。如圖一中，$d(7, 5) = 2$，而 $d(1, 2) = 3$。對於樹狀圖中的節點 $v$，我們以 $h(v)$ 代表節點 $v$ 的高度，其定義是節點 $v$ 和節點 $v$ 下面最遠的葉節點之間的距離，而葉節點的高度定義為 0。如圖一中，節點 6 的高度為 0，節點 2 的高度為 2，而節點 4 的高度為 4。此外，我們定義 $H(T)$ 為 $T$ 中所有節點的高度總和，也就是說 $H(T) = \sum_{v \in T} h(v)$。給定一個樹狀圖 $T$，請找 出 $T$ 的根節點以及高度總和 $H(T)$。 <br /> ### 輸入格式 第一行有一個正整數 n 代表樹狀圖的節點個數，節點的編號為 1 到 n。接下來有 n 行，第 i 行的第一個數字 k 代表節點 i 有 k 個子節點，第 i 行接下來的 k 個數字就是這些子節點的編號。每一行的相鄰數字間以空白隔開。 <br /> ### 輸出格式 輸出兩行各含一個整數，第一行是根節點的編號，第二行是 $H(T)$。 <br /> ### 範例一：輸入 ``` 7 0 2 6 7 2 1 4 0 2 3 2 0 0 ``` ### 範例一：正確輸出 ``` 5 4 ``` <img height="50%" width="50%" src="https://imgur.com/ulVao06.png" style="display: block; margin-left: auto; margin-right: auto;"/> <div style="text-align:center">範例一</div> <br /> ### 範例二：輸入 ``` 9 1 6 3 5 3 8 0 2 1 7 1 9 0 1 2 0 0 ``` ### 範例二：正確輸出 ``` 4 11 ``` <img height="40%" width="40%" src="https://imgur.com/FtdKTfk.png" style="display: block; margin-left: auto; margin-right: auto;"/> <div style="text-align:center">範例二</div> <br /> ### 評分說明 輸入包含若干筆測試資料，每一筆測試資料的執行時間限制(time limit)均為 1 秒，依正確通過測資筆數給分。測資範圍如下，其中 k 是每個節點的子節點數量上限： - 第 1 子題組 10 分，$1 \leq n \leq 4$, $k \leq 3$, 除了根節點之外都是葉節點。 - 第 2 子題組 30 分，$1 \leq n \leq 1,000$, $k \leq 3$。 - 第 3 子題組 30 分，$1 \leq n \leq 100,000$, $k \leq 3$。 - 第 4 子題組 30 分，$1 \leq n \leq 100,000$, $k$ 無限制。 <br /> ### 提示 輸入的資料是給每個節點的子節點有哪些或沒有子節點，因此，可以根據定義找出根節點。關於節點高度的計算，我們根據定義可以找出以下遞迴關係式： 1. 葉節點的高度為 0 2. 如果 $v$ 不是葉節點，則 $v$ 的高度是它所有子節點的最大高度加一。也就是說，假設 $v$ 的子節點有 a, b 與 c，則 $h(v) = max\{ h(a), h(b), h(c) \}+1$。以遞迴方式可以計算出所有節點的高度。 <br /> ## Python 程式碼 ```python= n = int(input()) # 由標準輸入讀取節點數量 n m = n+1 # 節點編號從1開始，但串列索引值從0開始，以下3個串列長度加1 parents = [0]*m # 每個節點的父節點資料，一維串列，如果為0就是根節點 depth = [-1]*m # 每個節點的深度，一維串列 num = [0]*m # 每個節點的子節點數量，一維串列 leafs = [] # 找深度用的葉節點，一維串列 for i in range(1, n+1): data = list(map(int, input().split())) # 由標準輸入讀取資料並暫時存成串列 k = data[0] # 索引值為0的資料存入子節點數量 k children = data[1:] # 之後的資料存入一維串列 children if k == 0: # 如果子節點數量為 0 leafs.append(i) # 此節點為葉節點，存入一維串列 leafs depth[i] = 0 # 此節點深度為 0 else: # 如果子節點數量不為 0 num[i] = k # 存入一維串列 num for j in children: parents[j] = i # 節點 j 的父節點為 i while leafs: # 若串列中還有元素繼續執行，最後會多跑一次根節點的深度，存到 deptho[0] #print(leafs) # 除錯用，印出葉節點 leaf = leafs.pop(0) # 取出 leafs 中最前面的元素 # 比較 leaf 的父節點深度與 leaf 深度加1，取較大者更新 leaf 的父節點深度 depth[parents[leaf]] = max(depth[parents[leaf]], depth[leaf]+1) #print(depth) # 除錯用，印出節點深度 num[parents[leaf]] -= 1 # leaf 的父節點對應的子節點數量減1 if num[parents[leaf]] == 0: # 若已無子節點，將自己加入 leafs，作為之後要檢測深度的節點 leafs.append(parents[leaf]) print(leaf) # 印出最後一個由 leafs 取出的元素，根節點 print(sum(depth[1:])) # 印出所有節點深度，記得要排除 depth[0] ``` <br /> 1. 這個寫法主要是由參考資料1改寫成 Python 版本，每行程式碼的用途已寫在註解之中。 2. 第20 ~ 28行：整個程式最主要的部分，如果輸入資料為範例2，以下是各次迴圈運作時的狀況 <div style="text-align:center"> | 迴圈運作次數 | 原來的 leafs 內容 | 效果 | | ---------- | -------- | ---- | | 1 | 3, 6, 8, 9 | 更新節點2的深度為1 | | 2 | 6, 8, 9 | 更新節點1的深度為1，將節點1加入 leafs | | 3 | 8, 9, 1 | 節點2的深仍然為1 | | 4 | 9, 1 | 更新節點5的深度為1，將節點5加入 leafs | | 5 | 1, 5 | 更新節點4的深度為2 | | 6 | 5 | 更新節點2的深度為2，將節點2加入 leafs | | 7 | 2 | 更新節點7的深度為3，將節點7加入 leafs | | 8 | 7 | 更新節點4的深度為4，將節點4加入 leafs | | 9 | 4 | 更新節點0的深度為5，**這是多跑的** | </div> <br /> 3. ZeroJudge 測試結果，花費時間最久為 2.5 s，使用記憶體最多為 27.2 MB，通過測試。 <br /><br /> ## C++ 程式碼 ```cpp= #include <iostream> #include <deque> #include <cstring> using namespace std; int main(int argc, char* argv[]) { int n; cin >> n; // 由標準輸入讀取節點數量 n int m = n+1; // 節點編號從1開始，但陣列索引值從0開始，以下3個陣列長度加1 int parents[m], depth[m], num[m], leaf; // leaf 為取出的節點 memset(parents, 0, sizeof(parents)); // 每個節點的父節點資料，一維陣列，如果為0就是根節點 memset(depth, -1, sizeof(depth)); // 每個節點的深度，一維陣列 memset(num, 0, sizeof(num)); // 每個節點的子節點數量，一維陣列 deque<int> leafs; // 找深度用的葉節點，雙端佇列 for(int i=1; i<m; i++) { // 由標準輸入讀取資料，共執行 n 次 int k; cin >> k; // 每行資料開頭存入子節點數量 k if (k == 0) { // 如果子節點數量為 0 leafs.push_back(i); // 此節點為葉節點，存入 leafs depth[i] = 0; // 此節點深度為 0 } else { // 如果子節點數量不為 0 for(int j=0; j<k; j++) { // 讀取該行接下來的資料共 k 次 int c; cin >> c; // 讀取節點 i 的子節點資料，存入 c parents[c] = i; // 節點 c 的父節點為節點 i } num[i] = k; // 節點 i 的子節點數量存入 num } } while(!leafs.empty()) { // 若雙端佇列中還有元素繼續執行，最後會多跑一次根節點的深度，存到 deptho[0] // 除錯用，印出葉節點 //for(deque<int>::iterator it=leafs.begin(); it != leafs.end(); it++) { // cout << *it << " "; //} //cout << endl; leaf = leafs.front(); // 取出 leafs 中最前面的元素 leafs.pop_front(); // 移除 leafs 中最前面的元素 // 比較 leaf 的父節點深度與 leaf 深度加1，取較大者更新 leaf 的父節點深度 depth[parents[leaf]] = max(depth[parents[leaf]], depth[leaf]+1); // 除錯用，印出節點深度 //for(int i=0; i<m; i++) { // cout << depth[i] << " "; //} //cout << endl; num[parents[leaf]]--; // leaf 的父節點對應的子節點數量減1 if (num[parents[leaf]] == 0) { // 若已無子節點，將自己加入 leafs，作為之後要檢測深度的節點 leafs.push_back(parents[leaf]); } } // 計算所有節點深度總合，記得要排除 depth[0] long long sum = 0; for(int i=1; i<m; i++) { sum += depth[i]; } cout << leaf << endl; // 印出最後一個由 leafs 取出的元素，根節點 cout << sum << endl; // 印出所有節點深度總合 return 0; } ``` <br /> 程式的運作邏輯與前面的 Python 程式碼相同，ZeroJudge 測試結果，花費時間最久為 0.1 s，使用記憶體最多為 1.9 MB，通過測試。 <br /><br /> ## 2024年11月23日更新，吳邦一教授的寫法 ### Python 程式碼 花費時間最久為 0.6 s，使用記憶體最多為 18 MB，通過測試。 ```python= n = int(input()) # 節點數量 parent = [-1] + [0]*n # 1 ~ n 號節點的父節點 h = [0]*(n+1) # 1 ~ n 號節點的高度 deg = [0]*(n+1) # 1 ~ n 號節點的子節點數量 for i in range(1, n+1): # 讀取 n 行資料 child = list(map(int, input().split())) # 子節點數量及編號 deg[i] = child[0] # 子節點數量 for ch in child[1:]: # 更新對應的父節點 parent[ch] = i que = [i for i in range(1, n+1) if deg[i] == 0] # 葉節點 head = 0 # 從 que 讀取資料的索引值 ans = 0 # 答案 while head < len(que): v = que[head]; head += 1 ans += h[v] # 更新 ans p = parent[v] # v 對應的父節點 p if p == 0: break # 根節點，中止迴圈 h[p] = max(h[p], h[v]+1) # 更新 h[p]，取 h[p] 及 h[v]+1 較大者 deg[p] -= 1 # p 的子節點數量減 1 if deg[p] == 0: que.append(p) # 如果 p 沒有子節點了，加入 que print(que[-1]) print(ans) ``` ### C++ 程式碼 花費時間最久為 39 ms，使用記憶體最多為 3.4 MB，通過測試。 ```cpp= #include <iostream> #include <vector> #include <queue> #include <algorithm> typedef long long LL; using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); LL n; cin >> n; vector<LL> parent (n+1, 0), h (n+1, 0), deg (n+1, 0); parent[0] = -1; for(LL i=1; i<=n; i++) { LL k; cin >> k; deg[i] = k; for(LL j=0; j<k; j++) { LL ch; cin >> ch; parent[ch] = i; } } queue<LL> que; for(LL i=1; i<=n; i++) { if (deg[i] == 0) que.push(i); } LL ans = 0, v = 0; while(!que.empty()) { v = que.front(); que.pop(); ans += h[v]; LL p = parent[v]; if (p == 0) break; h[p] = max(h[p], h[v]+1); deg[p]--; if (deg[p] == 0) que.push(p); } cout << v << "\n"; cout << ans << "\n"; return 0; } ``` <br /><br /> ## 參考資料 1. 黃建庭（2019）。**C++程式設計解題入門 融入程式設計競賽與APCS實作題（第二版）**。臺北市：碁峰資訊。 2. 吳燦銘（2020）。**APCS大學程式設計先修檢測：C++超效解題致勝祕笈**。新北市：博碩文化。 3. 吳燦銘（2019）。**APCS大學程式設計先修檢測：Python超效解題致勝祕笈**。新北市：博碩文化。 4. 吳邦一教授的 **[AP325-Python 第3章 佇列與堆疊](https://hackmd.io/L9sVPW65R8yu0voahymg7g)** --- ###### tags:`APCS`、`C++`、`Python`