309812: CF1739D. Reset K Edges

Memory Limit:256 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

## 题目描述 给你一棵由 $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$

Output

**题目大意**:

给定一棵由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

加入题单

上一题 下一题 算法标签: