# Arkady and a Nobody-men

## 题意翻译

一棵n个结点的有根树。定义dep(x)=x到根结点的简单路径上的点数。定义f(x,y)=∑[dep(p) ≤ dep(x)]，其中p在y的子树中且p≠y。定义g(x)=∑f(x,p)，其中x在p的子树中且p≠x。
对于所有i∈[1,n]，求g(i)。
数据范围：n<=5*10^5

## 题目描述

Arkady words in a large company. There are $ n $ employees working in a system of a strict hierarchy. Namely, each employee, with an exception of the CEO, has exactly one immediate manager. The CEO is a manager (through a chain of immediate managers) of all employees.
Each employee has an integer rank. The CEO has rank equal to $ 1 $ , each other employee has rank equal to the rank of his immediate manager plus $ 1 $ .
Arkady has a good post in the company, however, he feels that he is nobody in the company's structure, and there are a lot of people who can replace him. He introduced the value of replaceability. Consider an employee $ a $ and an employee $ b $ , the latter being manager of $ a $ (not necessarily immediate). Then the replaceability $ r(a,b) $ of $ a $ with respect to $ b $ is the number of subordinates (not necessarily immediate) of the manager $ b $ , whose rank is not greater than the rank of $ a $ . Apart from replaceability, Arkady introduced the value of negligibility. The negligibility $ z_{a} $ of employee $ a $ equals the sum of his replaceabilities with respect to all his managers, i.e. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF860E/505bc2ce43f8c1ae79d55147b7d11673e92ab6e4.png), where the sum is taken over all his managers $ b $ .
Arkady is interested not only in negligibility of himself, but also in negligibility of all employees in the company. Find the negligibility of each employee for Arkady.

## 输入输出格式

### 输入格式

The first line contains single integer $ n $ ( $ 1<=n<=5·10^{5} $ ) — the number of employees in the company.
The second line contains $ n $ integers $ p_{1},p_{2},...,p_{n} $ ( $ 0<=p_{i}<=n $ ), where $ p_{i}=0 $ if the $ i $ -th employee is the CEO, otherwise $ p_{i} $ equals the id of the immediate manager of the employee with id $ i $ . The employees are numbered from $ 1 $ to $ n $ . It is guaranteed that there is exactly one $ 0 $ among these values, and also that the CEO is a manager (not necessarily immediate) for all the other employees.

### 输出格式

Print $ n $ integers — the negligibilities of all employees in the order of their ids: $ z_{1},z_{2},...,z_{n} $ .

## 输入输出样例

### 输入样例 #1

```
4
0 1 2 1
```

### 输出样例 #1

```
0 2 4 2
```

### 输入样例 #2

```
5
2 3 4 5 0
```

### 输出样例 #2

```
10 6 3 1 0
```

### 输入样例 #3

```
5
0 1 1 1 3
```

### 输出样例 #3

```
0 3 3 3 5
```

## 说明

Consider the first example:
- The CEO has no managers, thus $ z_{1}=0 $ .
- $ r(2,1)=2 $ (employees $ 2 $ and $ 4 $ suit the conditions, employee $ 3 $ has too large rank). Thus $ z_{2}=r(2,1)=2 $ .
- Similarly, $ z_{4}=r(4,1)=2 $ .
- $ r(3,2)=1 $ (employee $ 3 $ is a subordinate of $ 2 $ and has suitable rank). $ r(3,1)=3 $ (employees $ 2 $ , $ 3 $ , $ 4 $ suit the conditions). Thus $ z_{3}=r(3,2)+r(3,1)=4 $ .