**赞**
by 摆渡 @ 2018-11-04 17:47:56
没错，只要能维护加点时图的合法性，想怎么加都行，贪心应该说是一种一定正确的维护方法。
by DarkValkyrie @ 2019-08-27 21:37:20
@[xeonz1](/space/show?uid=42139) 为什么在最小的情况下是没有冲突的
by nardo_ @ 2019-08-30 17:58:31
@[DarkValkyrie](/space/show?uid=125299) 怎么证明贪心出最小的一定是正确的维护方法 求解答
by nardo_ @ 2019-08-30 18:00:34
@nardo
窝尝试口胡一下，严谨证明就算了（本人理解，不一定对）：
首先，题目明确给出对于一个特定的矩阵，其对应的树的重量是唯一的。
重点在于，题目还告诉我们：
dT(i,j)=M[i,j]，其中dT(i,j)表示**树上i到j的最短路径长度**。
试想你肯定不能每次都枚举一遍之前所有加入的节点，检验新加入节点的合法性。
所以每次加点时，我们贪心选取使得最短路径性质成立的情况加入答案。
细一点说的话：
假设目前要加入第$i$个点，我们枚举另外两个$1\sim i-1$的节点$j,k$，此时我们要找出：$min\{(a[i][k]+a[i][j]-a[j][k])/2\}$
首先这个玩意是新增树的重量的值，可以借助题解那边那个图，理解为新增权值。
为什么是这个玩意的最小值？为什么要最小化？
首先矩阵里头存的是最短路径，我们就要好好利用。如果我们找出使得当前树的总边权增加最少的情况，这就能使得这个新加入的点到其它任意点的距离不能再小，刚好满足最短路径性质。
正是利用这两个性质，我们可以贪心地构造出解。
by DarkValkyrie @ 2019-08-30 19:10:10
@[DarkValkyrie](/space/show?uid=125299) 不枚举一遍树上所有节点，怎么判断新节点的合法性。新节点到树上每个节点不是都应该等于M[][]才正确么？
by nardo_ @ 2019-08-30 19:53:34
@[DarkValkyrie](/space/show?uid=125299) 我就是不太明白为什么在最小的情况下这个新节点与所有的节点都没有冲突，你是通过点1和点i判断出来的新节点，那么按照道理来说新节点应该与1和i不冲突，但是其他点呢，为什么不需要判断一下
by nardo_ @ 2019-08-30 19:58:19
@[nardo_](/space/show?uid=236352) 不枚举一遍树上所有节点，怎么判断新节点的合法性。新节点到树上每个节点不是都应该等于M[][]才正确么？||
是这样的，我一开始也琢磨了很久，为什么不检验新节点到其它每个节点的合法性。
应该是这样理解：对于每一次加点，我们都让这个点符合最短路性质。
然后问题就来到怎么让这个新点符合最短路性质。
其实，你要考虑到在我们的假设下，每次加入新节点时，之前已经加入的节点都是符合最短路性质的，也可以说是符合题给矩阵要求的。
**如果新节点加入以后新多出来的树的重量不能再小的话（第一篇题解里的那个叫len的东西），也就意味着这个新节点到剩下的所有点距离也是最短的。**
by DarkValkyrie @ 2019-08-30 20:36:14
还有一个这边不是通过1，i两个点判断新节点合法性，而是找某两个点（也有可能是一个点），使得这个新节点造成的树的重量的增量最少。
by DarkValkyrie @ 2019-08-30 21:44:39
@[nardo_](/space/show?uid=236352)
大学刚开学。。。一年没有看oi了。。。
by xeonz1 @ 2019-09-02 10:12:40