CF1662G Gastronomic Event

SWERC 组织者想要举办一场美食活动。 活动地点是一栋有 $n$ 个房间的建筑，这些房间通过 $n-1$ 条走廊连接（每条走廊连接两个房间），保证任意两个房间之间都可以互相到达。 你需要在每个房间内安排一道典型的意大利菜品品鉴。你可以从 $n$ 道典型的意大利菜中选择，评分从 $1$ 到 $n$，分数越高表示菜品越好（$n$ 是最高分）。这 $n$ 道菜的评分互不相同。 你需要将这 $n$ 道菜分配到 $n$ 个房间，使得“令人愉悦的游览”数量最大。一次令人愉悦的游览是指一个非空的房间序列，满足： - 序列中每个房间与下一个房间之间都有走廊直接连接。 - 按照序列顺序，房间内菜品的评分严格递增。 如果你最优地分配这 $n$ 道菜，最多能有多少次令人愉悦的游览？

第一行包含一个整数 $n$（$2 \le n \le 1\,000\,000$），表示房间的数量。 第二行包含 $n-1$ 个整数 $p_2, p_3, \cdots, p_n$（$1 \leq p_i < i$）。每个 $p_i$ 表示房间 $i$ 与房间 $p_i$ 之间有一条走廊。保证建筑满足任意两个房间都可以互相到达的性质。

输出一个整数，表示最多能有多少次令人愉悦的游览。

在第一个样例中，最优的分配方式是将评分为 $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$。 由 ChatGPT 4.1 翻译