树形dp，是一种建立在树形结构上的dp，因此dfs一般是实现它的通用手段。
是一种很美的动态规划呢。
P1352 没有上司的舞会
在一棵树中，找到若干个互相独立（即互相没有边直接相连）的点，使它们的权值和最大。
我们发现，间隔选择的方法（只选深度为奇数/偶数的点）是不可行的。一个很简单的反例是这棵树是一条链：10 <-> 3 <-> 3 <-> 10，显然选择\(1,4\)才是正确的。
那么我们该怎么做呢？我们可以dfs遍历这棵树，对于一个节点，我们考虑两种选择情况：
- 选当前节点：那么子节点就不能选。当前权值为所有子节点不选状态下的答案和。
- 不选当前节点：那么子节点可以选，也可以不选。当前答案为所有子节点两种状态下的最大值之和。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,happy[6010];
vector<int> ch[6010];
bool b[6010];
int mem[6010][2];
int dfs(int pos,bool is){
if(mem[pos][is]) return mem[pos][is];
int ans=0,len=ch[pos].size();
if(is){//如果上司去，则员工必须不去
for(int i=0;i<len;i++) ans+=dfs(ch[pos][i],0);
ans+=happy[pos]*(happy[pos]>0);
}else{//如果上司不去，则员工有两种选择
for(int i=0;i<len;i++) ans+=max(dfs(ch[pos][i],0),dfs(ch[pos][i],1));
}
return mem[pos][is]=ans;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>happy[i];
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
b[x]=1;
ch[y].push_back(x);
}
for(int i=1;i<=n;i++){
if(!b[i]){
cout<<max(dfs(i,0),dfs(i,1));
break;
}
}
return 0;
}
UVA1292 Strategic game
在一棵树中，找到若干个点，每个点放置\(1\)个士兵，每个士兵可以看守所在点邻接的所有边，现在我们想知道：要看守这棵树的所有边，最少需要多少士兵。
对于每个节点，考虑其选择情况：
- 该节点放士兵：那么子节点可以放，也可以不放。取每个子节点放/不放的最小值求和即可。
- 该节点不放士兵：那么子节点必须全放。取每个子节点放的和即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> G[1510];
int f[1510][2];
bool vis[1510];
void dfs(int pos){
f[pos][1]=1;
for(auto i:G[pos]){
dfs(i);
f[pos][0]+=f[i][1];//如果当前不选，那么子节点必须全选
f[pos][1]+=min(f[i][0],f[i][1]);//如果当前选，则选最小
}
}
int main(){
while(~scanf("%d",&n)){
memset(f,0,sizeof f);
memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++) G[i].clear();
for(int i=1;i<=n;i++){
int pos,m,num;
scanf("%d:(%d)",&pos,&m);
pos++;
for(int j=1;j<=m;j++){
cin>>num;
num++;
G[pos].push_back(num);
vis[num]=1;
}
}
int awa=-1;
for(int i=1;i<=n;i++){
if(!vis[i]){
awa=i;
break;
}
}
dfs(awa);
cout<<min(f[awa][0],f[awa][1])<<endl;
}
return 0;
}
P1122 最大子树和
在一棵树中选择一块联通分量，让其点权和最大。
用\(f[i]\)表示以\(i\)为根节点子树的答案。显然它的值就是子节点答案中，非负答案的和。
最后遍历\(f\)求出最大值即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,v[16010];
vector<int> G[16010];
bool vis[16010];
int f[16010];
void dfs(int pos){
vis[pos]=1;
f[pos]=v[pos];
for(auto i:G[pos]){
if(vis[i]) continue;
dfs(i);
if(f[i]>0) f[pos]+=f[i];
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>v[i];
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1);
int ans=INT_MIN;
for(int i=1;i<=n;i++) ans=max(ans,f[i]);
cout<<ans;
return 0;
}