自闭了，sb斯坦纳树题没看出来，以此纪念..

\(dp_{s,i}\)表示点\(i\)联通关键点集合\(s\)的最小代价，转移显然。

\[ dp_{S,i}=\min_{Q+T=S}dp_{Q,i}+dp_{T,i}\\ dp_{S,i}=\min_{E(i,j)\in G}dp_{S,j}+\mathtt {edge_{i,j}} \]

对\(S\)分层，每层跑最短路即可。

最后再拿个dp合并斯坦纳森林

---

Code:

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using std::max;const int SIZE=1<<21;char ibuf[SIZE],*iS,*iT;//#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT?EOF:*iS++):*iS++)#define gc() getchar()template 
         
          void read(T &x){ int f=0;x=0;char c=gc(); while(!isdigit(c)) f|=c=='-',c=gc(); while(isdigit(c)) x=x*10+c-'0',c=gc(); if(f) x=-x;}void ckmin(int &x,int y){x=x