/ 
Time Limit: 2.525 sec / Memory Limit: 246 MB
問題文
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