Mato is No.1

相关链接

Orz AHdoc!!!!!!!!!!!!!

这种神犇算法的关键在于真正利用了MST是一棵“树”的性质。也就是，它在求出MST后把它转化为有根树，然后，按长度递增顺序对于图中每一条不在MST中的边(i, j)，找到树中i、j的最近公共祖先(LCA)，记为p=LCA(i, j)。这样，树中i->p->j就是从i到j的路径。然后，依次扫描这条路径上的所有的边，将新边(i, j)的长度与路径上所有边的长度比较，找到长度差最小的（不过由于边(i, j)的长度一定不小于路径上所有边的长度，所以只要找到路径上最长边，则“删去这条最长边，加入边(i, j)”一定是所有加入的边为(i, j)的可行变换中代价最小的），取这个长度差最小的即可。不过最为神犇的一点是，这个算法在遍历完这条路径后，会将路径上所有的点（p点除外）的父结点全部设为p，也就是相当于并查集的路径压缩！这虽然会改变树的形态，但任何两点的LCA都是不会变的，因此不会影响后面的边。

注意上面“按长度递增顺序”是重点，原因是“路径压缩”可能会改变某些点之间的路径，也就是将某些点之间的路径长度减小。但是，很容易发现，被“压缩”的这些边必然是已经访问过的，也就是说这些边必然已经作为了前面的某条边(i, j)，i到j路径上的边。对于这条边来说，可行变换中，新加入的边的长度应尽量小，因此，如果按长度递增顺序，则这些边在(i, j)之后肯定不会出现代价更小的可行变换，因此就可以将它们压缩，不会影响最优解。

复杂度分析：先不管求LCA的时间复杂度。设树中结点i的深度为h[i]（h[root]=0）。对于树中的任意一个叶结点v，从root到v的路径的总长度（总边数）为h[v]，因此，若某次要尝试的边(i, j)的某一端点（设为i）在从root到v的这条路径上，则p=LCA(i, j)一定也在这条路径上。这样，访问从i到p的路径上的总访问次数（也就是从i到p路径上的边数）为(h[i]-h[p])。在访问完成后，需要将从i到p路径上除p外的所有结点的父结点都设为p，也就是从root到v的路径的总长度减少了(h[i]-h[p]-1)。因此，在尝试所有不在MST中的边的过程中，访问从root到v的最初路径上的边的总次数不会超过(h[v]+这些边的总数)（这里h[v]指初始的h[v]）。因此可以得到：访问树中所有边的总次数不会超过（最初所有叶结点深度之和+2*M），M为所有不在MST中边的总数！由于“最初所有叶结点深度之和”不会超过Nlog2N，因此总时间复杂度为O(Mlog2M+M+Nlog2N)，其中O(Mlog2M)为用Kruskal求MST的时间，如果忽略这部分时间，则总时间复杂度为O(M+Nlog2N)。
其实这个算法的时间复杂度在忽略排序的情况下是线性的，即O(M+N)，但本沙茶搞不懂怎么证明这一步。

下面是具体实现时的注意事项：
（1）将MST转化为有根树时，应用BFS，而不要用DFS，否则对于特殊数据可能爆栈；
（2）求LCA时，应用先让深度大的结点向上的方法（AHdoc神犇的方法），具体见下面的代码片段1；或者应用两者同时往上的方法（本沙茶的方法），具体见下面的代码片段2；否则，对于树是一条链，且每次访问都是访问最深的两个结点时，一次求LCA的时间复杂度可能升到O(N)。

【代码片段1】 【代码片段2】
【具体题目】Beijing2010 Tree（BZOJ1977）
这题要求严格次小生成树，因此在枚举的时候要注意，不能使可行变换的代价为0。