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

时间限制: 1s 内存限制: 128MB 提交: 2004 解决: 739
题目描述
对于一棵多叉树,我们可以通过 “左孩子右兄弟” 表示法,将其转化成一棵
二叉树。
如果我们认为每个结点的子结点是无序的,那么得到的二叉树可能不唯一。换句话说,每个结点可以选任意子结点作为左孩子,并按任意顺序连接右兄弟。
给定一棵包含 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

比赛公告

填空题:https://www.lanqiao.cn/courses/2786/learning/?id=280827&compatibility=false