← 返回题目列表

AtCoder · icpc2014spring_a

A. Foxpower 的广度优先搜索

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

问题陈述

福克斯夏尔骑着自行车去了JAG王国,但是她忘记了停放自行车的地方。 因此,她需要在回家之前从自行车停放区寻找它。

停车区形成为具有 $n$ 个顶点的未加权有根树 $T$,编号为 $1$ 到 $n$。 每个顶点都有一个可停放一辆或多辆自行车的空间。 Ciel认为她把自行车停在顶点$1$附近,所以她决定从那里开始通过广度优先搜索来搜索。 也就是说,她按照距顶点 $1$ 的距离递增的顺序在顶点上进行搜索。 如果多个顶点具有相同的距离,她会按照搜索父级的顺序优先搜索这些顶点。 如果多个顶点具有相同的父节点,则她首先在数量最少的顶点进行搜索。

与计算机不同,她无法通过随机访问到达下一个顶点。 因此,如果她在顶点$i$之后到达顶点$j$,则她需要走过顶点$i$和$j$之间的距离。 Fox Power 的 BFS 可能需要很长时间,所以她要求你计算从顶点 $1$ 开始的最坏情况下的总移动距离。


输入

输入格式如下。

$n$
$p_2$ $p_3$ $p_4$ $\cdots$ $p_n$

第一行包含一个整数 $n$ ($1 \le n \le 10^5$),它是未加权有根树 $T$ 上的顶点数。 第二行包含 $n-1$ 个整数 $p_i$ ($1 \le p_i < i$),它们是顶点 $i$ 的父节点。 顶点$1$是根节点,因此$p_1$不存在。

输出

在一行中打印最坏情况下的总移动距离。


示例输入 1

4
1 1 2

样本输入 1 的输出

6

示例输入 2

4
1 1 3

样本输入 2 的输出

4

示例输入 3

11
1 1 3 3 2 4 1 3 2 9

样本输入 3 的输出

25