A6490 | $[NOIP2025] 树的价值$

来源NOIP提高组 / 2025

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

NOIP2025 T3 给定一棵 $n$ 个结点的有根树，其中结点 1 为根，结点 $i$ ($2 \le i \le n$) 的父亲结点为结点 $p_i$。 对于 $1 \le i \le n$，定义结点 $i$ 的深度 $d_i$ 为结点 1 到结点 $i$ 的简单路径的边数，也就是说，$d_1 = 0$，$d_i = d_{p_i} + 1$ ($2 \le i \le n$)。定义有根树的高度 $h$ 为所有结点的深度的最大值，即 $h = \max_{i=1}^{n} d_i$。 给定高度的上限 $m$。在本题中，给定的有根树的高度不超过 $m$。 你需要给每个结点设置一个非负整数作为它的权值。对于 $1 \le i \le n$，若结点 $i$ 的权值为 $a_i$，令 $S_i$ 表示结点 $i$ 的子树中结点权值构成的集合。对于每一种权值设置方案，定义树的价值为 $\sum_{i=1}^{n} \operatorname{mex}(S_i)$，其中 $\operatorname{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$。 【等待好心人上传图片】 你需要求出，在所有权值设置方案中，树的价值的最大值。

本题包含多组测试数据。 输入的第一行包含一个正整数 $k$，表示测试数据组数。 接下来依次输入每组测试数据。对于每组测试数据： - 第一行包含两个正整数 $n, m$，分别表示结点数量与高度的上限； - 第二行包含 $n-1$ 个正整数 $p_2, p_3, \ldots, p_n$，分别表示每个结点的父亲结点。

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

输入 #1

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

输出 #1

9
13

C++ 编辑器

输入

输出