固定直径树的距离平方和问题

Sum of the squares of all distances in a tree with fixed diameter

定义图G中所有点对间的距离的平方和为S(G)=∑uv∈VGd2G(u,v)=1/2∑v∈VGLG(v),其中dG(u,v)为图G中任意顶点u,v之间的距离,LG(v)表示图G中点v到其它点的距离的平方和。在所有直径为d的n顶点树中分别确定使S(G)最小和第二小的树。

Denote the sum of the squares of all distances between all pairs of vertices in G by S（G）=∑uv∈VGdG^2（u,v）=1/2∑v∈VGLG（v）where dG（u,v） is the distance between u and v in G and the sum goes over all the pairs of vertices, LG（v） denotes the sum of the squares of all distances from u in G. The trees with minimum and second-minimum S（G） among all the trees with n vertices and diameter d are obtained respectively.