# APCS實作題2016年3月第4題：血緣關係

> 日期：2024年8月26日
> 作者：王一哲
> 題目來源：[105年3月5日實作題第4題](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2020/10/APCS-%E5%AF%A6%E4%BD%9C%E9%A1%8C-2016.03.05.pdf)
> [ZeroJudge 單筆測資版本題目連結](https://zerojudge.tw/ShowProblem?problemid=h032)
> [ZeroJudge 多筆測資版本題目連結](https://zerojudge.tw/ShowProblem?problemid=b967)

<br />

## 題目

### 問題描述

小宇有一個大家族。有一天，他發現記錄整個家族成員和成員間血緣關係的家族族譜。小宇對於最遠的血緣關係 (我們稱之為"血緣距離") 有多遠感到很好奇。

下圖為家族的關係圖。0 是 7 的孩子，1、2 和 3 是 0 的孩子，4 和 5 是 1 的孩子，6 是 3 的孩子。我們可以輕易的發現最遠的親戚關係為 4(或 5)和 6，他們的"血緣距離"是 4 (4 ~ 1，1 ~ 0，0 ~ 3，3 ~ 6)。

給予任一家族的關係圖，請找出最遠的"血緣距離"。你可以假設只有一個人是整個家族成員的祖先，而且沒有兩個成員有同樣的小孩。

<img height="40%" width="40%" src="https://i.imgur.com/ALDTyWr.png" style="display: block; margin-left: auto; margin-right: auto;"/>
<br />

### 輸入格式

第一行為一個正整數 $n$ 代表成員的個數，每人以 $0$ ~ $n-1$ 之間惟一的編號代表。接著的
$n-1$ 行，每行有兩個以一個空白隔開的整數 $a$ 與 $b$ ($0 \leq a, b \leq n-1$)，代表 $b$ 是 $a$ 的孩子。
<br />

### 輸出格式

每筆測資輸出一行最遠"血緣距離"的答案。
<br />

### 範例一：輸入

8
0 1
0 2
0 3
7 0
1 4
1 5
3 6

### 範例一：正確輸出

4

（說明）如題目所附之圖，最遠路徑為 4 → 1 → 0 → 3 → 6 或 5 → 1 → 0 → 3 → 6，距離為 4。

<img height="40%" width="40%" src="https://imgur.com/x07ATaE.png" style="display: block; margin-left: auto; margin-right: auto;"/>
<div style="text-align:center">範例一</div>
<br />

### 範例二：輸入

4
0 1
0 2
2 3

### 範例二：正確輸出

3

（說明）最遠路徑為 1 → 0 → 2 → 3，距離為 3。

<img height="23%" width="23%" src="https://imgur.com/45gYhbQ.png" style="display: block; margin-left: auto; margin-right: auto;"/>
<div style="text-align:center">範例二</div>
<br />

### 評分說明

輸入包含若干筆測試資料，每一筆測試資料的執行時間限制(time limit)均為 2 秒，依正確通過測資筆數給分。其中，
- 第 1 子題組 10 分，整個家族的祖先最多 2 個小孩，其他成員最多一個小孩，$2 \leq n \leq 100$。
- 第 2 子題組 30 分，$2 \leq n \leq 100$。
- 第 3 子題組 30 分，$101 \leq n \leq 2,000$ 。
- 第 4 子題組 30 分，$1,001 \leq n \leq 100,000$。

<br />

## Python 程式碼

### 寫法1，先由下到上找根節點，再找樹的直徑

單筆測資版，費時最久約 0.9 s，使用記憶體最多 13.3 MB，通過測試。

n = int(input())  # 成員個數
par = [-1]*n  # 編號 0 ~ n-1 對應的父節點，-1 為根節點
deg = [0]*n  # 子節點數量，如果是0則是葉節點

for _ in range(n-1):  # 讀取 n-1 行資料
    a, b = map(int, input().split())  # 讀取 a, b
    par[b] = a  # a 是 b 的父節點
    deg[a] += 1  # a 的子節點數量加 1

""" bottom-up 由下到上找根節點 """
que = [int(x) for x in range(n) if deg[x] == 0]  # 找出葉節點
head = 0  # 從 que 讀取資料用的索引值
while head < len(que):  # 如果 head 還沒有出界繼續執行
    u = que[head]; head += 1  # 由 que 讀取目前走訪的節點 u，head 加 1
    v = par[u]  # 讀取 u 的父節點 v
    if v == -1: break  # 找到根節點了
    deg[v] -= 1  # v 節子節點數量減 1
    if deg[v] == 0: que.append(v)  # 將 v 加入要走訪的佇列

""" 由根節點往下找樹的直徑 """
dia = 0  # 樹的直徑，預設為 0
hei = [0]*n  # 每個節點的高度
for u in que[:-1]:  # 由 que 依序讀取最後一個以外的節點，不要讀到最後的根節點
    v = par[u]  # 讀取 u 的父節點 v
    dia = max(dia, hei[u]+hei[v]+1)
    # 如果 u 的高度加 1 較大，更新 v 的高度
    hei[v] = max(hei[v], hei[u]+1)

print(dia)  # 印出答案

<br /><br />

多筆測資版，費時最久約 0.8 s，使用記憶體最多 13.3 MB，通過測試。

while True:
    try: n = int(input())  # 試著讀取成員個數
    except EOFError: break  # 如果遇到 EOFError 中止 while 迴圈
    par = [-1]*n  # 編號 0 ~ n-1 對應的父節點，-1 為根節點
    deg = [0]*n  # 子節點數量，如果是0則是葉節點

    for _ in range(n-1):  # 讀取 n-1 行資料
        a, b = map(int, input().split())  # 讀取 a, b
        par[b] = a  # a 是 b 的父節點
        deg[a] += 1  # a 的子節點數量加 1

    """ bottom-up 由下到上找根節點 """
    que = [int(x) for x in range(n) if deg[x] == 0]  # 找出葉節點
    head = 0  # 從 que 讀取資料用的索引值
    while head < len(que):  # 如果 head 還沒有出界繼續執行
        u = que[head]; head += 1  # 由 que 讀取目前走訪的節點 u，head 加 1
        v = par[u]  # 讀取 u 的父節點 v
        if v == -1: break  # 找到根節點了
        deg[v] -= 1  # v 節子節點數量減 1
        if deg[v] == 0: que.append(v)  # 將 v 加入要走訪的佇列

    """ 由根節點往下找樹的直徑 """
    dia = 0  # 樹的直徑，預設為 0
    hei = [0]*n  # 每個節點的高度
    for u in que[:-1]:  # 由 que 依序讀取最後一個以外的節點，不要讀到最後的根節點
        v = par[u]  # 讀取 u 的父節點 v
        dia = max(dia, hei[u]+hei[v]+1)  # 更新 dia
        hei[v] = max(hei[v], hei[u]+1)  # 如果 u 的高度加 1 較大，更新 v 的高度

    print(dia)  # 印出答案

<br /><br />

### 寫法2，用 BFS 找最遠的節點，再找樹的直徑

單筆測資版，費時最久約 0.7 s，使用記憶體最多 28.3 MB，通過測試。

n = int(input())  # 成員個數
adj = [[] for _ in range(n)]  # 無向圖，編號 0 ~ n-1 節點各自相連的節點
for _ in range(n-1):  # 讀取 n-1 行資料
    a, b = map(int, input().split())  # 讀取 a, b
    adj[a].append(b)  # a、b 相連
    adj[b].append(a)  # b、a 相連

""" 自訂函式 BFS """
def BFS(s):  # 輸入起點 s
    dis = [-1]* n  # 距離，預設為 -1 代表還沒有走訪
    dis[s] = 0  # 起點的距離為 0
    que = [s]  # 要走訪的節點
    head = 0  # 從 que 讀取資料用的索引值
    while head < len(que):  # 如果 head 還沒有出界繼續執行
        u = que[head]; head += 1  # 由 que 讀取目前走訪的節點 u，head 加 1
        for v in adj[u]:  # 依序讀取與 u 相連的節點 v
            if dis[v] < 0:  # v 還沒有走訪
                dis[v] = dis[u] + 1  # 更新 v 的距離為 u 的距離加 1
                que.append(v)  # 將 v 加入 que
    return que[-1], dis[que[-1]]  # 回傳最後一個節點及距離

""" 呼叫 BFS """
u, _ = BFS(0)  # 代入節點 0，回傳最遠的節點 u，距離不重要
_, d = BFS(u)  # 代入節點 u，回傳最遠的距離 d，節點不重要
print(d)  # 印出答案

<br /><br />

多筆測資版，費時最久約 0.7 s，使用記憶體最多 28.3 MB，通過測試。

while True:
    try: n = int(input())  # 試著讀取成員個數
    except EOFError: break  # 如果遇到 EOFError 中止 while 迴圈
    adj = [[] for _ in range(n)]  # 無向圖，編號 0 ~ n-1 節點各自相連的節點
    for _ in range(n-1):  # 讀取 n-1 行資料
        a, b = map(int, input().split())  # 讀取 a, b
        adj[a].append(b)  # a、b 相連
        adj[b].append(a)  # b、a 相連

    """ 自訂函式 BFS """
    def BFS(s):  # 輸入起點 s
        dis = [-1]* n  # 距離，預設為 -1 代表還沒有走訪
        dis[s] = 0  # 起點的距離為 0
        que = [s]  # 要走訪的節點
        head = 0  # 從 que 讀取資料用的索引值
        while head < len(que):  # 如果 head 還沒有出界繼續執行
            u = que[head]; head += 1  # 由 que 讀取目前走訪的節點 u，head 加 1
            for v in adj[u]:  # 依序讀取與 u 相連的節點 v
                if dis[v] < 0:  # v 還沒有走訪
                    dis[v] = dis[u] + 1  # 更新 v 的距離為 u 的距離加 1
                    que.append(v)  # 將 v 加入 que
        return que[-1], dis[que[-1]]  # 回傳最後一個節點及距離

    """ 呼叫 BFS """
    u, _ = BFS(0)  # 代入節點 0，回傳最遠的節點 u，距離不重要
    _, d = BFS(u)  # 代入節點 u，回傳最遠的距離 d，節點不重要
    print(d)  # 印出答案

<br /><br />

## C++ 程式碼

### 寫法1，先由下到上找根節點，再找樹的直徑

單筆測資版，費時最久約 32 ms，使用記憶體最多 2.4 MB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    int n; cin >> n; // 成員數量
    vector<int> par (n, -1);  // 每個子節點對應的父節點，-1 為根節點
    vector<int> deg (n, 0);  // 每個節點的子節點數量
    for(int i=0; i<n-1; i++) {  // 讀取 n-1 行資料
        int a, b; cin >> a >> b;  // 讀取節點 a、b
        par[b] = a;  // b 節父節點為 a
        deg[a]++;  // a 的子節點數量加 1
    }

    vector<int> que;  // 要走訪的葉節點
    for(int i=0; i<n; i++) {  // 依序讀取 deg 的資料
        if (deg[i] == 0) que.push_back(i);  // 如果 deg[i] 為 0，將 i 加入 que
    }
    
    int head = 0;  // 由 que 讀取資料用的索引值
    while(head < (int)que.size()) {  // 當 head 還沒有出界時繼續執行
        int u = que[head]; head++;  // 讀取 que[head]，head 加 1
        int v = par[u];  // 讀取 u 的父節點 v
        if (v == -1) break;  // 找到根節點了
        deg[v]--;  // v 的子節點數量減 -1
        if (deg[v] == 0) que.push_back(v);  // 如果 v 的子節點數量歸零，將 v 加入 que
    }
    
    int dia = 0;  // 樹的直徑
    vector<int> hei (n, 0);  // 各節點的高度
    for(int i=0; i<(int)que.size()-1; i++) {  // 不要讀到 que 最後一項
        int u = que[i];  // 讀取節點 u
        int v = par[u];  // 讀取 u 的父節點 v
        dia = max(dia, hei[v]+hei[u]+1);  // 更新 dia
        hei[v] = max(hei[v], hei[u]+1);  // 如果 u 的高度加 1 較大，更新 v 的高度
    }
    cout << dia << "\n";  // 印出答案
    return 0;
}

<br /><br />

多筆測資版，費時最久約 32 ms，使用記憶體最多 2.3 MB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    int n; 
    while(cin >> n) {  // 如果有讀到成員數量繼續執行
        vector<int> par (n, -1);  // 每個子節點對應的父節點，-1 為根節點
        vector<int> deg (n, 0);  // 每個節點的子節點數量
        for(int i=0; i<n-1; i++) {  // 讀取 n-1 行資料
            int a, b; cin >> a >> b;  // 讀取節點 a、b
            par[b] = a;  // b 節父節點為 a
            deg[a]++;  // a 的子節點數量加 1
        }
    
        vector<int> que;  // 要走訪的葉節點
        for(int i=0; i<n; i++) {  // 依序讀取 deg 的資料
            if (deg[i] == 0) que.push_back(i);  // 如果 deg[i] 為 0，將 i 加入 que
        }
        
        int head = 0;  // 由 que 讀取資料用的索引值
        while(head < (int)que.size()) {  // 當 head 還沒有出界時繼續執行
            int u = que[head]; head++;  // 讀取 que[head]，head 加 1
            int v = par[u];  // 讀取 u 的父節點 v
            if (v == -1) break;  // 找到根節點了
            deg[v]--;  // v 的子節點數量減 -1
            if (deg[v] == 0) que.push_back(v);  // 如果 v 的子節點數量歸零，將 v 加入 que
        }
        
        int dia = 0;  // 樹的直徑
        vector<int> hei (n, 0);  // 各節點的高度
        for(int i=0; i<(int)que.size()-1; i++) {  // 不要讀到 que 最後一項
            int u = que[i];  // 讀取節點 u
            int v = par[u];  // 讀取 u 的父節點 v
            dia = max(dia, hei[v]+hei[u]+1);  // 更新 dia
            hei[v] = max(hei[v], hei[u]+1);  // 如果 u 的高度加 1 較大，更新 v 的高度
        }
        cout << dia << "\n";  // 印出答案
    }
    return 0;
}

