Dotcpp  >  编程题库  >  蓝桥杯2021年第十二届省赛真题-左孩子右兄弟
题目 2606:

蓝桥杯2021年第十二届省赛真题-左孩子右兄弟

时间限制: 1Sec 内存限制: 128MB 提交: 1006 解决: 345

题目描述

对于一棵多叉树,我们可以通过 “左孩子右兄弟” 表示法,将其转化成一棵
二叉树。
如果我们认为每个结点的子结点是无序的,那么得到的二叉树可能不唯一。换句话说,每个结点可以选任意子结点作为左孩子,并按任意顺序连接右兄弟。
给定一棵包含 N 个结点的多叉树,结点从 1 至 N 编号,其中 1 号结点是根,每个结点的父结点的编号比自己的编号小。请你计算其通过 “左孩子右兄弟” 表示法转化成的二叉树,高度最高是多少。注:只有根结点这一个结点的树高度为 0 。

例如如下的多叉树:

蓝桥杯2021年第十二届省赛真题-左孩子右兄弟1

可能有以下 3 种 (这里只列出 3 种,并不是全部) 不同的 “左孩子右兄弟”
表示:
蓝桥杯2021年第十二届省赛真题-左孩子右兄弟2


其中最后一种高度最高,为 4


输入格式

输入的第一行包含一个整数 N。
以下 N 1 行,每行包含一个整数,依次表示 2 至 N 号结点的父结点编号。

输出格式

输出一个整数表示答案。

样例输入

5
1
1
1
2

样例输出

4

提示

【评测用例规模与约定】
对于 30% 的评测用例,≤ ≤ 20
对于所有评测用例,≤ ≤ 100000
标签

通过率

统 计

 提交 1006
 正确 345
 格式错误 0
 答案错误 192
 时间超限 330
 内存超限 6
 输出超限 30
 运行错误 44
 编译错误 59