#10109. [NOIP2025] 树的价值

给定一棵 个结点的有根树，其中结点 1 为根，结点 () 的父亲结点为结点 。

对于 ，定义结点 的深度 为结点 1 到结点 的简单路径的边数，也就是说，， ()。定义有根树的高度 为所有结点的深度的最大值，即 。

给定高度的上界 。在本题中，给定的有根树的高度不超过 。

你需要给每个结点设置一个非负整数作为它的权值。对于 ，若结点 的权值为 ，令 表示结点 的子树中结点权值构成的集合。对于每一种权值设置方案，定义树的价值为 ，其中 表示不在集合 中的最小非负整数。例如，在下图中，若设置 ，，，，则 ，，，，，树的价值为 。

:::align{center} :::

你需要求出，在所有权值设置方案中，树的价值的最大值。

本题包含多组测试数据。

输入的第一行包含一个正整数 ，表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含两个正整数 ，分别表示结点数量与高度的上界。
• 第二行包含 个正整数 ，分别表示每个结点的父亲结点。

对于每组测试数据，输出一行一个非负整数，表示树的价值的最大值。

输入 #1

2
5 2
1 1 2 2
7 2
1 1 2 2 2 3

输出 #1

9
13

【样例 1 解释】

该样例共包含两组测试数据。

对于第一组测试数据，可以设置 ，，，，则树的价值为 。

对于第二组测试数据，可以设置 ，，，，，则树的价值为 。

【样例 2】

见选手目录下的 tree/tree2.in 与 tree/tree2.ans。

该样例满足测试点 的约束条件。

【样例 3】

见选手目录下的 tree/tree3.in 与 tree/tree3.ans。

该样例满足测试点 的约束条件。

【样例 4】

见选手目录下的 tree/tree4.in 与 tree/tree4.ans。

该样例满足测试点 的约束条件。

【样例 5】

见选手目录下的 tree/tree5.in 与 tree/tree5.ans。

该样例满足测试点 的约束条件。

【数据范围】

对于所有测试数据，均有：

• ；
• ，；
• 对于所有 ，均有 ；
• 给定的有根树的高度不超过 。