AT_dwango2016final_d 木

[problemUrl]: https://atcoder.jp/contests/dwango2016-finals/tasks/dwango2016final_d $ 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\

入力は以下の形式で標準入力から与えられる。 > $ 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-1 $個の整数を空白区切りで$ 1 $行に出力せよ。 $ i(1\ ≦\ i\ ≦\ N-1) $番目の整数は、辺$ (p_i,i+1) $の重みを$ 2 $としたときの「木全体のコスト」の増加を表す。 行末に余計な空白を入れないこと。また、出力の最後には改行を忘れないこと。

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 300 $ を満たすデータセットに正解した場合、部分点として $ 30 $ 点が与えられる。 - $ N\ ≦\ 3000 $ を満たすデータセットに正解した場合、部分点として追加で $ 50 $ 点が与えられる。合計で$ 80 $点となる。 - 追加の制約のないデータセットに正解した場合、部分点として追加で $ 160 $ 点が与えられる。合計で$ 240 $点となる。 ### Sample Explanation 1 辺$ (1,2),\ (1,3) $の重みを$ 2 $としたとき、 $ 1≦\ u\