最小斯坦纳树

解决一类图上存在 \(\mathcal O(\log)\) 量级关键点，使其连通的最小贡献子图的问题。

---

首先我们能轻易证明这个子图一定是树，因为断掉环不影响连通性。这棵树就是最小斯坦纳树。

我们不妨考虑状压 dp 求解。\(f_{i,S}\) 表示树根为 \(i\)，我们已经在这棵树中连通了 \(S\) 这些关键点，产生的最小贡献。

考虑类似树形 dp 进行转移。我们首先可以合并子树：

\[f_{i,S}\gets \min\limits_{T\subset S} f_{i,T}+f_{i,S\backslash T} \]

其次我们可以转移树根（这里利用了不合法不优，我们不在意新树根是不是关键点）：

\[f_{i,S}\gets f_{j,S}+w(j\to i) \]

然后考虑转移顺序。显然对于第一种转移，我们按照 \(S\) 从小到大转移就可以了。然后注意到对于每个 \(S\)，第二种转移本质上是对 dp 数组搞了一遍最短路，于是我们拿 dij 把 dp 数组松弛一遍就好了。

这是带边权的写法。点权也是类似的，只有一点很小的细节上的变化。

[ABC395G] Minimum Steiner Tree 2

题意

给定一张完全图，有 $Q$ 个询问 $S,T$。查询包含 $\{i|1\le i\le K\}\cup \{S,T\}$ 的边权和最小斯坦纳树。

保证 \(K+1\le S,T\)。

我们考虑状压 \(1\) 到 \(K\) 这一部分的永久关键点，在状态最后带两个非关键点。换句话说，我们设 \(f_{S,i,j,k}\) 表示现在 \(1\) 到 \(K\) 中的关键点连通了 \(S\)，树根是 \(i\)，存在两个非关键点 \(j,k\) 的最小边权和。

然后你发现我们状态数起飞了。考虑我们是否真的有必要存储根加上两个非关键点。显然，我们可以强行钦定树根是两个非关键点的其中一个，答案仍然会是合法的状态。

于是我们现在已经直接就能做有一个非关键点的问题了（其实和原来的 dp 没有一点区别）。

考虑还有一个关键点怎么办。比较搞笑的是，这里的解决方式是直接暴力：我们直接把所有非关键点一个一个塞进关键点集合，做 \(n\) 次一个非关键点的最小斯坦纳树（也就是本身）把答案预处理出来即可。简单预处理最短路，时间复杂度 \(\mathcal O(n^23^k+n^32^k+q)\)，可以通过。

P3264 [JLOI2015] 管道连接

这里终于出现了一点不一样，我们可以不把所有关键点连在一起，只需要把同色的关键点连在一起就好了。

于是考虑简单地增加一条转移就行：当我们的状态里面关键点构成若干个颜色的全集的并，我们可以切换根而不做路径的贡献，因为新的根根本没有必要和目前的子图连通。

P4294 [WC2008] 游览计划

点权最小斯坦纳树，附加输出方案。

由于我的这个手太懒了，我不想写输出方案，所以不写了。