#21421. [MOI周比赛] 做任务赚硬币

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: chf123456

题目描述

Mirko 是一家大公司的CEO。该公司由N人组成,编号为1到N,Mirko 编号为1。每个员工(Mirko除外)都有一个老板,我们说这个员工是该老板的助手。每个老板都可以有多名助手。Mirko 没有老板,但有他的助手。

之后会有一些任务,Mirko 会将该任务委托给他编号最小的助手。然后,该助手也将任务委托给他编号最小的助手,并且这个过程重复进行,直到任务被发送给没有助手的人,然后他必须亲自完成任务。

执行任务的人获得1个硬币,那个人的老板获得 2个硬币,老板的老板获得 3个硬币,依此类推,一直到 Mirko 。之后,真正完成工作的员工意识到系统的不公平并感到伤心,并且不会再执行任务(也就是辞职)。

当公司收到的下一个任务时,因为少了一个人,所以薪水可能更少,但工作必须继续。任务是无限多的(直到公司倒闭),因此整个过程(分配新任务,执行任务,划分薪水和执行任务人员的退出)重复进行,最后 Mirko 独自留在公司并完成他的第一个(也是他的最后一个)任务。

当然,在此之前,Mirko 将积累相当多的财富,但他也想知道每个员工赚了多少钱。

输入格式

第一行有一个整数 N,包括 Mirko 在内的员工的个数。

第二行有 n−1 个整数,分别为a2,a3,...,an,依次表示编号 2,3,4,..n 的员工的老板。

输出格式

输出一行 N 个整数,第 i 个整数表示编号为 i 的人获得的硬币数量

样例

3
1 1

5 1 1

5
1 2 2 4

13 8 1 3 1

数据范围与提示

对于 50% 的数据,2≤N≤5000。

对于 100% 的数据,2≤N≤2×105