ztm 的二叉树转换

题目描述

ztm 最近学习了二叉树的遍历序列知识，但是毕竟不是所有的树都叫二叉树

这让 ztm 非常头疼，于是他自己自创了一种 二叉树转换法

可以把一棵非二叉树用这种方法转换成一棵二叉树！

ztm 会从根节点 $root$ 出发，用递归的形式遍历每个节点

当遍历到节点 $A$ 时， ztm 会列出 $A$ 的所有兄弟节点 $x$，以及 $A$ 的所有孩子节点 $y$

接着随机选择一个孩子节点 $y1$ 成为 $A$ 的左儿子，再随机选择一个兄弟节点 $x1$ 成为 $A$ 的右孩子

递归遍历刚才选出的两个节点

但是显然，这种转换方式会构造出非常多不同形态的二叉树

为了不浪费空间， ztm 希望转换出来的二叉树深度尽可能小

他想知道在给定一棵树的情况下，构造出的树深度最小是多少？

输入格式

输入第一行一个整数 $n$ 表示这棵树的节点数量

接下来一行包含 $n - 1$ 个数字，分别表示 $2 \sim n$ 每个节点的父亲节点编号

题目保证第 $i$ 个节点的父亲编号均小于 $i$

输出格式

输出一个整数，表示这棵树用 二叉树转换法 转换成二叉树后最小的深度

数据范围

对于 $20\%$ 的测试数据满足：$n \leq 10$

对于 $50\%$ 的测试数据满足：$n \leq 500$

对于 $100\%$ 的测试数据满足：$n \leq 100000$

样例输入

10
1 1 1 2 3 4 4 5 7

样例输出

5

样例解释

$1$ 选 $2$ 作为左儿子，$1$ 没有兄弟，所以没有右儿子
$2$ 选 $5$ 作为左儿子，选 $4$ 作为右儿子
$5$ 选 $9$ 作为左儿子，$5$ 没有兄弟，所以没有右儿子
$4$ 选 $7$ 作为左儿子，选 $3$ 作为右儿子
$7$ 选 $10$ 作为左儿子，选 $8$ 作为右儿子
$3$ 选 $6$ 作为左儿子，此时 $3$ 已经没有兄弟节点了，所以没有右儿子