Up and Down the Tree

题意翻译

你有一棵带有 $n$ 个结点的树,根是结点 $1$。有一个标记,最初在根结点处。你可以将标记移动到其他结点处。假设标记当前所在结点为 $v$,你可以做出以下两种操作: 1. 将标记移动到 $v$ 子树的任一叶子处。 2. 如果是结点 $v$ 为叶子,则将标记向根移动不超过 $k$ 次。换句话说,如果 $h_v$ 为结点 $v$ 的深度 (根的深度为 $0$),你可以将其移动到顶点 $to$($to$ 为 $v$ 祖先)并且 $h_v-k\le h_{to}$。 根不是叶子(即使它的度数是 $1$)。计算最多能访问多少叶子。 #### 输入格式: - 第一行包含两个整数 $n$ 和 $k(1\le k<n\le 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.