回『AP325題庫』
e043: 樹的高度與根 (bottom-up)
Tags :
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式：
Tolerant

最近更新 : 2024-01-15 22:48

Content

有一個大家族有 N 個成員，編號 1~N，我們請每個成員寫下此家族中哪幾位是他的孩 子。我們要計算每個人有幾代的子孫，這個值稱為他在這個族譜中的高度，也就是說， 編號 i 的人如果高度記做 h(i)，那麼 h(i)就表示在所有 i 的子孫中，最遠的子孫與他隔了幾代。本題假設除了最高的一位祖先(稱為 root)之外，其他成員的 parent 都在此家族中(且只有一個 parent)。本題要計算所有成員高度的總和以及根的編號。

 

Input

第一行有一個正整數 N。接下來有 N 行，第 i 行的第一個數字 k 代表 i 有 k 個孩子，第 i 行接下來的 k 個數字就是孩子的編號。每一行的相鄰數字間以空白隔 開。N ≤ 1e5。

Output

第一行輸出根的編號，第二行輸出高度總和。

Sample Input 
9
1 6
3 5 3 8
0
2 1 7
1 9
0
1 2
0
0
Sample Output 
4
11
測資資訊：
記憶體限制： 64 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
Hint ：

畫圖想一想

Tags:
出處:
AP325 [管理者：
Eason0165 (EasonLearner)
]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」