题意：
给你一棵由 (n) 个结点构成的树，树的每条边都有权值，问在树的叶子结点上选定 (k) 个结点，使任意两个结点之间的距离之和最短，求出最小值。
想法：
- 结点之间距离之和最短问题，我们考虑每条边的贡献。此类问题大多数可以用树形dp解决。
- (dp[i][j]) 表示编号为 (i) 的结点为根的子树中有 (j) 个叶子结点被使用时的最优解。
- 考虑转移方程：(dp[u][x]=min(dp[u][x],dp[u][x-y]+dp[v][y]+w imes (k-y) imes y))，其中 (u)为当前结点， (v) 为 (u) 的父亲结点， (w) 为 (dis(u,v)) 。
- 那么对于每一对父子，我们都可以通过背包去求最优解，每次枚举范围一定是 (1sim min(k,siz[u]))， (siz[u]) 表示以 (u) 为根的子树的叶子数。
- 只要先选定一个非叶子结点作为根 (rt) ，然后一步步向叶子结点转移，最后答案就是 (dp[rt][k]) 。
代码：
struct node{
int nxt;
ll w;
};
int n,k;
vector<node>g[100005];
ll dp[100005][105];
int in[100005];
int siz[100005];
void dfs(int u,int fa)
{
if(in[u]==1){
siz[u]=1;
dp[u][1]=0;
}
for(int i=0;i<g[u].size();i++){
int v=g[u][i].nxt;
ll w=g[u][i].w;
if(v==fa)continue;
dfs(v,u);
siz[u]+=siz[v];
for(int x=min(k,siz[u]);x>=1;x--){
for(int y=1;y<=min(x,siz[v]);y++){
dp[u][x]=min(dp[u][x],dp[u][x-y]+dp[v][y]+w*(k-y)*y);
}
}
}
}
int main()
{
int T,CASE=0;
cin>>T;
while(T--){
scanf("%d%d",&n,&k);
for(int i=0;i<=n;i++)g[i].clear();
mem(in,0);
mem(siz,0);
for(int i=1;i<n;i++){
int u,v;
ll w;
scanf("%d%d%lld",&u,&v,&w);
in[u]++;
in[v]++;
g[u].push_back((node){v,w});
g[v].push_back((node){u,w});
}
int rt=1;
for(int i=1;i<=n;i++){
if(in[i]>1){
rt=i;
break;
}
}
for(int i=1;i<=n;i++){
dp[i][0]=0;
for(int j=1;j<=k;j++){
dp[i][j]=INF;
}
}
dfs(rt,-1);
printf("Case #%d: ",++CASE);
printf("%lld
",dp[rt][k]);
}
}