不知怎么，这么一道简单的TreeDP弄得我这么狼狈。。。
关于这道题，网上有两种解法，一种是双DP，过程叫清楚，也适合于对于TreeDP不是太了解或者自由树转有根树理解不太透彻的人来做，抑或对背包问题了解的很牛的人，过双DP也很简单。。其实双DP也很具有启发意义，是很精巧的算法。。。但是个人认为第二种算法更体现了TreeDP的精髓。。
这儿介绍一下第二种方法

先把自由树转化成有根树（直接转成孩子兄弟表示法），网上我找到的唯一一个用这种方法做的人，在树的转化这个环节用了100行（Orz，膜拜），其实一个遍历就可以了。孩子兄弟表示法到处都有教程，这儿就不多赘述）

void Zh(int p)
{
  f[p]=1;
  for(int i=0;i<d[p];i++)
    if (!f[next[p][i]])      
      {
      bro[next[p][i]]=son[p];
      son[p]=next[p][i];
      Zh(next[p][i]);                       
      }
}

然后直接TreeDP
用maxt[0][p][m]表示p的右边兄弟和下面儿子（这个有点XX吧，但是相信大家能理解）消耗m步还要回起点p，最多能吃的个数。。
用maxt[1][p][m]表示p的右边兄弟和下面儿子，消耗m步不需回起点p，最多能吃的个数。。

对于每一个节点p，先考虑无视p的情况（p取不到），直接把“走路的权利”传给自己右边兄弟的情况。
接下来我们考虑的情况，p一定能取道。
分“只往下扩展孩子”和“只往右扩展兄弟”两种情况。
最后，考虑既扩展孩子又扩展兄弟的情况。。。

其中最复杂的就算是“走路的权利”的问题了。。。
我们分maxt[0]和maxt[1]两种情况讨论

maxt[0]时，一定要回到原点，那么很简单，扩展孩子和扩展右边兄弟的时候，“走路的权利”都要-2（想想为什么？）

maxt[0]时，不需要回到原点，那么扩展右边兄弟的时候，“走路的权利”-2，而扩展孩子的时候，只需要-1（想想为什么？）

这两个问题，如果你画一下图，也许能很快明白。。。。

如果你全部明白了，恭喜你，这道题AC将会在30分钟内诞生。。。

祝你成功！


PS:
    以下是小弟的代码，为了看的清楚，我把程序写的简洁，但也损失了很多时间，当然对于p==0和m==0的时候的剪枝，其实很可以做的更好。
     祝大家AC愉快！

Source Code

Problem: 2486  User: forsona 
Memory: 620K  Time: 422MS 
Language: G++  Result: Accepted 

Source Code 
#include"iostream"
#define INF -99999999
using namespace std;
int d[110],next[110][110],son[110],bro[110],c[110],f[110],n,k,maxt[2][110][210],r;
void Zh(int p)
{
  f[p]=1;
  for(int i=0;i<d[p];i++)
    if (!f[next[p][i]])      
      {
      bro[next[p][i]]=son[p];
      son[p]=next[p][i];
      Zh(next[p][i]);                       
      }
  memset(maxt,-1,sizeof(maxt));      
}
void Inp(void)
{
  int i,j,k;
  memset(d,0,sizeof(d));
  for(i=1;i<=n;i++)
    scanf("%d",&c[i]);
  for(i=0;i<n-1;i++)
    {
    scanf("%d%d",&j,&k);
    next[j][d[j]++]=k;
    next[k][d[k]++]=j;
    } 
  memset(bro,0,sizeof(bro));
  memset(son,0,sizeof(son));    
  memset(f,0,sizeof(f));  
  Zh(1);
  
}
int Loop(int b,int p,int m)                          
 //b==0  back to root     b==1  no need to root
{
  int i,mt;
  if (maxt[b][p][m]!=-1)
    return maxt[b][p][m];
  if (!p)
    return maxt[b][p][m]=0;  
  if (m==0)
    return maxt[b][p][m]=max(Loop(b,bro[p],m),c[p]);  
  if (b==0)
    {
    mt=Loop(0,bro[p],m);
    if (m>=2)
      {
      mt=max(mt,c[p]+Loop(0,bro[p],m-2));
      mt=max(mt,c[p]+Loop(0,son[p],m-2));
      }
    for(i=0;i<=m-4;i++)  
      mt=max(mt,Loop(0,bro[p],i)+Loop(0,son[p],m-4-i)+c[p]);
    return maxt[b][p][m]=mt;        
    }
  else
    {
    mt=Loop(1,bro[p],m);       
    mt=max(mt,c[p]+Loop(1,son[p],m-1));
    if (m>=2)
      mt=max(mt,c[p]+Loop(1,bro[p],m-2));
    for(i=0;i<=m-4;i++)
      mt=max(mt,Loop(1,bro[p],i)+Loop(0,son[p],m-4-i)+c[p]); 
    for(i=0;i<=m-3;i++)         
      mt=max(mt,Loop(0,bro[p],i)+Loop(1,son[p],m-3-i)+c[p]);          
    return maxt[b][p][m]=mt;       
    }  
}
int main()
{
  while(scanf("%d%d",&n,&k)!=EOF)
    {
    Inp();
    r=Loop(1,1,k);
    printf("%d\n",r);                             
    }
  return 0;  
} 

• 赞一个~ (3359) gfedcba 2009-03-05 22:50:49
• Re:为了这道题贡献了32个WA啊。。。。给大家一点提示 (78) forsona 2009-03-07 21:47:51
• Re:赞一个...话说不懂转化成二叉树有多大好处... (3359) wzc1989 2009-10-14 21:06:31
• 有一点表示不明白，那位高人帮忙指点一下 (154) 090609103 2011-11-02 18:29:42
  • Re:有一点表示不明白，那位高人帮忙指点一下 (217) hzoi 2014-03-03 17:17:52
    • Re:有一点表示不明白，那位高人帮忙指点一下 (55) hzoi 2014-03-03 17:18:17
• 怒赞！ (6) fzfzfz 2014-09-26 16:13:43