d114:
P_8_8 樹的最大獨立集
Content
輸入一棵有 $n$ 個點的樹，我們要挑選一群彼此不相鄰的點，而且挑選的點越多點越好。請計算最多可以挑多少點。以下圖為例，我們可以挑 $\{0,3,4,5,6,7\}$ 共 $6$ 點，沒有辦法挑出更多的不相鄰的點。
Input
第一行是正整數 $n$，代表點數，點以 $0 \sim (n-1)$編號，$0$ 是根，
第二行有 $(n-1)$ 個正整數，$p_1, p_2, \dots ,p_{n-1}$，依序是編號 $1 \sim (n-1)$各點的parent。
n不超過$10^5$，相鄰數字以空白間隔。
Output
最多可以挑選幾點。
Sample Input
#1
9 0 0 1 1 2 2 2 6
Sample Output
#1
6
Sample Input
#2
8 0 1 2 3 3 2 2
Sample Output
#2
5
測資資訊：
記憶體限制：
256
MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
Hint ：
Tags:
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||