CK 公司中共有 n 個員工,其中除了編號1 的餅乾之外,每個人都恰有一個直屬長官。即 CK 公司中的人際關係網路可視為一個樹狀結構。
為了增進 CK 公司中員工的感情與強化生活資訊的交流,你決定主辦一系列共 m 場的大型活動。
現在的問題是要邀請哪些員工來參加。
為了避免某些尷尬狀況的發生(例如在活動中催收作業或舉行小考等),你不希望有員工跟他的某個長官(註)參加了在同一場活動,而當然每個員工只能參加一場活動。
(註:一個員工的長官不只有他的直屬長官,也包括他的直屬長官的長官們。換句話說,他的長官為在CK 公司人際關係網路樹狀結構圖中所有他的祖先。)
同時,你也希望要參加活動的總人數越多越好(這代表著越多的報名費),究竟對每個場地要分別邀請哪些員工來參加才能使總人數最多呢?
第一行有兩個數字:n 以及 m,n 代表員工的數量,m 代表與舉辦活動的場數。
第二行~第 n 行,共 n-1 行,每行有一個數字:ai,代表編號2~n 的員工的直屬長官編號,且永遠符合(ai<i)
請輸出一個數字: k,代表最多能邀請到 k 人參加活動。
對於所有測試資料,1 <= k <= n <= 106。
原TIOJ1654 / 98建中校內資訊能力競賽(prob5)
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 |