题目描述

Mirko has become CEO of a huge corporation. This corporation consists of ​N people, labeled from 1 to ​N , and Mirko is labeled 1. The corporation is structured so that each employee (except Mirko) has a boss, and we say that employee is an assistant to that boss. Each boss can have multiple assistants, but still reports to their boss. This holds for everyone except Mirko, who is at the top of the pyramid and doesn’t have a boss, but has his assistants.

When Mirko gets a task from the investors, he then delegates that task to his assistant with the minimal number. This assistant then delegates the task to their assistant with the minimal number, and this process repeats until the task is given to an unlucky person without an assistant, who then must do the task.

This is when the real problems begin. The person that did the task gets paid 1 coin, the boss of that person gets 2 coins, the boss of that person gets 3 coins, and so on, all the way to Mirko, who gets as many coins as there are people in this sequence. After that, the employee that really did the job realizes how unfair the system is and quits their job out of principle.

When it comes to doing the next task in the corporation, there is a person less, so maybe the paychecks are less, but the work must continue. Tasks are piling up, so the whole procedure (assigning a new task, doing it, dividing paychecks and the person doing the task quitting) repeats until Mirko is left alone in the corporation and does his first (also his last) task.

Of course, Mirko will have amassed quite a fortune until then, but he also wants to know how much money each of the employees earned.

输入格式

The first line of input contains the positive integer ​N (2 ≤ ​N ≤ 2·$10^5$​ ), the number of employees (including Mirko).

The following line contains ​N- 1 positive integers $a_2$​ , ​$a_3$​ , ​$a_4$ , …, ​$a_n$ (1 ≤ ​$a_i$ < ​i ), where ​$a_i$ denotes the boss of employee ​i .

输出格式

You must output a single line consisting of ​N numbers, the $i^{th}$ number corresponding to the amount of money earned by the $i^{th}$ employee.

题目大意

Mirko是一家大公司的CEO。该公司由$N$人组成，编号为1到N，Mirko编号为$1$。公司的结构像一棵树一样，每个员工（Mirko除外）都有老板，我们说这个员工是该老板的助手。每个老板都可以有多名助手。Mirko没有老板，但有他的助手。

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

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

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

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

输入输出格式

输入格式： 第一行有一个整数$N(2 ≤ N ≤ 2e5)$，既包括Mirko在内的员工的个数。 紧接着第二行有$n-1$个整数，分别为$a2,a3,\cdots ,an(1 ≤ a_i < i )$，$ai$表示$ai$的上级。

输出格式

输出一行$N$个整数，第$i$个整数表示编号为$i$的人 能得到的金币数。

说明

$50\%$的数据满足$2≤N≤5000$。

3
1 1

5 1 1

5
1 2 2 4

13 8 1 3 1

提示

In test cases worth 50% of total points, it will hold 2 ≤ ​N ≤ 5000.

Clarification of the second test case:

Mirko assigns the first task to employee 2, who then assigns it to employee 3, who then does it. For this, employee 3 gets 1 coin, employee 2 gets 2 coins, and employee 1 (Mirko) gets 3 coins. Employee 3 then quits.

Mirko assigns the second task to employee 2, who then assigns it to employee 4 (because employee 3 quit), who then assigns it to employee 5, who then does it. For this, employee 5 gets 1 coin, employee 4 gets 2 coins, employee 2 gets 3 coins, and employee 1 gets 4 coins. Employee 5 then quits.

The procedure is repeated for a total of 5 tasks.

In total, Mirko gets 13 coins, employee 2 gets 8, employee 4 gets 3, and employee 3 and 5 each get 1 coin.