問題文
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