CF1065F Up and Down the Tree

You are given a tree with $ n $ vertices; its root is vertex $ 1 $ . Also there is a token, initially placed in the root. You can move the token to other vertices. Let's assume current vertex of token is $ v $ , then you make any of the following two possible moves: - move down to any leaf in subtree of $ v $ ; - if vertex $ v $ is a leaf, then move up to the parent no more than $ k $ times. In other words, if $ h(v) $ is the depth of vertex $ v $ (the depth of the root is $ 0 $ ), then you can move to vertex $ to $ such that $ to $ is an ancestor of $ v $ and $ h(v) - k \le h(to) $ . Consider that root is not a leaf (even if its degree is $ 1 $ ). Calculate the maximum number of different leaves you can visit during one sequence of moves.

The first line contains two integers $ n $ and $ k $ ( $ 1 \le k < n \le 10^6 $ ) — the number of vertices in the tree and the restriction on moving up, respectively. The second line contains $ n - 1 $ integers $ p_2, p_3, \dots, p_n $ , where $ p_i $ is the parent of vertex $ i $ . It is guaranteed that the input represents a valid tree, rooted at $ 1 $ .

Print one integer — the maximum possible number of different leaves you can visit.

The graph from the first example: One of the optimal ways is the next one: $ 1 \rightarrow 2 \rightarrow 1 \rightarrow 5 \rightarrow 3 \rightarrow 7 \rightarrow 4 \rightarrow 6 $ . The graph from the second example: One of the optimal ways is the next one: $ 1 \rightarrow 7 \rightarrow 5 \rightarrow 8 $ . Note that there is no way to move from $ 6 $ to $ 7 $ or $ 8 $ and vice versa.