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. , 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 $ .