UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4632. 树的编码

统计 下载数据

Description

SHUXK 正在对一棵N个结点的有根树进行研究,首要的一件事就是对这棵树进行编码。
lz 说:“这还不容易吗?我令根节点的编号为 1,然后保证每个结点的编号都比它的父亲结点的编号大。这样不
就行了吗?”但 SHUXK 对这种编码方案并不满意,因为没什么特色,从中也得不到什么有用的信息。于是他想出
了一种新的编码,这种编码需要满足两个条件:
1. 作为一个 OIer,应该保证每个结点的编码是一个 01 串;
2. 为了体现树的特点,假设??号结点的编码为Si,应该有如下性质:
如果结点U是结点V的祖先,那么Su就应该是Sv的前缀;
如果结点U不是结点V的祖先或后代,那么Su就不允许是Sv的前缀。
lz 说:“ 这样编码确实有特色。 但是这样一来,编码会很长呀!”
SHUXK 说:“我们就来求一种最优的编码,使得所有结点的编码长度之和最小。”当然, lz 和 SHUXK 都已经从 
OI 界退役了,他们讨论完了以后就把这个任务交给你了。

Input

输入文件的第一行包含一个正整数N(N<=10^5),表示棋盘的大小。
第二行包含N - 1个整数, 分别表示2~N号结点的父亲结点Fi( 保证Fi<i,也就是说 lz 已经编码好了)。

Output

输出文件只有一行一个整数, 表示所有结点编码长度之和的最小值。

Sample Input

5
1 1 3 3

Sample Output

6

Hint

Source