Maple and Tree Beauty (Hard Version) 枫树与树之美（困难版）

---

题目描述

本题为困难版本。两个版本的区别在于：本版本对 $t$ 和 $n$ 的数据限制更大。 只有通过本题所有版本，才可以进行 hack 操作。

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

对每个顶点定义节点名： 将从根到该顶点路径上所有点的标记依次拼接，形成二进制字符串。 形式化定义：

$$\begin{cases} \mathit{name}_1 = \mathit{label}_1 \\ \mathit{name}_u = \mathit{name}_{p_u} + \mathit{label}_u \quad (2\le u \le n) \end{cases} $$

其中 $p_u$ 表示点 $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 10^4$）。

每组测试数据：

1. 第一行两个整数 $n,k$（$2\le n \le 2\cdot 10^5,\ 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$ 每个顶点的父节点。

数据保证：所有测试数据的 $\boldsymbol{n}$ 总和不超过 $2\cdot 10^5$。

---

输出格式

对于每组测试数据，输出一个整数，表示合法标记方案下树的最大美观度。

---

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

---

难易版区别

• 简单版：$n \le 1000$，允许 $O(n^2)$ 背包做法；
• 困难版：$\sum n \le 2\cdot 10^5$，必须使用 bitset 优化背包 / 贪心结论优化，严格限制线性/线性对数复杂度。