d107: P-8-8. 樹的最大獨立集
Tags : 圖論
Accepted rate : 67人/69人 ( 97% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-07-19 16:16

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
6
Sample Input #2
8
0 1 2 3 3 2 2
Sample Output #2
5
測資資訊:
記憶體限制: 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
沒有發現任何「解題報告」