CF1856E1 PermuTree (easy version)

这是该问题的简单版本。两个版本的区别在于 $n$ 的约束和时间限制。只有当你同时解决了两个版本的问题时，才能进行 hack。 给定一棵以 $1$ 号结点为根的 $n$ 个结点的树。 对于长度为 $n$ 的某个排列 $^\dagger$ $a$，定义 $f(a)$ 为满足 $a_u < a_{\operatorname{lca}(u, v)} < a_v$ 的结点对 $(u, v)$ 的数量。这里，$\operatorname{lca}(u,v)$ 表示结点 $u$ 和 $v$ 的最近公共祖先（lowest common ancestor）。 请你求出所有长度为 $n$ 的排列 $a$ 中，$f(a)$ 的最大可能值。 $^\dagger$ 长度为 $n$ 的排列是指由 $1$ 到 $n$ 的 $n$ 个不同整数组成的数组，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（$n=3$，但数组中有 $4$）。

第一行包含一个整数 $n$（$2 \le n \le 5000$）。 第二行包含 $n-1$ 个整数 $p_2,p_3,\ldots,p_n$（$1 \le p_i < i$），表示存在一条连接结点 $i$ 和 $p_i$ 的边。

输出 $f(a)$ 的最大值。

第一组测试中的树结构如下：  一种可能的最优排列 $a$ 为 $[2, 1, 4, 5, 3]$，此时有 $4$ 个满足条件的结点对： - $(2, 3)$，因为 $\operatorname{lca}(2, 3) = 1$ 且 $1 < 2 < 4$； - $(2, 4)$，因为 $\operatorname{lca}(2, 4) = 1$ 且 $1 < 2 < 5$； - $(2, 5)$，因为 $\operatorname{lca}(2, 5) = 1$ 且 $1 < 2 < 3$； - $(5, 4)$，因为 $\operatorname{lca}(5, 4) = 3$ 且 $3 < 4 < 5$。 第三组测试中的树结构如下：  第四组测试中的树结构如下：  由 ChatGPT 4.1 翻译