题意：给你一棵 \(n\) 个节点的树找出 \(k\) 个不同的点 \(a_1,a_2,\cdots,a_k\)，
使得 \(\sum\limits_{i=1}^{k-1} dis(a_i,a_{i+1})\) 最小。
首先有个容易想到的性质：这 \(k\) 个点一定是相邻的，那么选 \(k\) 个点可以看成选 \(k-1\) 条相连的边。
但关键是我们不是要算一个环的长度，而是一条路径的长度，也就是说不用算从终点再走回到起点的距离，事情就变得麻烦起来。
用树形 dp 求解：设 \(dp(i,j,0/1/2)\) 表示在 \(i\) 子树中，选出 \(j\) 条边的方案数。
其中第 \(3\) 维是 \(0\) 表示这条路径的两个端点都在根节点 \(i\) 上；第 \(3\) 维是 \(1\) 表示这条路径的两个端点一个在根节点 \(i\) 上，另一个在 \(i\) 的子树内；第 \(3\) 维是 \(2\) 表示这条路径的两个端点都在 \(i\) 的子树内，但是这条路径经过 \(i\)。
那么答案就是 \(\min\limits_{i=1}^n dp(i,k-1,0/1)\)。
然后转移也比较明显，主要是这个时间复杂度的证明。
证法一：
设对于某一个点 \(u\)，以 \(u\) 为根的子树大小为 \(s\)，\(u\) 的儿子的子树大小分别为 \(s_1,s_2,\cdots,s_m\)。
那么在 \(u\) 节点的时间是：
然后每两层相消，最后总时间复杂度就是根所代表的子树的大小的平方，即 \(O(n^2)\)。
证法二：
dp 的实质可以看做枚举树中的点对 \((u,v)\)，然后当且仅当存在某一个 \(root\)，使得 \(u\) 和 \(v\) 分别在 \(root\) 的两个儿子的子树中。显然，对于每一个点对 \((u,v)\)，有且仅有一个 \(root=\operatorname{lca}(u,v)\)。所以总时间复杂度是 \(O(n^2)\)。
代码如下：
#include<bits/stdc++.h>
#define N 3010
#define ll long long
#define INF 0x7fffffff
using namespace std;
int n,k,size[N];
int cnt,head[N],nxt[N<<1],to[N<<1];
ll w[N<<1],dp[N][N][3];
//dp[0]：根进根出
//dp[1]：根进子树内出
//dp[2]：子树内进子树内出（经过根）
void adde(int u,int v,ll wi)
{
to[++cnt]=v;
w[cnt]=wi;
nxt[cnt]=head[u];
head[u]=cnt;
}
void dfs(int u,int fa)
{
size[u]=1;
dp[u][0][0]=dp[u][0][1]=0;
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(v==fa) continue;
dfs(v,u);
for(int j=size[u]-1;j>=0;j--)
{
for(int k=size[v]-1;k>=0;k--)
{
dp[u][j+k+1][0]=min(dp[u][j+k+1][0],dp[u][j][0]+dp[v][k][0]+w[i]*2);
dp[u][j+k+1][1]=min(dp[u][j+k+1][1],min(dp[u][j][0]+dp[v][k][1]+w[i],dp[u][j][1]+dp[v][k][0]+w[i]*2));
dp[u][j+k+1][2]=min(dp[u][j+k+1][2],min(dp[u][j][0]+dp[v][k][2]+w[i]*2,min(dp[u][j][1]+dp[v][k][1]+w[i],dp[u][j][2]+dp[v][k][0]+w[i]*2)));
}
}
size[u]+=size[v];
}
}
int main()
{
memset(dp,127,sizeof(dp));
scanf("%d%d",&n,&k);
for(int i=1;i<n;i++)
{
int u,v;ll w;
scanf("%d%d%lld",&u,&v,&w);
adde(u,v,w),adde(v,u,w);
}
dfs(1,0);
ll ans=INF;
for(int i=1;i<=n;i++)
ans=min(ans,min(dp[i][k-1][1],dp[i][k-1][2]));
printf("%lld\n",ans);
return 0;
}
原文地址：http://www.cnblogs.com/ez-lcw/p/16837307.html
