题意理解
要你构造一棵nn个节点的严格次小生成树.
算法解析
分析条件
题目中给出的关键点,就是严格和次小.
什么是严格
就是题目强制要求严格单调性,不可以有=号的出现.
什么是次小
我们应该都知道,最小生成树,它要求边集合的边总和最小,那么次小生成树,要求边集合的边总和只比最小生成树边集合权值大.
总结性质
有至少一个（严格）次小生成树，和最小生成树之间只有一条边的差异
总而言之,言而总之,我们现在知道了这条多余边的加入.,一定会产生非最小生成树.
我们不妨令
ans=最小生成树边权之和
假如说我们将多余边,替换掉最大权值边.
Val1==>z此时我们发现当前生成树
W=ans+z−Val1
W=最小生成边权之和+加上多余边−最大权值边
这一轮替换,我们可以认为这棵生成树有潜力成为次小生成树.
然后,我们发现,换一换次大边,也是可以的.
我们将多余边,强行替换掉次大权值边.
Val2==>z此时当前生成树
W=ans+z−Val2
W=最小生成树之和+加入多余边−次大权值边
现在所有的候选生成树都出来了,但是我们面临一个非常严重的问题.
我们如何快速计算,一条路径上的最大边,和次大边.
动态规划
我们可以当前需要知道的状态,无非就是两个.
一条路径上的最大边
一条路径上的严格次大边
所以说,我们不妨就按照倍增数组的思路,去制造两个新数组.
最大边数组
严格次大边数组
f[x][k]=f[fa[x][k−1]][k−1]
f[x][k]=f[fa[x][k−1]][k−1]
这是我们非常熟悉的Lca倍增数组.
然后咱们现在其实,手上掌握的最有力的性质,就是最值性质.
我们假设一条路径是由三段构造而成.
是三段,不是就三个点.
a=>c,c=>b,b=>a
a=>c,c=>b,b=>a
我们发现
A=>B的最大值其实等于max(A=>C最大值,B=>C最大值)
这就是区间最值性质.
不过严格次大边,就比较麻烦了,不慌,咱们慢慢画图来.
为了下面简述方面,我们设置一下变量.
A=>C上最大边权为ValA,C 次大边权为VA,C
C=>B上最大边权为ValB,C 次大边权为VB,C
A=>B上最大边权为ValA,B次大边权为VA,B
巧计一下,Val字母多,所以是最大边权,V字母少,所以是次大边权.
我们分类讨论一下,三种情况.
①第一段最大值=第二段最大值
ValA,C=ValB,C
我们发现两段居然最大值一样.
次大边权就只能
VA,B=max(VA,C,VB,C)
②第一段最大值<第二段最大值.
那么此时,次大边权是可以取第一段最大值.
因为此时总段的最大值,一定是第二段最大值.
ValA,B=ValB,C因此VA,B可以=ValA,C
综上所述,我们总结下来就是.
VA,B=max(ValA,C,VB,C)
③第一段最大值>第二段最大值.
那么此时,次大边权是可以取第二段最大值.
因为此时总段的最大值,一定是第一段最大值.
ValA,B=ValA,C因此VA,B可以=ValB,C
同样,总结一下.
VA,B=max(ValB,C,vA,B)
然后我们将A,B,C具体化一下.
A其实就是起始节点.
C其实就是A跳跃了2^(i−1)格节点.
B其实就是A跳跃了2^i格节点.