SWERC 组织者想要举办一场美食活动。
活动地点是一栋有 $$$n$$$ 个房间的建筑物,由 $$$n-1$$$ 走廊连接(每个走廊连接两个房间),因此可以从任何房间前往任何其他房间。
在每个房间里,您都必须品尝典型的意大利菜肴。您可以选择 $$$n$$$ 典型的意大利菜肴,评级从 $$$1$$$ 到 $$$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
5 1 2 2 2
输出 #1
13
输入 #2
10 1 2 3 4 3 2 7 8 7
输出 #2
47
注意
在第一个样本中,最好将评级为 $$$1$$$ 的菜肴放在 $$$1$$$ 房间,将评级为 $$$2$$$ 的菜肴放在 $$$3$$$ 房间,将评级为 $$$3$$$ 的菜肴放在 $$$2$$$ 房间,将评级为 $$$4$$$ 的菜肴放在 $$$5$$$ 房间,将评级为 $$$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$$$ 愉快的旅行。