# [E2. Maple and Tree Beauty (Hard Version)](https://codeforces.com/problemset/problem/2139/E2)
## Problem Statement
Maple is given a rooted tree consisting of $n$ vertices, numbered from $1$ to $n$. The root of the tree is vertex $1$. Each vertex of the tree is labeled with either a $0$ or a $1$. Unfortunately, Maple has forgotten the specific labels of the vertices and only remembers that there are exactly $k$ vertices labeled with $0$ and $n-k$ vertices labeled with $1$.
For each vertex $u$, its *name* is defined as the binary string formed by concatenating the labels of the vertices along the unique path from the root (vertex $1$) to vertex $u$. More formally:
- $name_1 = label_1$
- $name_u = name_{p_u} + label_u$ for all $2
eq u
eq n$, where $p_u$ is the parent of vertex $u$, and $+$ represents string concatenation.
The *beauty* of the tree is defined as the length of the longest common subsequence (LCS) of the names of all the leaves. A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by deleting zero or more elements from arbitrary positions. The longest common subsequence of strings $s_1, s_2, \dots, s_m$ is the longest string that is a subsequence of all of $s_1, s_2, \dots, s_m$.
A vertex is considered a *leaf* if it has no children. Your task is to determine the maximum possible beauty among all valid labelings of the tree that use exactly $k$ zeros and $n-k$ ones.
## Input Format
The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
For each test case:
- The first line contains two integers $n$ and $k$ ($2 \le n \le 2 \cdot 10^5$, $0 \le k \le n$) — the number of vertices in the tree and the number of vertices labeled with $0$, respectively.
- The second line contains $n-1$ integers $p_2, p_3, \dots, p_n$ ($1 \le p_i \le i-1$) — $p_i$ is the parent of vertex $i$. It is guaranteed that $p_i < i$ and $p_i$ is the parent of $i$, forming a valid tree rooted at $1$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
## Output Format
For each test case, output a single integer representing the maximum beauty.
## Sample Test Cases
### Sample Input 1
```
5
7 3
1 1 2 2 3 3
7 2
1 1 2 3 1 1
5 0
1 2 3 4
5 2
1 1 1 1
5 4
1 1 1 1
```
### Sample Output 1
```
3
2
5
1
2
```
### Sample Input 2
```
5
2 0
1
2 1
1
3 0
1 1
3 1
1 2
3 1
1 1
```
### Sample Output 2
```
2
2
2
3
2
```
## Constraints
- $1 \le t \le 10^4$
- $2 \le n \le 2 \cdot 10^5$
- $0 \le k \le n$
- $1 \le p_i \le i-1$ for $2 \le i \le n$
- The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
- Time limit: 6 seconds
- Memory limit: 1024 MB
## Explanation
For the first test case in Sample Input 1:
$n = 7$, $k = 3$. The parents are $p_2=1, p_3=1, p_4=2, p_5=2, p_6=3, p_7=3$.
The leaves are vertices $4, 5, 6, 7$.
One possible labeling that achieves a beauty of $3$ is $[label_1, label_2, label_3, label_4, label_5, label_6, label_7] = [0, 0, 0, 1, 1, 1, 1]$.
- $name_4 = label_1 + label_2 + label_4 = \text{`001`}$
- $name_5 = label_1 + label_2 + label_5 = \text{`001`}$
- $name_6 = label_1 + label_3 + label_6 = \text{`001`}$
- $name_7 = label_1 + label_3 + label_7 = \text{`001`}$
The LCS of `001`, `001`, `001`, `001` is `001`, which has a length of $3$. It can be proven that $3$ is the maximum possible beauty for this configuration.
For the second test case in Sample Input 1:
$n = 7$, $k = 2$. The parents are $p_2=1, p_3=1, p_4=2, p_5=3, p_6=1, p_7=1$.
The leaves are vertices $4, 5, 6, 7$.
One possible labeling that achieves a beauty of $2$ is $[label_1, label_2, label_3, label_4, label_5, label_6, label_7] = [1, 0, 0, 1, 1, 1, 1]$.
- $name_4 = label_1 + label_2 + label_4 = \text{`101`}$
- $name_5 = label_1 + label_3 + label_5 = \text{`101`}$
- $name_6 = label_1 + label_6 = \text{`11`}$
- $name_7 = label_1 + label_7 = \text{`11`}$
The LCS of `101`, `101`, `11`, `11` is `11`, which has a length of $2$. It can be proven that $2$ is the maximum possible beauty for this configuration.
Loading problem statement...