P-8-8. 樹的最大獨立集
輸入一棵有 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
留言