AT_icpc2014spring_a.Breadth-First Search by Foxpower
通过率：0%
AC君温馨提醒
该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。
题目描述
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.
输入解题思路，AI测评打分。不知道怎么写?