389. 【25NOIP提高组】树的价值(tree) 中等

给定一棵 $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_{i-1}^{n}d_i$。 给定高度的上界 $m$。在本题中，给定的有根树的高度不超过$m$。 你需要给每个结点设置一个非负整数作为它的权值。对于 $1 ≤ i ≤ n$，若结点 $i$ 的权值为 $a_i$，令 $S_i$ 表示结点 $i$ 的子树中结点权值构成的集合。对于每一种权值设置方案，定义树的价值为$\sum^{n}_{i=1}mex(S_i)$，其中 $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$。 你需要求出，在所有权值设置方案中，树的价值的最大值。