AT848 BFS真菜.

问题描述.

Fox Ciel骑自行车去JAG王国,然而她忘记自行车停在哪里.在回家前她需要在停车场找到自己的自行车.

停车场可以看做1个无权带根树(边权值为1.),共有n个节点,编号1~n.每个点上都可以停放很多自行车.

Ciel认为她的自行车在1号点附近,所以她决定使用BFS寻找.

具体的,BFS根据所有点到1号点的距离从近到远搜索节点.

如果有多个点距离相同,BFS会按照父节点搜索顺序,选择更早的点.

如果有多个点的父节点相同,BFS会先选择编号最小的点.

由于BFS不能像电脑1样随机访问.所以,如果BFS从顶点i走到顶点j,需要移动从i到j的距离.

她觉的BFS真是太菜了.她想问你BFS最菜的时候需要走的距离.

输入格式.

输入格式如下:

n p2 p3 p4 ... pn 第1行有1个整数n.表示树上节点总数.

第2行有n-1个整数p_i (1 <= p_i < i).表示第i个点的父亲.

由于1号节点为根,所以没有p_1.

输出格式.

输出BFS最菜的时候找到自行车走的总距离.

输入样例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

来源.

Japan Alumni Group Spring Contest 2014.