该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一棵 $n$ 个结点的有根树，其中结点 $1$ 为根，结点 $i$ ($2 ≤ i ≤ n$) 的父亲结点为 结点 $p_i$。 对于 $1 ≤ i ≤ n$，定义结点 $i$ 的深. 度. $d_i$ 为结点 $1$ 到结点 $i$ 的简单路径的边. 数. ，也就 是说，$d_1 = 0$，$d_i = d_{p_i} + 1$ ($2 ≤ i ≤ n$)。定义有根树的高. 度. $h$ 为所有结点的深. 度. 的. 最. 大. 值. ，即 $h = \max_{1 ≤ i ≤ n} d_i$。 给定高度的上界 $m$。在本题中，给. 定. 的. 有. 根. 树. 的. 高. 度. 不. 超. 过. $m$。 你需要给每个结点设置一个非. 负. 整. 数. 作为它的权. 值. 。对于 $1 ≤ i ≤ n$，若结点 $i$ 的权 值为 $a_i$，令 $S_i$ 表示结点 $i$ 的子. 树. 中结点权值构成的集合。对于每一种权值设置方案，定 义树的价. 值. 为 $\sum_{i=1}^{n} \mathrm{mex}(S_i)$，其中 $\mathrm{mex}(S)$ 表示不. 在. 集合 $S$ 中的最. 小. 非. 负. 整. 数.。

例如，在下图中，若设置 $a_1 = 3$，$a_2 = 2$，$a_3 = a_4 = 0$，$a_5 = 1$，则 $S_1 = \{0, 1, 2, 3\}$，$S_2 = \{0, 1, 2\}$，$S_3 = \{0\}$，$S_4 = \{0\}$，$S_5 = \{1\}$，树的价值为 $4 + 3 + 1 + 1 + 0 = 9$。

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

输入格式

从文件 tree.in 中读入数据。 本. 题. 包. 含. 多. 组. 测. 试. 数. 据。 输入的第一行包含一个正整数 $t$，表示测试数据组数。 接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含两个正整数 $n, m$，分别表示结点数量与高度的上界。
• 第二行包含 $n - 1$ 个正整数 $p_2, p_3, \ldots, p_n$，分别表示每个结点的父亲结点。

输出格式

输出到文件 tree.out 中。 对于每组测试数据，输出一行一个非负整数，表示树的价值的最大值。

样例 1 输入

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

样例 1 输出

9
13

样例 1 解释

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

• 对于第一组测试数据，可以设置 $a_1 = 3$，$a_2 = 2$，$a_3 = a_4 = 0$，$a_5 = 1$，则树的价值为 $4 + 3 + 1 + 1 + 0 = 9$。
• 对于第二组测试数据，可以设置 $a_1 = 4$，$a_2 = 3$，$a_4 = 2$，$a_3 = a_6 = 1$，$a_5 = a_7 = 0$，则树的价值为 $5 + 4 + 2 + 0 + 1 + 0 + 1 = 13$。

样例 2

见选手目录下的 tree/tree2.in 与 tree/tree2.ans。 该样例满足测试点 $3, 4$ 的约束条件。

样例 3

见选手目录下的 tree/tree3.in 与 tree/tree3.ans。 该样例满足测试点 $7, 8$ 的约束条件。

样例 4

见选手目录下的 tree/tree4.in 与 tree/tree4.ans。 该样例满足测试点 $13, 14$ 的约束条件。

样例 5

见选手目录下的 tree/tree5.in 与 tree/tree5.ans。 该样例满足测试点 $18, 19$ 的约束条件。

数据范围

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

• $1 ≤ t ≤ 5$；
• $2 ≤ n ≤ 8000$，$1 ≤ m ≤ \min(n-1, 800)$；
• 对于所有 $2 ≤ i ≤ n$，均有 $1 ≤ p_i ≤ i-1$；
• 给定的有根树的高度不超过 $m$。