[Solution] Reset K Edges solution codeforces

Reset K Edges solution codeforces – You are given a rooted tree, consisting of 𝑛n vertices. The vertices are numbered from 11 to 𝑛n, the root is the vertex 11.

Table of Contents

[Solution] Reset K Edges solution codeforces

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,𝑢)(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 11 is 00, since it’s the root, and the depth of all its children is 11.

What’s the smallest height of the tree that can be achieved?

Input

The first line contains a single integer 𝑡t (1𝑡1041≤t≤104) — the number of testcases.

The first line of each testcase contains two integers 𝑛n and 𝑘k (2𝑛21052≤n≤2⋅1050𝑘𝑛10≤k≤n−1) — the number of vertices in the tree and the maximum number of operations you can perform.

The second line contains 𝑛1n−1 integers 𝑝2,𝑝3,,𝑝𝑛p2,p3,…,pn (1𝑝𝑖<𝑖1≤pi<i) — the parent of the 𝑖i-th vertex. Vertex 11 is the root.

The sum of 𝑛n over all testcases doesn’t exceed 21052⋅105.

[Solution] Reset K Edges solution codeforces

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

Example
input

Copy
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

[Solution] Reset K Edges solution codeforces

Copy
2
1
5
3
1

 

For Solution

“Click Here”

Leave a Comment