8632: BZOJ4632:树的编码

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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


输入格式

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


输出格式

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


样例输入

5
1 1 3 3

样例输出

6

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: