P1268 树的重量

题目描述

树可以用来表示物种之间的进化关系。一棵“进化树”是一个带边权的树,其叶节点表示一个物种,两个叶节点之间的距离表示两个物种的差异。现在,一个重要的问题是,根据物种之间的距离,重构相应的“进化树”。 令 $N=\{1,2,3,\cdots ,n\}$,用一个 $N$ 上的矩阵 $M$ 来定义树 $T$。其中,矩阵 $M$ 满足:对于任意的 $i$,$j$,$k$,有 $M[i,j]+M[j,k] \ge M[i,k]$。树 $T$ 满足: 1. 叶节点属于集合 $N$; 2. 边权均为非负整数; 3. $d_T(i,j)=M[i,j]$,其中 $d_T(i,j)$ 表示树上 $i$ 到 $j$ 的最短路径长度。 如下图,矩阵 $M$ 描述了一棵树。 $$M=\begin{bmatrix} 0 & 5 & 9 & 12 & 8 \\ 5 & 0 & 8 & 11 & 7 \\ 9 & 8 & 0 & 5 & 1 \\ 12 & 11 & 5 & 0 & 4 \\ 8 & 7 & 1 & 4 & 0 \\ \end{bmatrix}$$ 树的重量是指树上所有边权之和。对于任意给出的合法矩阵 $M$,它所能表示树的重量是惟一确定的,不可能找到两棵不同重量的树,它们都符合矩阵 $M$。你的任务就是,根据给出的矩阵 $M$,计算 $M$ 所表示树的重量。下图是上面给出的矩阵 $M$ 所能表示的一棵树,这棵树的总重量为 $15$。 ![](https://cdn.luogu.com.cn/upload/image_hosting/dnk8ys2t.png)

输入格式

输出格式