解決一類圖上存在 \(\mathcal O(\log)\) 量級關鍵點，使其連通的最小貢獻子圖的問題。

首先我們能輕易證明這個子圖一定是樹，因為斷掉環不影響連通性。這棵樹就是最小斯坦納樹。

我們不妨考慮狀壓 dp 求解。\(f_{i,S}\) 表示樹根為 \(i\)，我們已經在這棵樹中連通了 \(S\) 這些關鍵點，產生的最小貢獻。

考慮類似樹形 dp 進行轉移。我們首先可以合并子樹：

其次我們可以轉移樹根（這里利用了不合法不優，我們不在意新樹根是不是關鍵點）：

然后考慮轉移順序。顯然對于第一種轉移，我們按照 \(S\) 從小到大轉移就可以了。然后注意到對于每個 \(S\)，第二種轉移本質上是對 dp 數組搞了一遍最短路，于是我們拿 dij 把 dp 數組松弛一遍就好了。

這是帶邊權的寫法。點權也是類似的，只有一點很小的細節上的變化。

[ABC395G] Minimum Steiner Tree 2

我們考慮狀壓 \(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] 游覽計劃

點權最小斯坦納樹，附加輸出方案。

由于我的這個手太懶了，我不想寫輸出方案，所以不寫了。

P7450 [THUSCH 2017] 巧克力

還有人類嗎。

考慮先不管中位數的事，我們怎么解決第一問這個“至少包含 \(k\) 種顏色”的限制。

如果我們能給出這 \(k\) 種顏色，那么實際上就是最小斯坦納樹的模板改一改就好了。但是實際上我們不可能枚舉所有可能的顏色集合，那怎么辦呢？

介紹一個叫 color-coding 的 trick：實際上我們隨機地把所有顏色映射到 \([0,k)\) 當中，然后按照只有這些顏色來做是正確的。考慮一個答案連通塊何時可以被算到：當且僅當它身上有完整的 \([0,k)\) 所有顏色時。我們直接考慮這個連通塊上原本的顏色有 \(k^k\) 種染法，答案的染法是 \(k!\) 種，一次獨立隨機映射顏色的正確率是 \(\frac{1}{26}\)。

可以證明，如果答案連通塊中包含超過 \(k\) 種顏色，概率不會變小。綜上所述，這個隨機化的正確率并不差，我們隨機映射 \(150\) 到 \(250\) 次就很難出錯了。

現在我們解決了第一問，那么第二問也不難了。trickily，我們考慮二分中位數，把小于中位數的美味值設置為 \(-1\)，大于中位數的美味值設成 \(1\)，那么我們在 dp 中最小化連通塊大小的同時最小化權值和就好了。網格圖上用 SPFA 寫最短路沒有問題。

然后注意一下寫法。二分套隨機化的寫法我覺得比較合理，因為隨機化套二分正確性不是很嚴謹（考慮二分相當于同一種映射多測 \(\log\) 次），需要增加次數，然后疑似就會被卡常，需要在二分時剪枝。

當然不是說前面一個寫法不被卡常的意思。注意到我們需要的比較和運算的性質恰好和整數的比較和運算是相同的，所以我們考慮 dp 時把兩維壓在一起變成一個大進制數來做，也就是把權值設置成 \(10^3+2\) 和 \(10^3\)，這樣前面的部分就表示連通塊中的點數，后面的部分就用來間接地表示權值和。

然后注意一下清空的復雜度，不要直接 memset dp 數組。因為實際上我們根本用不到 \(233\times 233\) 大小。