Levels of a tree

★★★★★

2.4

7 votes

Algorithms, Graphs

Details

Submissions

Discussion

Editorial

Problem

You are given a tree that consists of $n$ vertex. In this tree, vertex 1 is the root vertex. Here, $level_i$ is defined as a set of vertex where the distance of the vertexes from the root vertex is equal to $i$ .

You are required to remove at most $k$ levels of the tree in such a manner that after removing the vertexes, the maximum size of the recently-created components is minimum.

Input format

First line: Two integers n, k denoting the number of nodes in the tree and maximum number of removed levels ( $1 \le k \le n \le 10^5$ )
Next line: $n-1$ space-separated integers where the $i^{th}$ integers is $par_i$ and it denotes the parent of vertex $i$ ( $1 \le par_i < i$ )

Output format

Print the required number.

Sample Input

13 1
1 2 3 4 5 1 7 8 9 1 10 1

Sample Output

Time Limit: 5

Memory Limit: 256

Source Limit:

Explanation

In this test if we remove level 1, it creates componenets with sizes {1, 1, 3, 4}. but if we remove another levels it creates components with a size of bigger than 4. so the answer is 4.

Contributers:

Amirreza Poorakhavan