BJWC2010 严格次小生成树

MoSalah · 2022-10-03 13:35:58 · 个人记录

很简单，也很难想象这是北京省选的一道题。

就是个严格次小生成的板子啊。

所以就讲一下次小生成树吧。

注意，题面给的是 严格，所以就是一棵在无向图中，边权和最小的满足边权和 严格大于 最小生成树边权和的生成树（严谨定义）。

首先建出最小生成树，大家都会

然后讲一下非严格次小生成树：

• 定义：在无向图中，边权和最小的满足边权和 大于等于 最小生成树边权和的生成树

关于求解方法，我的描述有问题，后来想想还是用 \texttt{OI-wiki} 里的东西吧：

求解方法

• 求出无向图的最小生成树 T，设其权值和为 M。
• 遍历每条未被选中的边 edge=(u,v,w)，找到 T 中 u 到 v 路径上边权最大的一条边 edge'=(s,t,w')，则在 T 中以 e 替换 e'，可得一棵权值和为 M'=M+w-w' 的生成树 T'。
• 对所有替换得到的答案 M' 取最小值即可
  如何求 u\to v 路径上的边权最大值呢？

我们可以使用倍增来维护，预处理出每个节点的 2^i 级祖先及到达其 2^i 级祖先路径上最大的边权，这样在倍增求 \texttt{LCA} 的过程中可以直接求得。

那么有人会问，\texttt{LCA} 是什么？是一棵树上两个点向根节点的方向走，直到两个点的路径交汇的那个点，就是两个点的最近公共祖先，这个就不讲了，因为（下北沢慧音）跟我说他会了。

那么就要求严格的，相区别的就是一个是 \ge 另一个是 >。

那么解决方法很简单，我们维护到 2^i 级祖先路径上的最大边权的同时维护 严格次大边权，当用于替换的边的权值与原生成树中路径最大边权相等时，我们用严格次大值来替换即可。