TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

96.2% (25/26)

Submission's AC Ratio

34.9% (58/166)

Tags

Description

CK 公司中共有 n 個員工,其中除了編號1 的餅乾之外,每個人都恰有一個直屬長官。即 CK 公司中的人際關係網路可視為一個樹狀結構。

為了增進 CK 公司中員工的感情與強化生活資訊的交流,你決定主辦一系列共 m 場的大型活動。

現在的問題是要邀請哪些員工來參加。

為了避免某些尷尬狀況的發生(例如在活動中催收作業或舉行小考等),你不希望有員工跟他的某個長官(註)參加了在同一場活動,而當然每個員工只能參加一場活動。

(註:一個員工的長官不只有他的直屬長官,也包括他的直屬長官的長官們。換句話說,他的長官為在CK 公司人際關係網路樹狀結構圖中所有他的祖先。)

同時,你也希望要參加活動的總人數越多越好(這代表著越多的報名費),究竟對每個場地要分別邀請哪些員工來參加才能使總人數最多呢?

Input Format

第一行有兩個數字:n 以及 m,n 代表員工的數量,m 代表與舉辦活動的場數。
第二行~第 n 行,共 n-1 行,每行有一個數字:ai,代表編號2~n 的員工的直屬長官編號,且永遠符合(ai<i)

Output Format

請輸出一個數字: k,代表最多能邀請到 k 人參加活動。

Sample Input 1

5 2
1
1
1
2

Sample Output 1

4

Sample Input 2

9 2
1
1
2
2
3
3
6
6

Sample Output 2

7

Hints

對於所有測試資料,1 <= k <= n <= 106。

Problem Source

原TIOJ1654 / 98建中校內資訊能力競賽(prob5)

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10