← 返回题目列表

Codeforces · 1856/E1

E1. PermuTree(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。两个版本之间的差异在于$$$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$$$。

第三次测试中的树:

第四次测试中的树: