AT_icpc2014spring_a Breadth-First Search by Foxpower
题目描述
## 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
输出格式
输出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.