一次AC。

考虑当m>2时，当大头吃掉k个果子之后，小头只需要交叉着去吃就绝对不会有“难受值”；m==2时的情况需要考虑到。此时问题转化为求大头吃掉k个果子的最小难受值，具体做法为动态规划。

《算法艺术与信息学竞赛》上出了点错。

将树用“左儿子右兄弟”表示法表示。类似“重建道路”，考虑定义f[i][j]表示以i为根的树上，取j个果子的最小难受值，但是这样的话难受值无法计算出来，所以再加一维：定义f[i][j][k]表示以i为根的树上，取j个果子的最小难受值，k==1表示i的父亲被大头吃，k==0表示i的父亲被小头吃。

所以有以下状态转移方程：

x1=tree[i].l；x2=tree[i].r；

f[i][j][k]=min{ f[x1][jj][1]+f[x2][j-jj-1][k]+d(1,k)*w[father[i]][i]，// (*1)

                     f[x1][jj][0]+f[x2][j-jj][k]+d(0,k)*w[father[i]][i] }；// (*2)

其中d(i,j)=1,(i==1&&j==1)||(i==0&&j==0&&m==2)；else d(i,j)=0;

(*2)可以决策的条件是i不是根结点，因为根结点必被大头吃掉。

状态转移方程中jj的取值容易推出，要考虑几种情况，不再细述。

在进行treedp之前，要先计算出以各个结点为根的树的结点数目。

以下是我的代码：

#include<stdio.h>
#define maxv 301
#define maxint 200000000
typedef struct NODE
{
    long x,l,r;
}node;
long m,n,k,root,father[maxv]={0},w[maxv][maxv]={0};
long f[maxv][maxv][2],num[maxv]={0},ans;
node tree[maxv];
void ins(long fa,long son)
{
    long p;
    if(tree[fa].l==0)
      tree[fa].l=son;
    else
    {
       p=tree[fa].l;
       while(tree[p].r!=0)
         p=tree[p].r;
       tree[p].r=son;
    }
}
void count(long node)
{
    long x1,x2;
    if(node==0) return;
    num[node]=1;
    x1=tree[node].l;
    count(x1);
    num[node]+=num[x1];
    x2=tree[node].r;
    count(x2);
    num[node]+=num[x2];
}
void init()
{
    long i,j,fa,son,weight;
    scanf("%ld%ld%ld",&n,&m,&k);// N个顶点 M个头 吃掉K个 
    for(i=1;i<=n;i++)
    {
       tree[i].x=i;
       tree[i].l=tree[i].r=0;
    }
    for(i=1;i<=n-1;i++)
    {
       scanf("%ld%ld%ld",&fa,&son,&weight);
       ins(fa,son);
       father[son]=fa;
       w[fa][son]=weight;
    }// Build a Tree
    // Read In
    for(i=1;i<=n;i++)
      if(father[i]==0)
      {root=i;break;}// Find the Root
    for(i=0;i<=n;i++)
      for(j=0;j<=n;j++)
      {
         f[i][j][0]=-1;
         f[i][j][1]=-1;
      }
    count(root);
}
long d(long i,long j)
{
    if((i==0&&j==0&&m==2)||(i==1&&j==1)) return 1;
    return 0;
}
long dp(long node,long nn,long kk)
{
    if(f[node][nn][kk]!=-1)
      return f[node][nn][kk];
    if(node==0) return 0;
    long i,x1,x2,t;
    f[node][nn][kk]=maxint;
    x1=tree[node].l;
    x2=tree[node].r;
    for(i=0;i<=num[x1];i++)
    {
       if(i>=nn-num[x2]-1&&i<=nn-1)
       {
          t=dp(x1,i,1)+dp(x2,nn-i-1,kk)+d(1,kk)*w[father[node]][node];
          if(t<f[node][nn][kk]) f[node][nn][kk]=t;
       }
       if(i>=nn-num[x2]&&i<=nn&&node!=root)// 只有此结点不是根节点才有可能不被大头吃掉 
       {
          t=dp(x1,i,0)+dp(x2,nn-i,kk)+d(0,kk)*w[father[node]][node];
          if(t<f[node][nn][kk]) f[node][nn][kk]=t;
       }
    }
    return f[node][nn][kk];
}
void write()
{
    printf("%ld\n",ans);
}
int main()
{
    init();
    if(n>=k+m-1)
      ans=dp(root,k,0);
    else ans=-1;
    write();
return 0;
}