题目描述

树被用于表示物种间的进化关系。进化树是一种带边权的树，其中每个叶子节点代表一个物种。树上两个叶子节点之间的距离表示这两个物种的差异程度。计算生物学中的一个重要问题是根据观察到的物种差异构建进化树。

设 $N = \{1 \cdots n\}$。若一个 $n\times n$ 的矩阵 $M$ 满足对称、非负，且对于任意的 $1\leq i, j, k \leq n$ 都有 $M[i, j] + M[j, k] \geq M[i, k]$（即三角不等式），则称 $M$ 是 $N$ 上的一个度量矩阵。若一个度量矩阵可以由一棵树实现，即存在一个带边权的树 $T$ 满足以下条件，则称该度量矩阵为树度量矩阵：

1. 树 $T$ 的叶子节点集合为 $N$；
2. 树 $T$ 中每条边的权值非负；
3. 对于任意的 $i, j \in N$，$d(T, i, j) = M[i, j]$，其中 $d(T, i, j)$ 表示树 $T$ 中节点 $i$ 和节点 $j$ 之间的最短路径长度。

例如，以下矩阵就是一个树度量矩阵，其对应的树如图 8 所示。

树的大小定义为树中所有边的权值之和。对于一个树度量矩阵，已经证明其对应的树的大小是唯一的，即不可能找到两棵大小不同的树来实现同一个树度量矩阵。你的任务是设计一个程序，计算给定树度量矩阵所对应的树的大小。下面这个简单的例子可能会有所帮助。当只有两个物种时，树只有一条边，树的大小就是这两个物种之间的距离。现在考虑有三个物种 $a$、$b$ 和 $c$ 的情况。设 $T$ 是对应的树，由于 $T$ 有三个叶子节点，所以存在一个内部节点 $x$。根据定义，路径长度 $d(T, a, b) = M[a, b]$。因为 $x$ 是节点 $a$ 和 $b$ 之间路径上的一个顶点，所以我们只需要确定边 $(x, c)$ 的权值（长度）。设 $w(x, c)$ 表示边 $(x, c)$ 的权值，我们有：

• $w(x, c) + w(x, a) = M[a, c]$；
• $w(x, c) + w(x, b) = M[b, c]$；
• $w(x, a) + w(x, b) = M[a, b]$。

因此，$w(x, c) = \frac{M[a, c] + M[b, c] - M[a, b]}{2}$。

输入

输入文件包含多个测试用例。每个测试用例的第一行是一个正整数 $n$（$2 < n < 30$）。接下来的 $n - 1$ 行表示树度量矩阵的上三角部分（不包含对角线元素）。每行代表矩阵的一行，元素之间用空格分隔。所有元素都是小于 $100$ 的非负整数。最后一个测试用例后面跟着一个 $0$ 表示输入结束。你可以假设输入的数据都是树度量矩阵，无需进行验证。

此外，树的大小等于测试用例中除第一行整数之外的所有整数之和。

输出

对于每个测试用例，在一行中输出对应的树的大小。

输入样例

5
5 9 12 8
8 11 7
5 1
4
4
15 36 60
31 55
36
0

输出样例

15
71

题目来源

台湾 2002 年竞赛题目