树是一个由 \(n\) 个节点，\(n-1\) 条边组成的联通图，图上没有环，其每一条边都是割边。

在树上设计动态规划算法时，一般以节点从深到浅的顺序作为 DP 的阶段。大多数时候，采用递归的方式实现树形动态规划。

对于每一个节点 \(x\)，先对它的每一个子节点进行 DP，回溯时从子节点向 \(x\) 进行状态转移。

例题 \(1\) P1352

以节点编号作为 DP 状态的第 \(1\) 维，一名职员是否愿意参加，只与他的直接上司是否参加有关。我们定义 \(f[x,0]\) 表示从以 \(x\) 为根的子树中邀请一部分职员参会，且 \(x\) 不参加舞会时，快乐总和的最大值，\(f[x,1]\) 则代表 \(x\) 参加舞会时快乐总和的最大值。

那么状态转移方程为：

如果是叶子结点，那么：

设根节点为 \(root\)，那么答案为 \(max(f[root,0],f[root.1])\)。

#include<bits/stdc++.h>
using namespace std;
int n,r[100009],f[100009][2];
vector<int> to[100009];
void dp(int x,int fa){
	for(int i=0;i<to[x].size();i++){
		if(to[x][i]==fa)  continue;
		dp(to[x][i],x);
	}
	for(int i=0;i<to[x].size();i++){
		f[x][0]+=max(f[to[x][i]][0],f[to[x][i]][1]);
		f[x][1]+=f[to[x][i]][0];
	}
	f[x][1]+=r[x];
	return ;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)  cin>>r[i];
	for(int i=1;i<=n-1;i++){
		int x,y;
		cin>>x>>y;
		to[x].push_back(y);
		to[y].push_back(x);
	}
	dp(1,0);
	cout<<max(f[1][0],f[1][1]);
	return 0;
}

例题 \(2\) P2014

我们定义 \(f[x,t]\) 为以 \(x\) 为根的子树中选修 \(t\) 门课能获得的最大学分。\(son(x)\) 为 \(x\) 的子节点集合，个数 \(p=|son(x)|\)

如果 \(x\) 学习完毕，则可以学习 \(x\) 的子节点，对于每个子节点 \(y_i∈son(x)\)，在以 \(y_i\) 为根的子树中选择 \(C_i\) 门课，则在满足 \(\displaystyle \sum_{y∈son(x)}=t-1\) 的情况下获得尽可能多的学分。

当 \(t=0\) 时，\(f[x,t]= 0\)。

当 \(t>0\) 时，状态转移方程如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,s[1009],f[1009][1009];
vector<int> to[1009];
void dp(int x){
	f[x][0]=0;
	for(int i=0;i<to[x].size();i++){
		int y=to[x][i];
		dp(y);
		for(int t=m;t>=0;t--){
			for(int j=0;j<=t;j++)  f[x][t]=max(f[x][t],f[x][t-j]+f[y][j]);
		}
	}
	if(x!=0){
		for(int t=m;t>0;t--)  f[x][t]=f[x][t-1]+s[x];
	}
	return ;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int ki,si;
		cin>>ki>>si;
		to[ki].push_back(i);
		s[i]=si;
	}
	dp(0);
	cout<<f[0][m]; 
	return 0;
}

例题 \(3\) P4395

题目和气垫车有什么关系

看到题目的第一反应可能是贪心 \(12\) 染色，但可以被菊花图 hack。

进过一系列玄学计算可以算出取值上界大约是 \(\log n +1\)，在本题中是 \(15\)，保险一点取 \(20\)。令 \(f[x,t]\) 表示节点 \(x\) 取 \(t\) 时的最小权值和。

如果 \(x\) 为叶节点，\(f[x,t]=t\)

否则

答案为 \(\min\{ f[1,t] \}\)。

#include<bits/stdc++.h>
using namespace std;
int n,f[10009][29];
vector<int> to[10009];
void dp(int x,int fa){
	for(int i=1;i<=20;i++)  f[x][i]=i;
	for(int i=0;i<to[x].size();i++){
		if(to[x][i]==fa)  continue;
		dp(to[x][i],x);
		for(int j=1;j<=20;j++){
			int minn=0x3f3f3f3f;
			for(int k=1;k<=20;k++){
				if(j==k)  continue;
				minn=min(minn,f[to[x][i]][k]);
			}
			f[x][j]+=minn;
		}
	}
	return ;
}
int main(){
	cin>>n;
	for(int i=1;i<=n-1;i++){
		int x,y;
		cin>>x>>y;
		to[x].push_back(y);
		to[y].push_back(x);
	}
	dp(1,0);
	int ans=0x3f3f3f3f;
	for(int i=1;i<=20;i++)  ans=min(ans,f[1][i]);
	cout<<ans;
	return 0;
}