問題文

$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)\\}$

と定めます。すなわち、頂点$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$個の整数を空白区切りで$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

---