b967. 4. 血緣關係
標籤 : APCS
通過比率 : 1540人/2193人 ( 70% ) [非即時]
評分方式:
Strictly

最近更新 : 2024-02-01 10:57

內容

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
8
0 1
0 2
0 3
7 0
1 4
1 5
3 6
範例輸出 #1
4
範例輸入 #2
4
0 1
0 2
2 3
範例輸出 #2
3
測資資訊:
記憶體限制: 512 MB
提示 :

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

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

標籤:
APCS
出處:
2016年3月apcs [管理者: snail (蝸牛) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
40483 youtong826 (Youtong0826) b967
1~4 題完題目解析
553 2024-05-24 02:50
37583 edoctopus322 ... (Moon Jam) b967
1463 2023-09-17 21:29
41433 glps1004@gma ... (Ian) b967
APCS 201603全解析
251 2024-07-26 13:56
38395 qerpzzea@gma ... (賽希爾 cecill(陳宥穎)) b967
517 2023-11-18 11:23
37400 wrr606@gmail ... (Function) b967
621 2023-09-05 22:05