正解：树形dp

思维能力不行，不看题解什么都想不出来= =

首先有一个很显然的结论，选出的k个点一定是连成一片的。

我们要做的就是选出顺次经过k个点的一条路径(边可以重合)，所以我们可以把选点转化为选边。

我们让f[i][j][k=0/1/2]f[i][j][k=0/1/2]表示ii的子树内选了jj条边，包含了kk个路径端点的最小代价。

f[i][j][0]f[i][j][0]代表从ii到子树内的某个节点，再回到ii的最小代价。

f[i][j][1]f[i][j][1]代表从ii子树内的某个节点到ii的最小代价。

f[i][j][2]f[i][j][2]代表从ii子树内的某个节点到ii，再到ii子树内的另一个节点的最小代价。

我们枚举uu的每一个儿子vv，用vv的ff数组更新uu的ff数组。

用f[v][j][0/2]f[v][j][0/2]更新f[u]f[u]时，u−>vu−>v这条边的代价算两次。

用f[v][j][1]f[v][j][1]更新f[u]f[u]时，u−>vu−>v这条边的代价只用算一次。、

由定义很容易理解。

边界：f[u][0][0]=f[u][0][1]=f[u][0][2]=0f[u][0][0]=f[u][0][1]=f[u][0][2]=0。其他初始化为infinf。

代码

#include
    
     #include
     
      #include
      
       using namespace std;const int N=3005;int n,k,u,v,d,cnt,ans=1e9,head[N],siz[N],f[N][N][3],to[N*2],nxt[N*2],dd[N*2];void adde(int u,int v,int d){    to[++cnt]=v;    nxt[cnt]=head[u];    dd[cnt]=d;    head[u]=cnt;}void dfs(int pre,int u){    f[u][0][0]=f[u][0][1]=0;    siz[u]=1;    int v;    for(int i=head[u];i;i=nxt[i]){        v=to[i];        if(v!=pre){            dfs(u,v);            for(int j=siz[u]-1;j>=0;j--){                for(int k=siz[v]-1;k>=0;k--){                    f[u][j+k+1][0]=min(f[u][j+k+1][0],f[u][j][0]+f[v][k][0]+2*dd[i]);                    f[u][j+k+1][1]=min(f[u][j+k+1][1],f[u][j][0]+f[v][k][1]+dd[i]);                    f[u][j+k+1][1]=min(f[u][j+k+1][1],f[u][j][1]+f[v][k][0]+2*dd[i]);                    f[u][j+k+1][2]=min(f[u][j+k+1][2],f[u][j][0]+f[v][k][2]+2*dd[i]);                    f[u][j+k+1][2]=min(f[u][j+k+1][2],f[u][j][1]+f[v][k][1]+dd[i]);                    f[u][j+k+1][2]=min(f[u][j+k+1][2],f[u][j][2]+f[v][k][0]+2*dd[i]);                }            }            siz[u]+=siz[v];        }    }    ans=min(ans,min(f[u][k-1][0],min(f[u][k-1][1],f[u][k-1][2])));}int main(){    scanf("%d%d",&n,&k);    for(int i=1;i