19108번 - Monkeys 다국어

Given is a tree with $N$ vertices. There are $K$ monkeys in the tree. The monkeys want to occupy some vertices of the tree so that each monkey is in some vertex and each vertex contains at most one monkey. Then, they want to remove some edges of the tree so that each monkey can still move to at least one other monkey using only the remaining edges.

Your task is to find the minimum possible number of remaining edges.

The first line of input contains an integer $T$, the number of test cases ($1 \le T \le 100$).

Each test case begins with a line containing two integers $N$ and $K$ ($2 \le K \le N \le 10^5$). The next line contains $N - 1$ space-separated integers $a_1, a_2, \ldots, a_{N - 1}$ ($1 \le a_i \le i$). They mean that, for each $i$, there is an edge between vertex $a_i$ and vertex $i + 1$.

For each test case, print the minimum possible number of remaining edges.