b967. 4. 血緣關係 - 高中生程式解題系統

內容

APCS 201603-4 血緣關係

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

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

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

輸入說明

第一行為一個正整數 N 代表成員的個數，每人以 0~N-1 之間唯一的編號代表。
接著的 N-1 行，每行有兩個以一個空白隔開的整數 a 與 b (0 ≤ a, b ≤ N-1)，代表 b 是 a 的孩子。

其中 10%的測資滿足， 2 ≤ N ≤ 100 ，整個家族的祖先最多 2 個小孩，其他成員最多一個小孩。
其中 40%的測資滿足， 2 ≤ N ≤ 100。
其中 70%的測資滿足， 2 ≤ N ≤ 2000。
其中100%的測資滿足， 2 ≤ N ≤ 100000。

輸出說明

輸出一行，輸出最遠"血緣距離"的答案。

範例輸入 #1

範例輸出 #1

範例輸入 #2

範例輸出 #2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 0.5s , <1K
公開測資點#1 (5%): 0.5s , <1K
公開測資點#2 (5%): 0.5s , <1K
公開測資點#3 (5%): 0.5s , <1K
公開測資點#4 (5%): 0.5s , <1K
公開測資點#5 (5%): 0.5s , <1K
公開測資點#6 (5%): 0.5s , <1K
公開測資點#7 (5%): 0.5s , <1K
公開測資點#8 (5%): 0.5s , <1M
公開測資點#9 (5%): 0.5s , <1M
公開測資點#10 (5%): 0.5s , <1M
公開測資點#11 (5%): 0.5s , <1M
公開測資點#12 (5%): 0.5s , <1M
公開測資點#13 (5%): 0.5s , <1M
公開測資點#14 (5%): 1.0s , <10M
公開測資點#15 (5%): 1.0s , <10M
公開測資點#16 (5%): 1.0s , <10M
公開測資點#17 (5%): 1.0s , <10M
公開測資點#18 (5%): 1.0s , <10M
公開測資點#19 (5%): 1.0s , <10M

提示：

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

第二筆說明：最遠路徑為 1→0→2→3，距離為 3 。

標籤:

APCS

出處:

2016年3月 apcs [管理者： snail (蝸牛) ]

編號	身分	題目	主題	人氣	發表日期
37583	edoctopus322 ... (Moon Jam)	b967	解題思路（含一些小技巧）	782	2023-09-17 21:29
38395	qerpzzea@gma ... (賽希爾 cecill(陳宥穎))	b967	TLE	249	2023-11-18 11:23
37400	wrr606@gmail ... (Function)	b967	cin/cout加速還是過不去的看這裡	369	2023-09-05 22:05
37399	wrr606@gmail ... (Function)	b967	cin/cout加速還是過不去的看這裡	262	2023-09-05 22:05
36642	fire5386 (becaidorz)	b967	題解	636	2023-07-31 00:40