HDOJ The more, The Better 树形DP

算是树形DP的入门题吧。学习了一下人家的代码过的。在网上看了几种版本。果然还是dfs遍历树好啊。树形结构用指针来建的话可以省去很多麻烦。另外这题不能赤裸裸的从叶子节点更新，因为根是可以选择多个叶子的。没用完一个叶子，就必须把相应的父亲节点更新。还不错的题。

#include<iostream>
#include<cstring>
#include<cstdio>
#define MAXN 222
using namespace std;struct node
{int point;node* next;
}edge[MAXN],*ptr[MAXN];int N,M;
int f[MAXN][MAXN];
int value[MAXN];
int edgeNum;
int max( int a,int b ){ return a>b?a:b; }void addEdge( int father,int son )
{node *p=&edge[edgeNum++];p->point=son;p->next=ptr[father];ptr[father]=p;
}void dfs( int cur,int deep )
{node *p=ptr[cur];while( p!=NULL ){for( int i=deep+1;i<=M;i++ )f[p->point][i]=f[cur][i-1]+value[p->point];dfs( p->point,deep+1 );for( int i=deep+1;i<=M;i++ )f[cur][i]=max( f[cur][i],f[p->point][i] );p=p->next;}
}int main()
{while( scanf( "%d %d",&N,&M ),N||M ){M++;memset( f,0,sizeof(f) );memset( value,0,sizeof(value) );memset( ptr,0,sizeof(ptr) );edgeNum=0;int father,val;for( int i=1;i<=N;i++ ){scanf( "%d %d",&father,&val );value[i]=val;addEdge( father,i );}dfs( 0,1 );printf( "%d\n",f[0][M] );}return 0;
}