传统题 1000ms 256MiB

T4

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

𝐽𝐾成为了一个大型企业的𝐶𝐸𝑂, 包含𝐽𝐾本人在内,这个公司一共有𝑁个人,编号从1到𝑁, 𝐽𝐾的编号为1,公司员工关系的构建使得所有的员工(除了𝐽𝐾)都有一个直属上司。
我们称一名员工为他的直属上司的一位助手。每一位上司可以有多个助手,但他也会有一个直属上司,除 了𝐽𝐾—这个企业的最终𝐵𝑂𝑆𝑆。我们保证任何一个员工的最终上司都是𝐽𝐾。
当𝐽𝐾接到了一个来自客户的委托的时候,他会把任务分配到给他编号最小的一个助手。然后得到任务的这个人又会把任务分配给他的编号最小的助手。以此类推,直到一个没有助手的人接到了这份工作。
这就是真正的问题的开端。真正着手进行工作的员工只获得了一个硬币的工资,而他的上司则获得了两个硬币的工资,他上司的上司则获得了三个硬币的收益。以此类推,在这份工作完成之后,真正完成工作的雇员意识到了这个制度是多么的邪恶,于是他决定退出这个公司。
当下一个委托到达的时候,这样的过程将会重复,直到最后𝐽𝐾接手进行自己的第一份(也是最后一份)工作。
当然,在公司完全解散之前, 𝐽𝐾仍然可以获得一笔不菲的财富。你的任务就是计算出𝐽𝐾的公司在解散之前每位员工究竟可以获得多少硬币。

输入格式

第一行包含一个正整数𝑁(2𝑁2105)𝑁(2 ≤ 𝑁 ≤ 2 * 10^5),含义如题面所示。
接下来一行𝑁 − 1个正整数𝑎2,𝑎3,𝑎4,,𝑎𝑛,(1𝑎𝑖<i)𝑎𝑖𝑎2, 𝑎3, 𝑎4, … , 𝑎𝑛, (1 ≤ 𝑎𝑖 < i), 𝑎𝑖表示员工𝑖𝑖的直属上司。

输出格式

输出一行𝑁𝑁个整数,第𝑖𝑖个整数表示编号为𝑖𝑖的员工获得的硬币数。

数据范围

存在50%的数据, 2𝑁50002 ≤ 𝑁 ≤ 5 000

样例

样例输入1

3
1 1

样例输出1

5 1 1

样例输入2

5
1 2 2 4

样例输出2

13 8 1 3 1

样例二解释:

第一个工作的传播路径为1−> 2−> 3,随后3退出, 3获得一个硬币, 2获得两个硬币,1获得三个硬币。
第二个工作的传播路径为1−> 2−> 4−> 5, 随后5退出, 5获得一个硬币,4获得两个硬币, 2获得三个硬币, 1获得四个硬币。
随后的工作传播路线为1−> 2−> 4, 1−> 2, 1。最终获得的硬币为13,8,1,3,1。

夏季清凉赛

未参加
状态
已结束
规则
IOI
题目
6
开始于
2023-7-10 18:30
结束于
2023-7-10 20:15
持续时间
1.8 小时
主持人
参赛人数
124