树形dp的模板是在做题中总结出来的
POJ 2342 Anniversary party_边
树形DP满足自下而上，在dfs处通过递归实现
与scnuoj不一样，这题需要找根节点
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define maxi 6010
using namespace std;
int n,dp[maxi][2],book[maxi];
vector<int> G[maxi];
void dfs(int u){
for(int i=0;i<G[u].size();i++){
int to=G[u][i];
dfs(to);
dp[u][1]+=dp[to][0];
dp[u][0]+=max(dp[to][0],dp[to][1]);
}
}
int main()
{
freopen("data.txt","r",stdin);
cin>>n;
int a,b;
for(int i=1;i<=n;i++){
cin>>dp[i][1];
}
for(int i=1;i<n;i++){
cin>>a>>b;
G[b].push_back(a);
book[a]=1;//寻找根节点
}
cin>>a>>b;
int root;
for(int i=1;i<=n;i++){
if(!book[i]){
root=i;
break;
}
}
dfs(root);
cout<<max(dp[root][0],dp[root][1]);
return 0;
}
洛谷 P2016 战略游戏_边
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define maxi 6010
using namespace std;
int n,dp[maxi][2],book[maxi];
vector<int> G[maxi];
void dfs(int u){
dp[u][1]=1;
for(int i=0;i<G[u].size();i++){
int to=G[u][i];
dfs(to);
dp[u][0]+=dp[to][1];
dp[u][1]+=min(dp[to][0],dp[to][1]);
}
}
int main()
{
freopen("data.txt","r",stdin);
cin>>n;
int a,b,c;
int root;
for(int i=1;i<=n;i++){
cin>>a>>b;
for(int j=0;j<b;j++){
cin>>c;
G[a].push_back(c);
book[c]=1;
}
}
//i从0开始，自行看题
for(int i=0;i<n;i++){
if(!book[i]){
root=i;
break;
}
}
dfs(root);
cout<<min(dp[root][0],dp[root][1]);
return 0;
}
POJ 3659 Cell Phone Network_结点
//#include <bits/stdc++.h>
#define maxi 100010
#define INF 99999999
using namespace std;
//dp[i][0] 自己不选，选父亲
//dp[i][1] 自己不选，选儿子
//dp[i][2] 选自己
vector<int> G[maxi];
int dp[maxi][3];
void dfs(int u,int f){
dp[u][0]=0;
dp[u][1]=0;
dp[u][2]=1;
if(G[u].size()==1&&G[u][0]==f){
//到底了
dp[u][1]=INF;
return ;
}
int flag=0,minn=INF,son=0,v;
for(int i=0;i<G[u].size();i++){
v=G[u][i];
//如果是最后一个结点，则不算
if(v==f)
continue;
dfs(v,u);
//u是自己，v是子节点
dp[u][2]+=min(dp[v][0],min(dp[v][1],dp[v][2]));
dp[u][0]+=min(dp[v][1],dp[v][2]);
if(dp[v][1]<dp[v][2]){
dp[u][1]+=dp[v][1];
if(minn>dp[v][2]){
minn=dp[v][2];
son=dp[v][1];
}
}
else{
flag=1;
dp[u][1]+=dp[v][2];
}
}
if(!flag)
dp[u][1]+=minn-son;
}
int main(){
int n;
cin>>n;
int a,b;
for(int i=1;i<n;i++){
cin>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
dfs(1,-1);
cout<<min(dp[1][1],dp[1][2])<<endl;
return 0;
}
ZOJ 3201 Tree of Tree_树上DP
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
//#include <bits/stdc++.h>
#define maxi 110
#define INF 99999999
using namespace std;
vector<int> G[maxi];
int dp[maxi][maxi],w[maxi],k,vis[maxi];
void dfs(int u,int f){
dp[u][1]=w[u];
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
//如果是最后一个结点，则不算
if(v==f)
continue;
dfs(v,u);
//u是自己，v是子节点
for(int j=k;j>=1;j--)
for(int l=1;l<=j;l++)
dp[u][j]=max(dp[u][j],dp[u][l]+dp[v][j-l]);
}
}
int main(){
// freopen("data","r",stdin);
int n;
while(scanf("%d%d",&n,&k)!=EOF){
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++){
G[i].clear();
cin>>w[i];
}
int a,b;
for(int i=0;i<n-1;i++){
cin>>a>>b;
G[a].push_back(b);
G[b].push_back(a);
}
dfs(0,-1);
int res=0;
for(int i=0;i<n;i++)
res=max(dp[i][k],res);
cout<<res<<endl;
}
return 0;
}
洛谷 P2014 选课_线上DP
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
//#include <bits/stdc++.h>
#define maxi 350
#define INF 99999999
using namespace std;
vector<int> G[maxi];
int dp[maxi][maxi],k,n,m,w[maxi];
void dfs(int u){
for(int i=1;i<m;i++)
dp[u][i]=w[u];
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
dfs(v);
//增加一个虚构结点，所以是m+1
for(int j=m;j>=1;j--)
for(int l=1;l<=j;l++)
dp[u][j]=max(dp[u][j],dp[u][l]+dp[v][j-l]);
}
}
int main(){
// freopen("data","r",stdin);
scanf("%d%d",&n,&m);
int a,b;
for(int i=1;i<=n;i++){
cin>>a>>w[i];
G[a].push_back(i);
}
dfs(0);
cout<<dp[0][m]<<endl;
return 0;
}
