我们通常采用递归的方式实现树形dp。
对于每个节点，先递归在它的每个子节点上进行dp，在回溯时，从子节点向根节点进行状态转移。
顺序一般为从叶子结点到根节点递推。
题目：
一. P1352 没有上司的舞会
以子树的根作为dp状态的第一维。容易发现，每个员工是否参加至于他的上司是否参加有关。
不妨设
1. f[x,0] 表示从以 x 为根的子树中选员工参会，而且不选 x 的最大价值。
那么我们得到：x的子节点 s 可以选，也可以不选，那么 f[x,0] 即为子节点选或不选的最大值。
f[x,0]=∑max( f[s,0] , f[s,1] )
2. f[x,1] 表示选 x 的最大价值。
此时发现：f[x,1]只能等于f[s,0]+自己的快乐指数。
f[x,1]=∑f[s,0] + h[x]
于是基本解决了这道题。
#include<bits/stdc++.h> using namespace std; vector<int>son[10010]; int f[10010][2],v[10010],h[10010],n; void dp(int x) { f[x][0]=0; f[x][1]=h[x]; for(int i=0;i<son[x].size();i++) { int y=son[x][i]; dp(y); f[x][0]+=max(f[y][0],f[y][1]); f[x][1]+=f[y][0]; } } //注意:需要先找到总上司。 int main() { cin>>n; for(int i=1;i<=n;i++) cin>>h[i]; for(int i=1;i<n;i++) { int x,y; cin>>x>>y; v[x]=1; son[y].push_back(x); } int u; for(int i=1;i<=n;i++) if(!v[i]) u=i; dp(u); cout<<max(f[u][0],f[u][1]); return 0; }