Reset K Edges

题意翻译

## 题目描述 给你一棵由 $n$ 个点组成的编号为 $1 \sim n$ 的以 $1$ 为根的有根树，你可以进行 $k$ 次如下操作： - 断开点 $u$ 与其父亲之间的边，并连接点 $1$ 与点 $u$。 定义树的高度为树上点的深度的最大值，点的深度为点到根的路径上经过的边的数量，问 $k$ 次操作后树的高度的最小值为多少。 ## 输入格式 **本题有多组数据。** 输入第一行一个整数 $T$ 表示数据组数。 对于每组数据第一行输入两个正整数 $n$ 和 $k$，表示树的大小和操作次数。 接下一行 $n-1$ 个正整数 $p_2,p_3,\cdots,p_n$，其中 $p_i$ 表示第 $i$ 个点的父亲。 ## 输出格式 对于每组数据输出一行一个整数表示答案。 ## 说明/提示 对于 $100\%$ 的数据： - $1 \le T \le 10^4$ - $2 \le n \le 2 \cdot 10^5,0 \le k \le n-1$ - $\forall i \in [2,n],1 \le p_i < i$ - 每组数据的 $n$ 的总和不超过 $2 \cdot 10^5$

题目描述

You are given a rooted tree, consisting of $ n $ vertices. The vertices are numbered from $ 1 $ to $ n $ , the root is the vertex $ 1 $ . You can perform the following operation at most $ k $ times: - choose an edge $ (v, u) $ of the tree such that $ v $ is a parent of $ u $ ; - remove the edge $ (v, u) $ ; - add an edge $ (1, u) $ (i. e. make $ u $ with its subtree a child of the root). The height of a tree is the maximum depth of its vertices, and the depth of a vertex is the number of edges on the path from the root to it. For example, the depth of vertex $ 1 $ is $ 0 $ , since it's the root, and the depth of all its children is $ 1 $ . What's the smallest height of the tree that can be achieved?

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. The first line of each testcase contains two integers $ n $ and $ k $ ( $ 2 \le n \le 2 \cdot 10^5 $ ; $ 0 \le k \le n - 1 $ ) — the number of vertices in the tree and the maximum number of operations you can perform. The second line contains $ n-1 $ integers $ p_2, p_3, \dots, p_n $ ( $ 1 \le p_i < i $ ) — the parent of the $ i $ -th vertex. Vertex $ 1 $ is the root. The sum of $ n $ over all testcases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式

For each testcase, print a single integer — the smallest height of the tree that can achieved by performing at most $ k $ operations.

输入输出样例

输入样例 #1

5
5 1
1 1 2 2
5 2
1 1 2 2
6 0
1 2 3 4 5
6 1
1 2 3 4 5
4 3
1 1 1

输出样例 #1

2
1
5
3
1

**题目大意**：

给定一棵由n个节点组成的以1为根的有根树，节点编号为1到n。你可以进行k次以下操作：

- 选择树中一条边(v, u)，其中v是u的父节点；
- 移除边(v, u)；
- 添加一条边(1, u)（即让u及其子树成为根的孩子）。

树的高度是树上节点的深度的最大值，一个节点的深度是从根到该节点的路径上经过的边的数量。问经过k次操作后，树的高度最小可以是多少。

**输入数据格式**：

输入的第一行包含一个整数T（1≤T≤10^4），表示数据组数。

每组数据的第一行输入两个正整数n和k（2≤n≤2×10^5，0≤k≤n-1），分别表示树的大小和最大操作次数。

接下来一行输入n-1个正整数p_2, p_3, …, p_n（1≤p_i
**输出数据格式**：

对于每组数据，输出一行一个整数，表示经过k次操作后树的最小高度。

**输入输出样例**：

**输入样例**：
```
5
5 1
1 1 2 2
5 2
1 1 2 2
6 0
1 2 3 4 5
6 1
1 2 3 4 5
4 3
1 1 1
```

**输出样例**：
```
2
1
5
3
1
```**题目大意**： 给定一棵由n个节点组成的以1为根的有根树，节点编号为1到n。你可以进行k次以下操作： - 选择树中一条边(v, u)，其中v是u的父节点； - 移除边(v, u)； - 添加一条边(1, u)（即让u及其子树成为根的孩子）。 树的高度是树上节点的深度的最大值，一个节点的深度是从根到该节点的路径上经过的边的数量。问经过k次操作后，树的高度最小可以是多少。 **输入数据格式**： 输入的第一行包含一个整数T（1≤T≤10^4），表示数据组数。 每组数据的第一行输入两个正整数n和k（2≤n≤2×10^5，0≤k≤n-1），分别表示树的大小和最大操作次数。 接下来一行输入n-1个正整数p_2, p_3, …, p_n（1≤p_i