这是问题的简单版本。版本之间的区别在于,在该版本中,$$$t$$$ 和$$$n$$$ 的约束较小。只有解决了该问题的所有版本,您才能破解。
Maple 被赋予一棵由 $$$n$$$ 顶点组成的有根树,编号从 $$$1$$$ 到 $$$n$$$,其中根的索引为 $$$1$$$。树的每个顶点都标记为零或一。不幸的是,Maple 忘记了顶点是如何标记的,只记得确切存在 $$$k$$$ 零和 $$$n - k$$$ 零。
对于每个顶点,我们定义 姓名 顶点的 作为从根到顶点的顶点标签连接而成的二进制字符串。更正式地说,$$$\text{name}_1 = \text{label}_1$$$ 和 $$$\text{name}_u = \text{name}_{p_u} + \text{label}_u$$$ 对于所有 $$$2\le u\le n$$$,其中 $$$p_u$$$ 是顶点 $$$u$$$ 的父节点,$$$+$$$ 表示字符串连接。
的 美女 等于所有树的名字的最长公共子序列$$$^{\text{*}}$$$的长度 叶子$$$^{\text{†}}$$$。您的任务是确定树的所有标签中的最大美度,其中恰好有 $$$k$$$ 个零和 $$$n - k$$$ 个。
$$$^{\text{*}}$$$ 序列 $$$a$$$ 是序列 $$$b$$$ 的子序列,如果 $$$a$$$ 可以通过从任意位置删除几个(可能是零个或全部)元素从 $$$b$$$ 获得。 字符串 $$$s_1, s_2, \ldots s_m$$$ 的最长公共子序列是所有 $$$s_1, s_2, \ldots, s_m$$$ 的子序列的最长字符串。
$$$^{\text{†}}$$$叶子是没有子节点的任何顶点。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 50$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq n \leq 1000$$$, $$$0 \leq k \leq n$$$) - 分别是顶点数和用零标记的顶点数。
第二行包含 $$$n - 1$$$ 整数 $$$p_2, p_3, \ldots, p_{n}$$$ ($$$1 \leq p_i \le i - 1$$$) — 顶点 $$$i$$$ 的父节点。
请注意,有 无限制 所有测试用例的 $$$n$$$ 总和。
输出
对于每个测试用例,输出一个整数,表示树的所有标签中最大的美感,其中恰好有 $$$k$$$ 个零和 $$$n - k$$$ 个。
示例
输入复制
57 31 1 2 2 3 37 21 1 2 3 1 15 01 2 3 45 21 1 1 15 41 1 1 1
输出复制
3 2 5 1 2
输入复制
52 012 113 01 13 11 23 11 1
输出复制
2 2 2 3 2
注意