###### tags: `APCS` `C463` `C`
# C463. 樹狀圖分析
## 題目描述
### 內容
本題是關於有根樹(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$ 都是葉節點。
樹狀圖中的兩個節點 $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(h(v))$。
給定一個樹狀圖 $T$，請找出 $T$ 的根節點以及高度總和 $H(T)$。
### 輸入說明
第一行有一個正整數 $n$ 代表樹狀圖的節點個數，節點的編號為 $1~n$。
接下來有 $n$ 行，第 $i$ 行的第一個數字 $k$ 代表節點 $i$ 有 $k$ 個子節點，
第 i 行接下來的 k 個數字就是這些子節點的編號。
每一行的相鄰數字間以空白隔開。
### 輸出說明
輸出兩行各含有一個整數，第一行是根節點的編號，第二行是 $H(T)$。
### 評分說明
輸入包含若干筆測試資料，每一筆測試資料的執行時間限制 $($Time Limit$)$ 均為1秒，
依正確通過測資筆數給分。測資範圍如下，其中 k 是每個節點的子節點數量上限：
第一題組 $(10$ %$)$：$1 ≤ n ≤ 4$，$k ≤ 3$，除了根節點之外都是葉節點。
第二題組 $(30$ %$)$：$1 ≤ n ≤ 1,000$，$k ≤ 3$。
第三題組 $(30$ %$)$：$1 ≤ n ≤ 100,000$，$k ≤ 3$。
第四題組 $(30$ %$)$：$1 ≤ n ≤ 100,000$，$k$ 無限制。
### 範例
測資 1：
7
0
2 6 7
2 1 4
0
2 3 2
0
0
輸出 1：
5
4
測資 2：
9
1 6
3 5 3 8
0
2 1 7
1 9
0
1 2
0
0
輸出 2：
4
11
***
## 題目思索
先從測資與每個節點之間的關係來看，第 1 行是總節點個數，代表有 n 個節點，從下一行開始的第 i 行的第一個數是編號 i 節點的子節點總數 (若為 0，則為該樹的葉節點)，而同行後面的數代表各子節點的編號。(1 ≤ i ≤ n)
先將 n 儲存，再透過之後每一行的行數 (即 i 節點) 存為各子節點的父節點。
```c
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &tree[i]);
if(tree[i] == 0){ //如果子節點數為零，存入至葉節點陣列
leaf[count] = i;
count++;
}
else{ //將第 i 節點作為其子節點的父節點
for(int j = 0; j < tree[i]; j++){
scanf("%d", &child);
parent[child] = i;
}
}
}
```
找完各點的父節點後，若有一節點的數值為預設值 -1 時，則該節點即是根節點。
```c
for(int i = 1; i <= n; i++)
if(parent[i] < 0)
root = i;
```
最重要的部分，也就是節點距離，從葉節點開始尋找父節點，每找到一次，距離 h 加一，父節點變成下一次判斷的子節點 (target)，若父節點為預設值 -1 時，就是找到了根節點，於此同時，將距離數值存進 sum 之中。
```c
for(int i = 1; i < count; i++){
target = leaf[i];
while(parent[target] > 0){ //當此子節點的父節點仍在時(非根節點時)
h++;
target = parent[target]; //此父節點變成下次判斷的子節點
}
printf("%d %d\n", i, h);
sum += h;
h = 0;
}
```
***
### 初稿程式碼
```c=
#include <stdio.h>
int main(){
int n;
scanf("%d", &n);
int tree[n + 1], parent[n + 1], leaf[n + 1];
int count = 1, child, root = -1, target = 0, h = 0, sum = 0;
for(int i = 1; i <= n; i++){ //節點值皆設為 -1，以便區分根與葉節點
parent[i] = -1;
child[i] = -1;
}
for(int i = 1; i <= n; i++){
scanf("%d", &tree[i]);
if(tree[i] == 0){
leaf[count] = i;
count++;
}
else{
for(int j = 0; j < tree[i]; j++){
scanf("%d", &child);
parent[child] = i;
}
}
}
for(int i = 1; i <= n; i++)
if(parent[i] < 0)
root = i;
for(int i = 1; i < count; i++){
target = leaf[i];
while(parent[target] > 0){
h++;
target = parent[target];
}
sum += h;
h = 0;
}
printf("%d\n%d", root, sum);
return 0;
}
```
### 測試結果
***
### 第一次嘗試更正
當我覺得奇怪而多往題目瞄一眼時，我發現原來不是算從**每個葉節點到根節點**的距離加總，而是**每個節點到葉節點**的**最大距離**加總，所以我重新整理了思緒，將每個節點的距離 h 另存成一個陣列，再判斷當葉節點經過此節點時距離之多寡，取其中最大值，在最後將每一高度存到 sum 以便輸出。
```c
int height[i] = 0, num = 0; //num為原程式碼中的h
for(int i = 1; i < count; i++){
target = leaf[i];
num = 0;
while(parent[target] > 0){ //當仍有父節點時(非根節點時)
num++;
height[parent[target]] = (num > height[parent[target]])? num : height[parent[target]];
target = parent[target];
}
}
for(int i = 1; i <= n; i++)
sum += height[i];
```
### 第一次更正後測試結果
***
### 第二次嘗試更正
好吧，看來有溢位的可能性，於是我重新審視了一遍，需要使用 long int 的形式宣告 sum，才能將溢位的問題解決。
```c
long int sum = 0;
printf("%d\n%ld", root, sum); //這裡差點漏掉，%d改成%ld
```
之後就AC了，耶~
***
## 成果
### 程式碼
```c=
#include <stdio.h>
int main(){
int n;
scanf("%d", &n);
int tree[n + 1], parent[n + 1], leaf[n + 1], height[n + 1], count = 1, child, root = -1, target, num = 0;
long int sum = 0;
for(int i = 1; i <= n; i++){
parent[i] = -1;
leaf[i] = -1;
height[i] = 0;
}
for(int i = 1; i <= n; i++){
scanf("%d", &tree[i]);
if(tree[i] == 0){
leaf[count] = i;
count++;
}
else{
for(int j = 0; j < tree[i]; j++){
scanf("%d", &child);
parent[child] = i;
}
}
}
for(int i = 1; i <= n; i++)
if(parent[i] < 0)
root = i;
for(int i = 1; i < count; i++){
target = leaf[i];
num = 0;
while(parent[target] > 0){
num++;
height[parent[target]] = (num > height[parent[target]])? num : height[parent[target]];
target = parent[target];
}
}
for(int i = 1; i <= n; i++)
sum += height[i];
printf("%d\n%ld", root, sum);
return 0;
}
```
### 解題
***
## 反思
可惜一開始沒理解題目要求的答案，導致過程中一時想不到的問題出現，但經歷過此事後，也成為我未來解題時的前車之鑑，檢查邏輯與題意是否如何，再判斷溢位的問題，將使我解題的速度與精確度提升。
### 心智圖
***
## 題目來源
[c463. apcs 樹狀圖分析 (Tree Analyses) (From Zero Judge)](https://zerojudge.tw/ShowProblem?problemid=c463)
###### 2023-11-30 完成編寫此文
###### 2023-12-10 來源勘誤
###### 2024-1-21 格式調整
Sign in with Wallet
Connect another wallet