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.