题目描述

秋日将尽，大笨龙与聪明兔准备在森林里举办一场灯火舞会。大笨龙召集了一支筹备队，拟定了逐级转交任务、逐级发放酬劳的规矩，聪明兔则负责核清每位帮手最终应得的硬币。

筹备队共有 $n$ 位帮手，编号为 $1 \sim n$，按树形结构组织，$1$ 号是队长。对于每个 $1 \le i < n$，编号为 $i+1$ 的帮手的直属上级是 $p_i$。

每次有一项新任务到来时，首先交给队长。收到任务的人若还有尚未离队的直属下属，就把任务转交给其中编号最小的一位；收到任务的下属继续按照相同的规则转交，直到某位没有在队下属的帮手亲自执行任务。

每完成一项任务，亲自执行任务的人获得 $1$ 枚硬币，他的直属上级获得 $2$ 枚，上级的上级获得 $3$ 枚，以此类推，直到队长。硬币发放完毕后，亲自执行任务的人立即离开筹备队，不再参与后续任务。

筹备队不断接收新任务，直到所有人都已离队。请你求出每个人总共获得了多少枚硬币。

输入格式

从文件 task.in 中读入数据。

第一行包含一个整数 $n$。

第二行包含 $n-1$ 个整数 $p_1, p_2, \ldots, p_{n-1}$，其中 $p_i$ 表示编号为 $i+1$ 的帮手的直属上级。当 $n=1$ 时，第二行可以为空。

输出格式

输出到文件 task.out 中。

输出一行 $n$ 个整数，依次表示编号为 $1 \sim n$ 的帮手获得的硬币总数。

样例 1

3
1 1

5 1 1

样例1解释

$2$ 号、$3$ 号、$1$ 号依次亲自执行任务并离队。$1$ 号在前两项任务中各获得 $2$ 枚硬币，最后亲自执行任务时获得 $1$ 枚，共获得 $5$ 枚硬币；另外两人各获得 $1$ 枚硬币。

样例 2

5
1 2 2 4

13 8 1 3 1

样例2解释

$3$ 号、$5$ 号、$4$ 号、$2$ 号、$1$ 号依次亲自执行任务并离队，最终获得的硬币数分别如样例输出所示。

样例3

见附件中的 task3.in 与 task3.ans。

样例4

见附件中的 task4.in 与 task4.ans。

数据范围

对于所有数据，$1 \le n \le 2 \times 10^5$；对于所有 $1 \le i < n$，均有 $1 \le p_i \le i$。

本题共有 $20$ 个测试点，每个测试点 $5$ 分。

测试点编号	$n \le$	特殊性质
$1 \sim 2$	$20$	无
$3 \sim 4$	$300$
$5 \sim 8$	$5000$
$9 \sim 12$	$2 \times 10^5$	A
$13 \sim 16$	$10^5$	无
$17 \sim 20$	$2 \times 10^5$

特殊性质 A：对于所有 $1 \le i < n$，均有 $p_i=i$。

样例附件

下载全部样例（task-samples.zip）