斯坦纳树

$dp[i][S]$表示 当前根为$i$当前生成树已经覆盖掉得关键点集合是$S$得最小代价。

转移分两种：

• 合并同一个根下的两种状态，$dp[i][S_1|S_2] = \min( dp[i][S_1]+dp[i][S_2] - w[i] ), S_1 \& S_2 = 0$

• 通过一个点状态转移到其他点的这个状态，就是选择一个点把根置成它

  $dp[j][S] = \min( dp[i][S] + w[j] )$。

转移的顺序是从小到大枚举集合，枚举所有点跑第一种转移，然后对这个状态跑第二种转移。

注意到这里没有必要判断$j$是否为关键点，如果它是关键点，在前面第一种转移中一定已经转移过了（除开这个点必然会剩下一个更小的集合，这个集合是已经被计算了的）。

复杂度是$n3^n$。

没有代码