d025. 例題 P-3-1. 樹的高度與根 (bottom-up) (APCS201710) (同 P-8-4-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 \leq 10^5$。

輸出說明

第一行輸出根的編號，

第二行輸出高度總和。

範例輸入 #1

範例輸出 #1

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

提示：

標籤:

出處:

AP325 [管理者：

TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」