题目完整中文翻译 + 规范排版

题目

Maple and Tree Beauty (Easy Version) 枫树与树之美（简单版）

---

题目说明

本题为简单版本。两个版本的区别在于：本版本中 $t$ 与 $n$ 的限制更小。 仅当你通过本题所有版本时，才可进行 hack 操作。

给定一棵以 $1$ 为根、包含 $n$ 个顶点的有根树，顶点编号为 $1 \sim n$。 每个顶点的权值为 $0$ 或 $1$。 已知整棵树中恰好有 $k$ 个点为 $0$，$n-k$ 个点为 $1$，但具体每个点的取值未知。

对每个顶点，定义该点的名称： 从根走到该点，沿途所有点的权值依次拼接形成的二进制字符串。 形式化定义：

• $\mathit{name}_1 = \mathit{label}_1$
• 对 $2\le u \le n$，设 $p_u$ 为 $u$ 的父节点，则：

$$\mathit{name}_u = \mathit{name}_{p_u} + \mathit{label}_u $$

其中 $+$ 代表字符串拼接。

定义树的美观度： 所有叶子节点的名称串的**最长公共子序列（LCS）**长度。

你的任务： 在满足恰好 $k$ 个 $0$、$n-k$ 个 $1$ 的所有赋值方案中，求出最大可能的美观度。

---

名词释义

1. 子序列 若序列 $a$ 可以通过删除序列 $b$ 中任意若干个（可为 $0$ 个）字符得到，则称 $a$ 是 $b$ 的子序列。 若干字符串 $s_1,s_2,\dots,s_m$ 的最长公共子序列，是同时属于所有串的最长子序列。

2. 叶子节点 没有子节点的顶点。

---

输入格式

多组测试数据。 第一行输入测试组数 $t$（$1\le t \le 50$）。

每组数据：

1. 第一行两个整数 $n,k$（$2\le n \le 1000,\ 0\le k \le n$），分别表示顶点数量、需要分配的 $0$ 的个数。
2. 第二行输入 $n-1$ 个整数 $p_2,p_3,\dots,p_n$（$1\le p_i \le i-1$），依次为编号 $2\sim n$ 每个点的父节点。

保证所有测试数据的 $n$ 之和无特殊限制。

---

输出格式

对每组测试数据，输出一个整数：在合法赋值下，树能达到的最大美观度。

---

样例输入 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

样例输出 1

3
2
5
1
2

样例输入 2

5
2 0
1
2 1
1
3 0
1 1
3 1
1 2
3 1
1 1

样例输出 2

2
2
2
3
2

---

样例注释

1. 第一组测试数据 $n=7,k=3$，最优赋值：$[0,0,0,1,1,1,1]$ 所有叶子名称的最长公共子序列为 $\texttt{001}$，长度为 $3$。

2. 第二组测试数据 $n=7,k=2$，最优赋值：$[1,0,0,1,1,1,1]$ 最长公共子序列为 $\texttt{11}$，长度为 $2$。