TopCoder

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

69.2% (27/39)

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

Sample Input #1
5 2
1
1
1
2

Sample Input #2
9 2
1
1
2
2
3
3
6
6

Sample Output

Sample Output #1
4

Sample Output #2
7

Hints

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

Problem Source

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

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 262144
1 3000 65536 262144
2 3000 65536 262144
3 3000 65536 262144
4 3000 65536 262144
5 3000 65536 262144
6 3000 65536 262144
7 3000 65536 262144
8 3000 65536 262144
9 3000 65536 262144