一次AC。

考慮當(dāng)m>2時，當(dāng)大頭吃掉k個果子之后，小頭只需要交叉著去吃就絕對不會有“難受值”；m==2時的情況需要考慮到。此時問題轉(zhuǎn)化為求大頭吃掉k個果子的最小難受值，具體做法為動態(tài)規(guī)劃。

《算法藝術(shù)與信息學(xué)競賽》上出了點錯。

將樹用“左兒子右兄弟”表示法表示。類似“重建道路”，考慮定義f[i][j]表示以i為根的樹上，取j個果子的最小難受值，但是這樣的話難受值無法計算出來，所以再加一維：定義f[i][j][k]表示以i為根的樹上，取j個果子的最小難受值，k==1表示i的父親被大頭吃，k==0表示i的父親被小頭吃。

所以有以下狀態(tài)轉(zhuǎn)移方程：

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不是根結(jié)點，因為根結(jié)點必被大頭吃掉。

狀態(tài)轉(zhuǎn)移方程中jj的取值容易推出，要考慮幾種情況，不再細(xì)述。

在進(jìn)行treedp之前，要先計算出以各個結(jié)點為根的樹的結(jié)點數(shù)目。

以下是我的代碼：

#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)// 只有此結(jié)點不是根節(jié)點才有可能不被大頭吃掉 
       {
          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;
}