有一個大家族有 $N$ 個成員,編號 $1 \sim 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 ≤ 10^5$。
接下來有 $N$ 行,第 $i$ 行的第一個數字 $k$ 代表 $i$ 有 $k$ 個孩子,第 $i$ 行接下來的 $k$ 個數字就是孩子的編號。同一行的相鄰數字間以空白隔開。
第一行輸出根的編號,第二行輸出高度總和。
9 1 6 3 5 3 8 0 2 1 7 1 9 0 1 2 0 0
4 11
ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |