← 返回题目列表

AtCoder · dwango2016final_d

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 < 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