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


提交答案

分數: 100 (部分)
時間限制: 1.0s
記憶體限制: 1G

作者:
題目類型

輸入一棵有 n 個點的樹,我們要挑選一群彼此不相鄰的點,而且挑選的點越多點越好。 請計算最多可以挑多少點。

輸入格式

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

輸出格式

最多可以挑選幾點。

範例輸入 1

9
0 0 1 1 2 2 2 6

範例輸出 1

6

範例輸入 2

8
0 1 2 3 3 2 2

範例輸出 2

5

留言

目前沒有評論。