自动搬运

查看原文

来自洛谷，原作者为

	TsReaper **

搬运于2025-08-24 21:23:08，当前版本为作者最后更新于2015-07-30 19:43:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

锻炼思维的好题，需要运用一些树的性质。以下用g(i,j)表示点i与点j之间的距离。

首先，我们考虑n=2时的情况，很显然答案就是g(1,2)。

接下来考虑n=3时的情况。由于所有点均为叶子节点，很显然点3是从点1到点2的路径上分叉出来的，就像下图。

设蓝色部分长度为len，那么答案就是g(1,2)+len。len怎么求呢？显然，len = (g(1,3)+g(2,3)-g(1,2))/2。

n>3的情况也同理。枚举i，看看点n是不是从点1~i的路径上分叉出来的，求出的最小len就是要加到答案里面去的。如下图。

如果认为点4是从1~2的路径上分叉出来的，答案就会加上红色部分的长度。但是红色部分长度显然有一部分是多余的。只有认为点4是从1~3的路径上分叉出来的，才能加上正确答案（也就是蓝色部分）。