← 返回题目列表

Codeforces · 2138/C2

C2. 枫树美人(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。版本之间的区别在于,在这个版本中,$$$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$$$ 的父节点,$$$+$$$ 表示字符串连接。

的 树的 美女 二进制字符串 $$$z$$$ 的 等于所有树的名字的最长公共子序列$$$^{\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 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq n \leq 2\cdot 10 ^ 5$$$, $$$0 \leq k \leq n$$$) - 分别是顶点数和用零标记的顶点数。

第二行包含 $$$n - 1$$$ 整数 $$$p_2, p_3, \ldots, p_{n}$$$ ($$$1 \leq p_i \le i - 1$$$) — 顶点 $$$i$$$ 的父节点。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数,表示树的所有标签中最大的美感,其中恰好有 $$$k$$$ 零和 $$$n - k$$$ 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

输出
复制

3
2
5
1
2

输入
复制

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

输出
复制

2
2
2
3
2

注意

在第一个测试用例中,当顶点标记为$$$[0, 0, 0, 1, 1, 1, 1]$$$时,最大美度为$$$3$$$,最长公共子序列为 001.
在第二个测试用例中,当顶点标记为$$$[1, 0, 0, 1, 1, 1, 1]$$$时,最大美度为$$$2$$$,最长公共子序列为 11.