<br /><br />

### 寫法2，用 BFS 找最遠的節點，再找樹的直徑

單筆測資版，費時最久約 54 ms，使用記憶體最多 8 MB，通過測試。

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

pair<int, int> BFS(int s, vector<vector<int>>& adj) {  // 輸入起點 s，節點數量 n，相連節點 adj，輸出最後一個節點及距離
    vector<int> dis (adj.size(), -1);  // 節點距離，-1 代表未走訪
    vector<int> que = {s};  // 要走訪的節點，先放入起點 s
    int head = 0;  // 由 que 讀取資料的索引值
    dis[s] = 0;  // 起點距離為 0
    while(head < (int)que.size()) {  // 如果 head 還沒有出界繼續執行
        int u = que[head]; head++;  // 讀取 que[head]，head 加 1
        for(int v : adj[u]) {  // 依序取出 u 相連的節點 v
            if (dis[v] < 0) {  // 如果 v 還沒有走訪
                dis[v] = dis[u] + 1;  // 更新 v 的距離
                que.push_back(v);  // 將 v 加入 que
            }
        }
    }
    return make_pair(que.back(), dis[que.back()]);  // 回傳最後一個節點及距離
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    int n; cin >> n;  // 成員數量
    vector<vector<int>> adj (n, vector<int> ());  // 相連的節點 
    for(int i=0; i<n-1; i++) {  // 讀取 n-1 行資料
        int a, b; cin >> a >> b;  // 讀取節點 a、b
        adj[a].push_back(b);  // a、b 相連
        adj[b].push_back(a);  // b、a 相連
    }
    pair<int, int> t, d;  // 接收回傳結果用的 pair
    t = BFS(0, adj);  // 代入節點 0，回傳最遠的節點，距離不重要
    d = BFS(t.first, adj);  // 代入節點 t.first，回傳最遠的距離，節點不重要
    cout << d.second << "\n";  // 印出答案
    return 0;
}

