CF1662G.Gastronomic Event

SWERC organizers want to hold a gastronomic event.

The location of the event is a building with $n$ rooms connected by $n-1$ corridors (each corridor connects two rooms) so that it is possible to go from any room to any other room.

In each room you have to set up the tasting of a typical Italian dish. You can choose from $n$ typical Italian dishes rated from $1$ to $n$ depending on how good they are ($n$ is the best possible rating). The $n$ dishes have distinct ratings.

You want to assign the $n$ dishes to the $n$ rooms so that the number of pleasing tours is maximal. A pleasing tour is a nonempty sequence of rooms so that:

• Each room in the sequence is connected to the next one in the sequence by a corridor.
• The ratings of the dishes in the rooms (in the order given by the sequence) are increasing.

If you assign the $n$ dishes optimally, what is the maximum number of pleasing tours?

SWERC 组委会希望举办一场美食活动。

活动地点是一座拥有 $n$ 个房间的建筑，这些房间由 $n-1$ 条走廊连接（每条走廊连接两个房间），且任意两个房间之间均可相互到达。

每个房间需布置一道典型的意大利菜肴供品鉴。你可以从 $n$ 道典型意大利菜肴中选择，这些菜肴按品质被评分为 $1$ 到 $n$（$n$ 为最高评分）。这 $n$ 道菜肴的评分互不相同。

你需要将这 $n$ 道菜肴分配到 $n$ 个房间中，使得“令人愉悦的游览路线”（pleasing tour）的数量最大化。所谓“令人愉悦的游览路线”，是指一个非空的房间序列，满足：

• 序列中每个房间均通过一条走廊与序列中的下一个房间相连；
• 按该序列顺序，各房间所布置菜肴的评分严格递增。

若以最优方式分配这 $n$ 道菜肴，最多能有多少条“令人愉悦的游览路线”？

The first line contains an integer $n$ ($2\le n\le 1\,000\,000$) — the number of rooms.

The second line contains $n-1$ integers $p_2, p_3, \cdots , p_n$ ($1 \leq p_i \lt i$). Each $p_i$ indicates that there is a corridor between room $i$ and room $p_i$. It is guaranteed that the building has the property that it is possible to go from any room to any other room.

第一行包含一个整数 $n$（$2\le n\le 1\,000\,000$）—— 房间的数量。

第二行包含 $n-1$ 个整数 $p_2, p_3, \cdots , p_n$（$1 \leq p_i \lt i$）。每个 $p_i$ 表示房间 $i$ 与房间 $p_i$ 之间存在一条走廊。保证该建筑具有如下性质：任意两个房间之间均可相互到达。

Print the maximum number of pleasing tours.

输出令人愉悦的游览路线的最大数量。

In the first sample, it is optimal to place the dish with rating $1$ in room $1$, the dish with rating $2$ in room $3$, the dish with rating $3$ in room $2$, the dish with rating $4$ in room $5$ and the dish with rating $5$ in room $4$.

All the $13$ possible pleasing tours are: $(1)$, $(2)$, $(3)$, $(4)$, $(5)$, $(1,2)$, $(3,2)$, $(2,4)$, $(2,5)$, $(1,2,4)$, $(1,2,5)$, $(3,2,4)$, $(3,2,5)$.

There are also other ways to assign the dishes to the rooms so that there are $13$ pleasing tours.

在第一个样例中，最优方案是将评分为 $1$ 的菜肴放在房间 $1$，评分为 $2$ 的菜肴放在房间 $3$，评分为 $3$ 的菜肴放在房间 $2$，评分为 $4$ 的菜肴放在房间 $5$，评分为 $5$ 的菜肴放在房间 $4$。

所有 $13$ 种可能的愉悦游线为：$(1)$、$(2)$、$(3)$、$(4)$、$(5)$、$(1,2)$、$(3,2)$、$(2,4)$、$(2,5)$、$(1,2,4)$、$(1,2,5)$、$(3,2,4)$、$(3,2,5)$。

此外，还存在其他将菜肴分配至房间的方式，也能得到 $13$ 条愉悦游线。