a145:
P-3-1.樹的高度與根
內容
有一個大家族有 N個成員，編號 1 N，我們請每個成員寫下此家族中哪幾位是他的孩子。我們要計算每個人有幾代的子孫，這個值稱為他在這個族譜中的高度，也就是說，編號 i 的人如果高度記做h(i)，那麼h(i)就表示在所有 i的子孫中，最遠的子孫 與他隔了幾代。本題假設除了最高的一位祖先(稱為 root)之外，其他成員的 pareNt 都在此家族中(且只有一個 parent)。本題要計算所有成員高度的總和以及根的編號。
右圖是一個例子，每個成員是一個圈起來的號碼，劃線相聯的表示上面的點是下面點的 parent。編號 4 是根，有兩個孩子 1與7。編號6,9,3,8都沒有孩子， h(6)=h(9)=h(3)=h(8)=0，此外 h(2)=2 因為 9 與他隔兩代。你可以看出來h(5)=h(1)=1，h(7)=3,h(4)=4，所以高度總和是11
輸入說明
第一行有一個正整數 N。接下來有 N 行，第 i 行的第一個數字 k 代表 i 有 k 個孩子，第 i 行接下來的 k 個數字就是孩子的編號。每一行的相鄰數字間以空白隔開。N≤105
輸出說明
第一行輸出根的編號，第二行輸出高度總和。
範例輸入
#1
9 1 6 3 5 3 8 0 2 1 7 1 9 0 1 2 0 0
範例輸出
#1
4 11
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (16%): 1.0s , <1M
公開 測資點#1 (16%): 1.0s , <1M
公開 測資點#2 (17%): 1.0s , <1M
公開 測資點#3 (17%): 1.0s , <1M
公開 測資點#4 (17%): 1.0s , <1M
公開 測資點#5 (17%): 1.0s , <1M
公開 測資點#0 (16%): 1.0s , <1M
公開 測資點#1 (16%): 1.0s , <1M
公開 測資點#2 (17%): 1.0s , <1M
公開 測資點#3 (17%): 1.0s , <1M
公開 測資點#4 (17%): 1.0s , <1M
公開 測資點#5 (17%): 1.0s , <1M
提示 ：
標籤:
出處:
APCS201710P-3-1ap3to5
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||