d107. P-8-8. 樹的最大獨立集

Content

輸入一棵有 $n$ 個點的樹，我們要挑選一群彼此不相鄰的點，而且挑選的點越多點越好。

請計算最多可以挑多少點。

Input

第一行是正整數 $n$，代表點數，點以 $0$~$n-1$ 編號，0 是根

第二行有 $n-1$ 個正整數，$p(1), p(2), …,p(n-1)$，依序是編號 $1$~$n-1$ 各點的 parent。$n$ 不超過 $10^5$，相鄰數字以空白間隔。

Output

最多可以挑選幾點。

Sample Input #1

9
0 0 1 1 2 2 2 6

Sample Output #1

Sample Input #2

8
0 1 2 3 3 2 2

Sample Output #2

測資資訊：

記憶體限制： 64 MB
不公開測資點#0 (20%): 1.0s , <1M
不公開測資點#1 (20%): 1.0s , <1K
不公開測資點#2 (20%): 1.0s , <1K
不公開測資點#3 (20%): 1.0s , <1M
不公開測資點#4 (20%): 1.0s , <1M

Hint ：

Tags:

圖論樹

出處:

AP325 [管理者：

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

]

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