<br /><br />

多筆測資版，費時最久約 63 ms，使用記憶體最多 8 MB，通過測試。

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

pair<int, int> BFS(int s, vector<vector<int>>& adj) {  // 輸入起點 s，節點數量 n，相連節點 adj，輸出最後一個節點及距離
    vector<int> dis (adj.size(), -1);  // 節點距離，-1 代表未走訪
    vector<int> que = {s};  // 要走訪的節點，先放入起點 s
    int head = 0;  // 由 que 讀取資料的索引值
    dis[s] = 0;  // 起點距離為 0
    while(head < (int)que.size()) {  // 如果 head 還沒有出界繼續執行
        int u = que[head]; head++;  // 讀取 que[head]，head 加 1
        for(int v : adj[u]) {  // 依序取出 u 相連的節點 v
            if (dis[v] < 0) {  // 如果 v 還沒有走訪
                dis[v] = dis[u] + 1;  // 更新 v 的距離
                que.push_back(v);  // 將 v 加入 que
            }
        }
    }
    return make_pair(que.back(), dis[que.back()]);  // 回傳最後一個節點及距離
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    int n; 
    while(cin >> n) {  // 如果有讀到成員數量繼續執行
        vector<vector<int>> adj (n, vector<int> ());  // 相連的節點 
        for(int i=0; i<n-1; i++) {  // 讀取 n-1 行資料
            int a, b; cin >> a >> b;  // 讀取節點 a、b
            adj[a].push_back(b);  // a、b 相連
            adj[b].push_back(a);  // b、a 相連
        }
        pair<int, int> t, d;  // 接收回傳結果用的 pair
        t = BFS(0, adj);  // 代入節點 0，回傳最遠的節點，距離不重要
        d = BFS(t.first, adj);  // 代入節點 t.first，回傳最遠的距離，節點不重要
        cout << d.second << "\n";  // 印出答案
    }
    return 0;
}

<br /><br />

## 參考資料

1. 吳邦一教授的 APCS 解題影片〈[PyAp45 ZJ_b967. Python APCS 題解：血緣關係(AP201603_4)](https://youtu.be/WVLEUoR-uT8?si=9YTeNOBXVCCwj0y1)〉
2. 吳邦一教授的 APCS 講義〈[AP325-Python 第8章 樹上演算法 (III)](https://hackmd.io/@bangyewu/rymQ7w7_a#P-8-14-%E8%A1%80%E7%B7%A3%E9%97%9C%E4%BF%82-APCS201603)〉

---

###### tags:`APCS`、`Python`、`C++`