题目描述

给出一棵树的叶子节点两两之间的距离,求这棵树的边权和。

题目分析

令a(i,j)为叶子i到j的距离
由于这是一棵树。
n=2的时候,只有一条链。

n=3的时候,由于是一棵树,所以3肯定连在1到2的那条链上,那么红边长=(a(1,3)+a(2,3)-a(1,2))/2

n=4的时候,4要么连在1到2的链上,要么连在1到3的链上(这样2到3的链已经包括在里面了),所以我们枚举并求最小新边权即可。

代码