题意：在一棵数的叶子上建k个工厂保证，求两两距离之和的最小值。
思路：如果一个一个叶子节点去考虑去与否太麻烦了，直接考虑该节点的子树上选取几个作为工厂，利用树形DP，dp[u][i]表示的是u节点为根的子树选取了i个叶子作为工厂的最小值。
转移方程：dp[u][i]=min(dp[u][i],dp[u][i-k]+dp[v][k]+w*k*(m-k)),v表示u的子节点，k表示在u的子节点子树上选取个数,w*k*(m-k)表示这条边的贡献。
AC代码：
1 int n,m,cas; 2 ll dp[maxn][102]; 3 int siz[maxn]; 4 struct node{ 5 int u; 6 ll w; 7 node(int _u,ll _w){ 8 u=_u; 9 w=_w; 10 } 11 }; 12 vector<node>a[maxn]; 13 void dfs(int u,int fa){ 14 if(a[u].size()==1){ 15 dp[u][1]=0; 16 siz[u]=1; 17 } 18 dp[u][0]=0; 19 rep(i,0,a[u].size()-1){ 20 int v=a[u][i].u; 21 ll w=a[u][i].w; 22 if(v==fa) continue; 23 dfs(v,u); 24 siz[u]+=siz[v]; 25 dp[u][m]=min(dp[u][m],dp[v][m]); 26 for(int j=min(m,siz[u]);j>=1;j--){ 27 for(int k=1;k<=min(j,siz[v]);k++){ 28 dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]+1ll*w*k*1ll*(m-k)); 29 } 30 } 31 } 32 } 33 void init(){ 34 rep(i,0,n) a[i].clear(); 35 mem(siz,0); 36 // mem(dp,INF); 37 rep(i,1,n) rep(j,1,m) dp[i][j]=INF; 38 } 39 void run(){ 40 n=rd(),m=rd(); 41 init(); 42 rep(i,1,n-1){ 43 int u=rd(),v=rd(); 44 ll w=rdll(); 45 a[u].push_back(node(v,w)); 46 a[v].push_back(node(u,w)); 47 } 48 int rt=1; 49 rep(i,0,n){ 50 if(a[i].size()>1){ 51 rt=i; 52 break; 53 } 54 } 55 rep(i,0,n) dp[i][0]=0; 56 dfs(rt,-1); 57 printf("Case #%d: %lld ",++cas,dp[rt][m]); 58 } 59 signed main() 60 { 61 int t=rd(); 62 while(t--){ 63 run(); 64 } 65 // run(); 66 return 0; 67 }