###### tags: `APCS`
# **c463－樹狀圖分析**
### **題目連結：** [**c463**](https://zerojudge.tw/ShowProblem?problemid=c463)
### **題目解析**
這題要求我們找出一個樹狀圖的根節點編號，並計算整個樹的總高度 H(T)。樹的根節點是沒有父節點的節點，而樹的總高度是所有節點高度的總和。
### **解題方向**
1. **讀取資料**：首先讀取樹的節點個數`n`**，然後逐個讀取每個節點的子節點資訊。對於每個節點，先讀入其子節點的數量**`k`**，然後讀入**`k`個子節點的編號。
2. **構建樹結構**：利用鄰接表`G`**來存儲樹的結構。**`G`**是一個列表的列表，其中**`G[i]`**包含了節點**`i`**的所有子節點。同時，使用**`Parent`列表來記錄每個節點的父節點編號，初始值為 -1。
3. **尋找根節點**：根節點是沒有父節點的節點，即`Parent`列表中值為 -1 的節點。
4. **計算樹的高度**：透過深度優先搜索（DFS）遍歷樹，計算從每個節點到葉節點的最大距離，這個距離稱為節點的高度。函數`dfs(node)`**遞迴地計算給定節點的高度，並更新全局**`height`**列表，其中**`height[i]`**表示節點**`i`的高度。
5. **計算樹的高度和**：樹的高度和（H(T)）是樹中所有節點的高度之和。遍歷`height`列表，將所有節點的高度累加得到總和。
6. **輸出結果**：輸出根節點的編號（由於節點編號從1開始，而列表索引從0開始，因此輸出時需要加1）和樹的高度和。
### **程式解析**
範例輸入：
7
0
2 6 7
2 1 4
0
2 3 2
0
0

1. **讀取節點個數 `n = 7`**：這意味著樹狀圖有7個節點。
2. **初始化結構**：
- **`G = [ [] for i in range(n) ]`** 創建一個包含7個空列表的列表，用於存儲每個節點的子節點。
- **`Parent = [ -1 for i in range(n) ]`** 創建一個長度為7的列表，初始值都為-1，用來記錄每個節點的父節點。
3. **構建樹結構**：逐行讀取節點的子節點資訊。
- 第1個節點：沒有子節點。
- 第2個節點：有2個子節點，分別是節點6和節點7。因此，**`G[1] = [5, 6]`**（編號減1以符合Python索引）。
- 第3個節點：有2個子節點，分別是節點1和節點4。因此，**`G[2] = [0, 3]`**。
- 以此類推，直到所有節點的子節點資訊都被讀取和存儲。
4. **尋找根節點**：在構建樹結構的過程中，對於每個子節點，都將其對應的父節點編號記錄在`Parent`**列表中。最終，**`Parent`列表中仍為-1的項目即為根節點。在這個例子中，假設最終找到的根節點為5（即列表中的編號4）。
5. **DFS遞迴計算高度**：從根節點開始進行深度優先搜索（DFS）。
- 假設從節點5開始，**`dfs(5)`**被調用。由於節點5有2個子節點（節點3和節點2），因此會分別對這些子節點進行DFS遞迴調用，即**`dfs(3)`**和**`dfs(2)`**。
- 在`dfs(3)`**中，由於節點3沒有子節點，其高度設為0。返回後，繼續處理**`dfs(2)`，依此類推。
6. **計算高度和**：每次DFS調用返回時，都會更新當前節點的高度，並將其添加到高度和中。在這個例子中，如果節點5的兩個子節點的最大高度是3（假設），那麼節點5的高度就是4。
7. **輸出結果**：
- 根節點編號：5（根據步驟4中的發現）。
- 高度和：對所有節點的高度進行加總。假設在這個例子中加總結果為4。
### **完整程式碼**

#
# c463 樹狀圖分析 NA40%
# Part1 基本寫法 for DFS
# 不考慮 IO優化, 不考慮 DP
#

import sys
sys.setrecursionlimit(1000000)

def dfs(node):
    global height

    if len(G[node]) == 0:
        height[node] = 0
        return 0

    else:
        mx = 0
        for i in G[node]:
            dfs(i)
            # 同一個 node 在不同 dfs 下哪個高度比較高
            # 最後更新回 height list
            mx = max(mx, height[i]+1)

        height[node] = mx


# start
n = int(input())

G = [ [] for i in range(n) ] # 創造 graph 的結構
Parent = [ -1 for i in range(n) ]


for i in range(n):
    row = list(map(int, input().split()))

    if row[0]>0:
        # 取出第一個之後的元素（因為第一個數代表有幾個子節點，後面的數字才是節點值）
        t = []
        for x in range(1, len(row)):
            t.append(row[x]-1)
            #  是將子節點的編號轉換為0基的索引（因為在Python中，清單索引從0開始）

        G[i] = t

        for j in G[i]:
            Parent[j] = i # 指派父節點

# 尋找 Parent list 中, 仍然是 -1 的為 root
for r in range(n):
    if Parent[r] == -1:
        root = r
        break

height = [ 0 for x in range(n) ]

# 由根開始探索
dfs(root)

ans = 0
for x in range(n):
    ans += height[x]

print(root+1)
print(ans)

[**AC版詳解**](https://yuihuang.com/zj-c463/)