这是问题的简单版本。两个版本之间的差异在于$$$n$$$ 的约束和时间限制。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
给你一棵树,其中有 $$$n$$$ 个顶点,以顶点 $$$1$$$ 为根。
对于长度为 $$$n$$$ 的某些排列$$$^\dagger$$$ $$$a$$$,令 $$$f(a)$$$ 为顶点对 $$$(u, v)$$$ 的数量,使得 $$$a_u < a_{\operatorname{lca}(u, v)} < a_v$$$。这里,$$$\operatorname{lca}(u,v)$$$表示顶点$$$u$$$和$$$v$$$的最低公共祖先。
找出 $$$f(a)$$$ 在长度 $$$n$$$ 的所有排列 $$$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)$$$的最大值。
示例
输入 #1
5 1 1 3 3
输出 #1
4
输入 #2
2 1
输出 #2
0
输入 #3
6 1 2 2 1 5
输出 #3
7
输入#4
4 1 1 1
输出#4
2
注意
第一次测试中的树:
一种可能的最佳排列 $$$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$$$。
第三次测试中的树:
第四次测试中的树: