Home => ProblemSet => [NOIP2025] 树的价值
2370: [NOIP2025] 树的价值
Time Limit: 2 Sec Memory Limit: 512 MB Submit: 0 Solved: 0[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]
Description
你需要求出，在所有权值设置方案中，树的价值的最大值。
Input
本题包含多组测试数据。
输入的第一行包含一个正整数 t，表示测试数据组数。
接下来依次输入每组测试数据，对于每组测试数据：
输入的第一行包含一个正整数 t，表示测试数据组数。
接下来依次输入每组测试数据，对于每组测试数据：
- 第一行包含两个正整数 n,m，分别表示结点数量与高度的上界。
- 第二行包含 n−1 个正整数 p2,p3,…,pn，分别表示每个结点的父亲结点。
Output
对于每组测试数据，输出一行一个非负整数，表示树的价值的最大值。
Sample Input Copy
2
5 2
1 1 2 2
7 2
1 1 2 2 2 3
Sample Output Copy
9
13
HINT
【样例 1 解释】
该样例共包含两组测试数据。对于第一组测试数据，可以设置 a1=3，a2=2，a3=a4=0，a5=1，则树的价值为 4+3+1+1+0=9。
对于第二组测试数据，可以设置 a1=4，a2=3，a4=2，a3=a6=1，a5=a7=0，则树的价值为 5+4+2+0+1+0+1=13。
其他测试数据：tree.zip