310592: CF1856E1. PermuTree (easy version)

E1. PermuTree (easy version)time limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

This is the easy version of the problem. The differences between the two versions are the constraint on $n$ and the time limit. You can make hacks only if both versions of the problem are solved.

You are given a tree with $n$ vertices rooted at vertex $1$.

For some permutation$^\dagger$ $a$ of length $n$, let $f(a)$ be the number of pairs of vertices $(u, v)$ such that $a_u < a_{\operatorname{lca}(u, v)} < a_v$. Here, $\operatorname{lca}(u,v)$ denotes the lowest common ancestor of vertices $u$ and $v$.

Find the maximum possible value of $f(a)$ over all permutations $a$ of length $n$.

$^\dagger$ A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Input

The first line contains a single integer $n$ ($2 \le n \le 5000$).

The second line contains $n - 1$ integers $p_2,p_3,\ldots,p_n$ ($1 \le p_i < i$) indicating that there is an edge between vertices $i$ and $p_i$.

Output

Output the maximum value of $f(a)$.

ExamplesInput

5
1 1 3 3

Output

4

Input

2
1

Output

0

Input

6
1 2 2 1 5

Output

7

Input

4
1 1 1

Output

2

Note

The tree in the first test:

One possible optimal permutation $a$ is $[2, 1, 4, 5, 3]$ with $4$ suitable pairs of vertices:

• $(2, 3)$, since $\operatorname{lca}(2, 3) = 1$ and $1 < 2 < 4$,
• $(2, 4)$, since $\operatorname{lca}(2, 4) = 1$ and $1 < 2 < 5$,
• $(2, 5)$, since $\operatorname{lca}(2, 5) = 1$ and $1 < 2 < 3$,
• $(5, 4)$, since $\operatorname{lca}(5, 4) = 3$ and $3 < 4 < 5$.

The tree in the third test:

The tree in the fourth test:

题目大意：

这是一个关于树的问题的简单版本。两个版本的区别在于对n的限制和时限。只有当问题的两个版本都解决时，你才能进行黑客攻击。

给你一个有n个顶点的树，根顶点为1。

对于长度为n的某个排列a，定义f(a)为满足a_u < a_{lca(u, v)} < a_v的顶点对(u, v)的数量。这里，lca(u,v)表示顶点u和v的最低共同祖先。

求所有长度为n的排列a中f(a)的最大可能值。

输入输出数据格式：

输入：

第一行包含一个整数n（2≤n≤5000）。

第二行包含n-1个整数p_2, p_3, …, p_n（1≤p_i < i），表示顶点i和p_i之间有一条边。

输出：

输出f(a)的最大值。

示例：

输入：

5

1 1 3 3

输出：

4

输入：

2

1

输出：

0

输入：

6

1 2 2 1 5

输出：

7

输入：

4

1 1 1

输出：

2题目大意： 这是一个关于树的问题的简单版本。两个版本的区别在于对n的限制和时限。只有当问题的两个版本都解决时，你才能进行黑客攻击。 给你一个有n个顶点的树，根顶点为1。 对于长度为n的某个排列a，定义f(a)为满足a_u < a_{lca(u, v)} < a_v的顶点对(u, v)的数量。这里，lca(u,v)表示顶点u和v的最低共同祖先。 求所有长度为n的排列a中f(a)的最大可能值。 输入输出数据格式： 输入： 第一行包含一个整数n（2≤n≤5000）。 第二行包含n-1个整数p_2, p_3, …, p_n（1≤p_i < i），表示顶点i和p_i之间有一条边。 输出： 输出f(a)的最大值。 示例： 输入： 5 1 1 3 3 输出： 4 输入： 2 1 输出： 0 输入： 6 1 2 2 1 5 输出： 7 输入： 4 1 1 1 输出： 2