Problem Description

Given a weighted undirected tree with $N$ vertices, where vertices are numbered from $1$ to $N$.

Initially, all edge weights are $1$. For vertices $u$ and $v$, let $dist(u,v)$ be the sum of the weights of the edges on the shortest path connecting $u$ and $v$.

For vertices $u$ and $v$, define

$f(u,v) = \max \{ dist(u2,v2) \mid dist(u,v2) = dist(u,v) + dist(v,v2) \text{ and } dist(v,u2) = dist(v,u) + dist(u,u2) \}$

This means the maximum distance when moving vertices $u$ and $v$ away from each other.

Define the "total cost of the tree" as

$\sum_{u \in \{1, ..., n\}, v \in \{1, ..., n\}, u < v} f(u,v)$

Create a program that outputs how much the "total cost of the tree" increases when the weight of each edge is changed to $2$.

Input Format

Input is given from standard input in the following format:

$ N $ $ p_1 $ $ p_2 $ ... $ p_{N-1} $

• The first line contains an integer $N (2 \leq N \leq 252525)$ representing the number of vertices in the tree.
• The second line contains $ N-1 $ integers separated by spaces, where the $i (1 \leq i \leq N-1)$-th integer indicates an edge between vertex $p_i (1 \leq p_i \leq i)$ and vertex $ i+1 $.

Output Format

Output $ N-1 $ integers separated by spaces on one line.

The $i (1 \leq i \leq N-1)$-th integer represents the increase in the "total cost of the tree" when the weight of edge $ (p_i, i+1) $ is changed to $2$.

Do not include extra spaces at the end of the line, and ensure there is a newline at the end of the output.

Sample Input and Output

Sample Input #1

5
1 1 2 2

Sample Output #1

9 9 7 7

Sample Input #2

8
1 1 2 3 1 4 3

Sample Output #2

24 23 24 18 7 24 18

Sample Input #3

5
1 1 1 1

Sample Output #3

7 7 7 7

Sample Input #4

10
1 2 2 2 3 3 4 5 6

Sample Output #4

9 35 25 25 30 9 25 25 30

Notes/Hints

Partial Points

This problem has partial scoring:

• $30$ points are awarded for correctly solving the dataset where $N \leq 300$.
• An additional $50$ points are awarded for correctly solving the dataset where $N \leq 3000$. This totals $80$ points.
• An additional $160$ points are awarded for correctly solving the dataset without additional constraints. This totals $240$ points.

见题面 Input 部分

见题面 Output 部分