问题

给定一个由N个顶点组成的带权无向树。每个顶点从1到N编号。

初始时，所有边的权重都为1。对于顶点u和v，定义dist(u,v)为连接u和v的最短路径上边的权重之和。

此外，对于顶点u和v，

$f(u,v)=\max\\{dist(u2,v2)|dist(u,v2)=dist(u,v)+dist(v,v2) 且 dist(v,u2)=dist(v,u)+dist(u,u2)\\}$

即，定义f(u,v)为将顶点u和v相互远离时的距离的最大值。

定义"整个树的成本"为

$∑_{u∈ \\{1,...n\\} ,v ∈ \\{1,...,n\\} , u < v}$ $f(u,v)$

对于每条边，编写一个程序来计算将该边的权重设置为2时，"整个树的成本"增加了多少。

---

输入

输入以以下格式从标准输入中提供。

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

• 第1行包含表示树的顶点的整数N（2 ≤ N ≤ 252525）。
• 第2行包含N-1个以空格分隔的整数，表示树的边。第i（1 ≤ i ≤ N-1）个整数表示连接顶点$p_i$（1 ≤ $p_i$ ≤ i）和顶点$i+1$的树边存在。

部分分

此问题有部分分。

• 对于满足N ≤ 300的数据集，如果能正确回答该数据集，将获得30分。
• 对于满足N ≤ 3000的数据集，如果能正确回答该数据集，将获得额外的50分。总计为80分。
• 如果能正确回答没有额外约束的数据集，将获得额外的160分。总共为240分。

输出

使用空格分隔的N-1个整数输出到一行中。

第i（1 ≤ i ≤ N-1）个整数表示将边（$p_i$，$i+1$）的权重设置为2时，"整个树的成本"增加的量。

输出时不要在行末添加多余的空格。同时，请勿忘记在输出末尾添加换行符。

---

示例1

5
1 1 2 2

输出例1

9 9 7 7

当将边(1,2)、(1,3)的权重设置为2时，

对于满足$1 ≤ u<v≤ N$的$(u,v)$组合，有$N*(N-1)/2=10$个。

对于$(u,v)≠(4,5)$，$f(u,v)$增加1，对于$(u,v)=(4,5)$，$f(u,v)$不变。因此，"整个树的成本"增加9。

当将边(2,4)的权重设置为2时，

对于$(u,v)=(2,4),(1,4),(3,4),(4,5),(1,3),(1,2),(2,3)$，$f(u,v)$增加1，对于其他情况，$f(u,v)$不变。因此，"整个树的成本"增加7。

当将边(2,5)的权重设置为2时，

对于$(u,v)=(2,5),(1,5),(3,5),(4,5),(1,3),(1,2),(2,3)$，$f(u,v)$增加1，对于其他情况，$f(u,v)$不变。因此，"整个树的成本"增加7。

---

示例2

8
1 1 2 3 1 4 3

输出例2

24 23 24 18 7 24 18

---

示例3

5
1 1 1 1

输出例3

7 7 7 7

---

示例4

10
1 2 2 2 3 3 4 5 6

输出例4

9 35 25 25 30 9 25 25 30

---