基本概念

树形DP就是在“树”的数据结构上做动态规划，通过有限次地遍历树，记录相关信息，以求解问题。树形DP有根到叶(常见)和叶到根两个方向，就是将父亲结点的信息向下传递给子结点，或者从子结点向上传递信息给父亲结点。

因为树本身至少就有“子结构”性质（树和子树）；也本身就具有递归性。所以在树上DP其实是其所当然的事，相比线性动态规划来讲，转移方程更直观，更易理解。

例题 HDU 1520

题意

有n个人，接下来n行是n个人的价值，再接下来n行给出l，k，说的是l的上司是k。要求l与k不能同时出现，求最大的结点价值和。

思路

dp[rt][1]+=dp[G[rt][i]][0]; dp[rt][0]+=max(dp[G[rt][i]][1],dp[G[rt][i]][0]); //G[rt][i]为当前根节点可以到达的孩子

此类题目的关键在于建树，建树的方法也有多种： 可以用链式结构，可以用下面代码示例中的二维动态数组（相当于链表） 也可以用链式向前星（优化空间，以我目前的经验是比vector稍快），但没有普通的邻接表好写 有的题目甚至不需要建树，只需边遍历边递推

建好树又有了转移方程，其他的就不怕不怕了

代码示例

#include<bits/stdc++.h> using namespace std; int n; const int maxn=6005; /* struct Edge{ int from,to; }edges[maxn]; */ vector<int> G[maxn]; int value[maxn]; int father[maxn]; int dp[maxn][2]; void dfs(int rt){ if(!G[rt].size()){ dp[rt][1]=value[rt]; dp[rt][0]=0; return ;//边界 } dp[rt][0]=0; dp[rt][1]=value[rt]; for(int i=0;i<G[rt].size();++i){ dfs(G[rt][i]); dp[rt][1]+=dp[G[rt][i]][0]; dp[rt][0]+=max(dp[G[rt][i]][1],dp[G[rt][i]][0]); } return ; } void init() { memset(value,0,sizeof(value)); memset(father,0,sizeof(father)); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;++i){ G[i].clear(); } } int main() { ios::sync_with_stdio(false); while(cin>>n) { init(); for(int i=1;i<=n;++i){ cin>>value[i]; } int u,v; while(cin>>u>>v&&(u+v)) { father[u]=v; G[v].push_back(u); } int root=1; while(father[root]){ root=father[root]; } dfs(root); cout<<max(dp[root][0],dp[root][1])<<endl; } return 0; }