树形dp就是把操作放在树上。
1. P1352 没有上司的舞会 ——树的最大独立集
题意：上司如果参加酒会，下属就不去了。很容易想到上司和员工之间的关系就是父节点与子节点的关系，用boss[i]来存储i的父节点编号。因为编号是1-n的嘛，我们就初始化boss[]为0,然后遍历知道根节点，显然，没有父节点的那个为根节点(boss[i]==0).
状态定义：dp[i][0]为i不参加时i和他的下属制造的最大欢乐度；
dp[i][0]为i参加时i和他的下属制造的最大欢乐度。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
const int maxn=6e3+10;
int a[maxn];
int n,boss[maxn],dp[maxn][2];
vector<int> E[maxn];void dfs(int x){dp[x][0]=0;dp[x][1]=a[x];for(int i=0;i<E[x].size();i++){int tmp=E[x][i];dfs(tmp);dp[x][0]+=max(dp[tmp][0],dp[tmp][1]); //没取父节点的值，子节点分为取或不取两种情况，取其中值较大的那种情况dp[x][1]+=dp[tmp][0]; //既然去了父节点的值，子节点的值不能取了}
}int main(){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);int L,k;while(~scanf("%d%d",&L,&k)){if(L==0&&k==0) break;boss[L]=k;E[k].push_back(L);}for(int i=1;i<=n;i++){if(boss[i]==0){dfs(i);printf("%d\n",max(dp[i][0],dp[i][1]));break;}}return 0;
}
2.工人的请愿书（Another Crisis UVA - 12186 ） 算法竞赛入门经典 P282
因为要排序，算法的时间复杂度为O(nlogn) 。
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;const int maxn = 100000 + 5;int n, t;
vector<int> sons[maxn];int dp(int u) //dp(u)表示让u给上级发信最少需要多少个工人。工人也就是叶子节点
{if (sons[u].empty()) return 1;vector<int> d;int k = sons[u].size();for (int i = 0; i < k; i++)d.push_back(dp(sons[u][i]));sort(d.begin(), d.end());//int c = (k*t - 1) / 100 + 1; //上取整语句，等价于下边那一句int c=ceil(k*t/100.0);//cout<<"c="<<c<<endl;int ans = 0;for (int i = 0; i < c; i++){ans += d[i];//cout<<"d["<<i<<"]="<<d[i]<<",ans="<<ans<<endl;}return ans;
}int main()
{int temp;while (cin >> n >> t && (n || t)){for (int i = 0; i <= n; i++)sons[i].clear();for (int i = 1; i <= n; i++){cin >> temp;sons[temp].push_back(i);}int ans=dp(0);cout << ans << endl;}return 0;
}
再次写的代码，
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
vector<int> sons[maxn];
int n,t;int dp(int x){if(sons[x].empty()) return 1;int ans=0;int k=sons[x].size();vector<int> w;for(int i=0;i<k;i++){//cout<<"子节点："<<sons[x][i]<<",dp(sons[x][i])="<<dp(sons[x][i])<<endl;w.push_back(dp(sons[x][i]));}/* for(int i=0;i<k;i++){cout<<"w[i]="<<w[i]<<endl;}*/sort(w.begin(),w.end());int c=ceil(k*t/100.0);//cout<<"c="<<c<<endl;for(int i=0;i<c;i++)ans+=w[i];return ans;
}int main(){while(cin>>n>>t){if(n==0&&t==0) break;for(int i=0;i<=n;i++)sons[i].clear();int tmp;for(int i=1;i<=n;i++){cin>>tmp;sons[tmp].push_back(i);}cout<<dp(0)<<endl;;}}