题意：在一棵数的叶子上建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 vectora[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\n",++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 }