这个题目如果不是模板题的话有点好，可是他是模板。
这个题其实是我随机跳题跳到的。
我看到他的 k<=5 我觉得很奇怪，然后画了一下 k=3,4,5 的所有情况。
然后我就发现这个复杂度是 \(O(n^{\max(1,k-2)})\) 的。很不好。
然后我就想到因为这个 k 很小是不是能用一些奇怪的 dp 来求。
但是我推了好几次都是错的。
后来我发现这个问题其实是最小斯坦纳树。
然后我就学了一下就做完了。
其实 dp 是正确的，只需要记录当前在哪个点，然后集合是什么就可以了。
这个题目如果不是模板题的话有点好，可是他是模板。
这个题其实是我随机跳题跳到的。
我看到他的 k<=5 我觉得很奇怪，然后画了一下 k=3,4,5 的所有情况。
然后我就发现这个复杂度是 \(O(n^{\max(1,k-2)})\) 的。很不好。
然后我就想到因为这个 k 很小是不是能用一些奇怪的 dp 来求。
但是我推了好几次都是错的。
后来我发现这个问题其实是最小斯坦纳树。
然后我就学了一下就做完了。
其实 dp 是正确的，只需要记录当前在哪个点，然后集合是什么就可以了。