树型DP不同于普通的的DP之处在于：通过递归找出儿子的信息，在回溯的过程中DP，计算结果(似乎很像记忆化搜索。。。。。。)然后处理相关信息，回答询问》》》》》》》经典应用：点分治中求重心，树链剖分中求重儿子，等等。。。。。。。。。

给大家几道水题》》》》

http://poj.org/problem?id=2342

http://oj.changjun.com.cn/problem/detail/pid/1976

http://oj.changjun.com.cn/problem/detail/pid/1634

http://oj.changjun.com.cn/problem/detail/pid/2171

第一题原码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define MAXX 6000#define INF -99999999using namespace std;struct data{  int nxt,to;}edge[MAXX*2+1];int dp[MAXX+1][2];//1选,0不选int head[MAXX+1],tot,ans,n;bool vis[MAXX+1];void add(int from,int too){edge[++tot].nxt=head[from];head[from]=tot;edge[tot].to=too;}void dfs(int num){  for(int i=head[num];i;i=edge[i].nxt){      int too=edge[i].to;      dfs(too);      dp[num][0]+=max(dp[too][0],dp[too][1]);      dp[num][1]+=dp[too][0];  }}int main(){  /* freopen("1.in","r",stdin);  freopen("1.out","w",stdout);*/  while(scanf("%d",&n)!=EOF){    memset(head,0,sizeof(head));    memset(vis,false,sizeof(vis));    for(int i=1;i<=n;++i)dp[i][0]=0;    tot=0;    for(int i=1;i<=n;++i)scanf("%d",&dp[i][1]);    int a,b;while(scanf("%d%d",&a,&b)&&a!=0&&b!=0)add(b,a),vis[a]=true;    for(int i=1;i<=n;++i)if(!vis[i]){dfs(i),printf("%d\n",max(dp[i][0],dp[i][1]));break;}  }  return 0;}