很久很久以前，有一个叫做杰哥的骑士. 他生活在一个小王国里. 这个王国由n座城市组成，这n座城市通过n-1条道路相连(意味着这个王国是一棵树结构). 由于杰哥打倒了大魔王，并且从魔王手中救出了公主，国王决定奖励他. 国王决定把公主嫁给杰哥，并且送出恰好K座城市，作为公主的嫁妆. 那么问题来了. 杰哥在和大魔王对♂战的时候，膝盖中了一剑，因此杰哥希望他的K座城市离得越近越好. 这就是说，杰哥希望他的K座城市的期望距离越小越好. 期望距离是这样定义的：首先，从杰哥的K座城市中随机选出一个点u，然后，再从杰哥的K座城市中随机选出一个点v，期望距离就是所有这样u和v的距离的平均值.(注意u可以等于v,此时u和v的距离为0). 请你决定这K座城市，使得杰哥尽量高兴. 你只需要输出最小的期望距离.
第一行是一个整数T，表示测试数据的数量. 对于每组测试数据，第一行包含两个整数n和K，表示城市的数量，以及作为奖励的城市数量. 接下来有n-1行，每行三个整数a,b,c，表示有一条长度为c的道路连接城市a和城市b. 数据范围 1 <= T <= 100 1 <= K <= min(50,n) 1 <= n <= 2000 1 <= a,b <= n 0 <= c <= 100000
对于每组数据，输出一行包含一个整数，表示最小的期望距离乘以K2.
1 2 2 1 2 1
2
dp[i][j]表示 以i为根选j个点的子树的最小值
注意初始化 dp[i][0]=dp[i][1]=0;
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<vector>
#define INF 1<<30
using namespace std;
vector<int> e[2005],w[2005];
long long dp[2005][55],ret[2005];
int n,k;
void dfs(int u,int father)
{
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(v==father)
continue;
dfs(v,u);
for(int j=0;j<=k;j++)
ret[j]=dp[u][j];
for(int j=k;j>=0;j--)
{
for(int t=0;t<=j;t++)
ret[j]=min(ret[j],dp[u][t]+dp[v][j-t]+(j-t)*(k-j+t)*w[u][i]*2);
}
for(int j=0;j<=k;j++)
dp[u][j]=ret[j];
}
}
int main()
{
int tt;
scanf("%d",&tt);
while(tt--)
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
e[i].clear(),w[i].clear();
for(int i=1;i<n;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
e[x].push_back(y);
e[y].push_back(x);
w[x].push_back(z);
w[y].push_back(z);
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=k;j++)
{
dp[i][j]=INF;
if(j<=1)
dp[i][j]=0;
}
}
dfs(1,-1);
printf("%I64d\n",dp[1][k]);
}
return 0;
}
原文：http://www.cnblogs.com/water-full/p/4509550.html