Up and Down the Tree

题意翻译

你有一棵带有n个结点的树,根是结点1。有一个标记,最初在根结点处。你可以将标记移动到其他结点处。假设标记当前所在结点为v,你可以做出以下两种操作: 将标记移动到v子树的任一叶子处。 如果是结点v为叶子,则将标记向根移动不超过 k 次。换句话说,如果 h(v) 为结点 v 的深度 (根的深度为0),你可以将其移动到顶点 to ( to 为 v 祖先) 并且 h(v)−k≤h(to)。 根不是叶子(即使它的度数是 1)。计算最多能访问多少叶子。 输入格式: 第一行包含两个整数 n 和 k (1<k<n≤10^6) --- 树中的顶点数和向上移动的限制。 第二行包含 n-1个整数 第i个整数表示结点i+1的父亲 输入保证树合法,根为1。 输出格式: 输出一个整数,表示可以访问的最大叶子数。

题目描述

You are given a <a>tree</a> 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.

输入输出样例

输入样例 #1

7 1
1 1 3 3 4 4

输出样例 #1

4

输入样例 #2

8 2
1 1 2 3 4 5 5

输出样例 #2

2

说明

The graph from the first example: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1065F/4492bbb0d034205ea39166c1307fdf5f1ba770f6.png)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: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1065F/e11448008e64eca6a39a266818c29c10e5e679a8.png)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.