【题解】Solution Set - NOIP2024集训Day47 最小生成树
【题解】Solution Set - NOIP2024集训Day47 最小生成树
https://www.becoder.com.cn/contest/5606
色
12min 没思路……
「THUPC 2022 初赛」最小公倍树
做过，但是印象不多。
完全图，所以跟图的形态关系不大。
有直接倍数关系的可以直接忽略较大值。
能不能想办法继续缩小边的范围？
\[\text{lcm}(a,b)=\dfrac {ab}{\text{gcd}(a,b)}
\]
感觉跟调和级数有关系。
（FAKE
把所有因子跟其倍数连边，然后想办法让取 mst 的时候，实点 \(\to\) 虚点 \(\to\) 实点的边权和为 \(\text{lcm}\)。
感觉怪怪的，有些虚点也不是必须要在 mst 上的，没前途的。
10min
其实远没有这么复杂。我们考虑去枚举这个 \(d=\gcd(a,b)\)，我们只需要对每个集合 \(S=\{x|x=kd\}\) 内部连边，就一定能覆盖完 mst 中的所有边。注意这里 \(d\) 可能并不一定是真正的 \(\gcd\)，但是可以证明在取最终 mst 的时候，对于同一对 \((a,b)\) 一定会去选取 \(d\) 最大的那条边，也即取到 \(\gcd\) 了。
对于一个 \(S\) 中，显然将所有的元素都连向 \(S_\min\) 是最优的，因为 \(\gcd\) 一样，我们显然要让乘积最小。
这样边数就是调和级数 \(O(n\ln n)\) 的了。
然后跑 kruskal 就行。