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

> 日期：2023年6月19日
> 作者：王一哲
> 題目來源：[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的 C++ 程式碼改寫而成，於 ZeroJudge 測試時，第18筆測資會因為遞迴深度過深被系統中止，其它筆測資可以通過測試。

md = 0
def DFS(x):
    global md
    max1, max2, result = 0, 0, 0
    if len(F[x]) == 0: return 0
    if len(F[x]) == 1: return DFS(F[x][0]) + 1
    else:
        for i in range(len(F[x])):
            result = DFS(F[x][i]) + 1
            if i == 0: max1 = result
            elif i == 1:
                if max1 >= result:
                    max2 = result
                else:
                    max1, max2 = result, max1
            else:
                if max1 <= result:
                    max1, max2 = result, max1
                elif max2 < result:
                    max2 = result
        md = max(md, max1+max2)
        return max1

n = int(input())
F = [[] for _ in range(n)]
isChild = [False]*n

for _ in range(n-1):
    a, b = map(int, input().split())
    F[a].append(b)
    if not isChild[b]: isChild[b] = True

root = isChild.index(False)
rd = DFS(root)
md = max(rd, md)
print(md)

<br /><br />

## 參考資料

1. 黃建庭（2019）。**C++程式設計解題入門 融入程式設計競賽與APCS實作題（第二版）**。臺北市：碁峰資訊。
2. 吳燦銘（2020）。**APCS大學程式設計先修檢測：C++超效解題致勝祕笈**。新北市：博碩文化。
3. 溫嘉榮（2019）。**Python程式設計技巧 發展運算思維（含「APCS先修檢測」解析）**。臺北市：碁峰資訊。
4. 吳燦銘（2019）。**APCS大學程式設計先修檢測：Python超效解題致勝祕笈**。新北市：博碩文化。

---

###### tags:`APCS`、`Python`