5981 - NOIP 2025 提高: 第三题树的价值 / tree

通过次数

提交次数

旧版界面

Time Limit : 2 秒

Memory Limit : 512 MB

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

Input

本题包含多组测试数据。

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

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

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

Output

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

Examples

Input

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

Output

9
13

Input

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

Output

Input

5
13 12
1 1 2 3 5 5 7 7 9 8 10 10
13 12
1 2 2 4 3 3 4 4 4 4 4 3
13 12
1 1 2 2 3 3 4 2 9 5 1 12
13 12
1 2 2 1 4 6 6 4 7 10 9 11
13 12
1 1 2 4 5 6 5 7 9 8 10 11

Output

Hint

【样例 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】

输入

5
13 12
1 2 1 4 3 6 7 6 9 9 10 12
13 12
1 2 2 2 2 2 6 5 7 4 5 4
13 12
1 1 2 2 3 3 4 4 1 10 11 2
13 12
1 1 3 4 4 6 7 6 7 9 11 10
13 12
1 1 3 3 4 5 5 7 9 10 11 10
输出
52
29
27
49
50

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

该样例满足测试点 $13,14$ 的约束条件。

【样例 5】

输入：

5
18 17
1 2 3 2 5 4 7 8 9 10 11 12 12 14 13 14 16
18 17
1 2 2 4 4 3 3 3 3 10 5 7 7 9 8 10 5
18 17
1 1 2 2 3 3 4 8 1 10 11 12 4 14 1 16 17
18 17
1 1 3 3 5 5 7 7 2 10 11 10 13 12 15 16 16
18 17
1 1 2 2 3 6 5 7 8 9 11 10 12 14 14 16 16
输出
125
51
43
65
88

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

该样例满足测试点 $18,19$ 的约束条件。