AT_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)\} $ 即， $f(u,v)$ 表示将顶点 $u$ 和 $v$ 朝着彼此远离的方向移动时的最大距离。 定义“整棵树的代价”为： $$\sum_{}^{} {f(u,v)}\\ ({u \in \{1,...n\}\ ,v \in \{1,...n\}\ , u < v})$$ 请编写一个程序，计算将每条边的权重设置为$ 2 $后，整棵树的代价增加了多少。

从标准输入中按以下格式读取输入： > $ N $ $ p_1 $ $ p_2 $ ... $ p_{N-1} $ - 第 $1$ 行包含一个整数 $N(2 \le N \le 252525)$，表示树的顶点数。 - 第 $2$ 行包含 $N-1$ 个整数，以空格分隔，第$ i(1\le i\le N-1) $个整数表示连接顶点 $p_i(1\le p_i\le i)$ 和顶点 $i+1$ 的树边。

输出 $N-1$ 个整数，以空格分隔，表示将边 $(p_i,i+1)$ 的权重设置为 $2$ 后，整棵树的代价增加了多少。 确保输出末尾没有多余的空格，并在最后记得输出换行。 ## 样例 ### 输入 ``` 5 1 1 2 2 ``` ### 输出 ``` 9 9 7 7 ``` ### 样例解释 设置边 $(1,2), (1,3)$ 的权重为 $2$ 后，整棵树的代价增加 $9$。设置边 $(2,4)$ 的权重为 $2$ 后，整棵树的代价增加 $7$。 （题目中的示例解释已经包含在了原文中，这里不再重复翻译。）

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