• 日期: 2026-11-11
  • 标签: 程序员

顾名思义，即在树上进行dp，涵盖普通dp（如例题一、三）、各种背包dp（如例题二、四）等。由于树的特殊递归结构，所以与普通dp不同的是，树形dp一般都是递归进行的。

例题

一、洛谷P1352 没有上司的舞会

题目大意

  有 \(n\) 个职员，编号 \(1-n\)，他们的关系就像一棵树，父亲节点是儿子节点的直接上司。如果一个职员的直接上司来参加舞会了，那么他无论如何也不会来参加舞会。对于每个职员 \(i\) 都有一个快乐指数 \(val[i]\)，求来参加舞会的职员的快乐指数之和的最大值。

设计状态

  设 \(dp[i][0/1]\) 表示以第 \(i\) 个职员为根的子树中快乐指数的最大值，其中 \(dp[i][0]\) 表示第 \(i\) 个职员不来参加舞会时的最大快乐指数，\(dp[i][1]\) 表示第 \(i\) 个职员来参加舞会时的最大快乐指数。

状态转移

  设职员 \(y\) 是职员 \(x\) 的儿子，那么显然有

\[dp[x][1]=dp[y][0] \]

  因为 \(x\) 来参加舞会了，\(y\) 就不能参加舞会。

\[dp[x][0]=max(dp[y][0],dp[y][1]+val[y]) \]

  因为 \(x\) 没来参加舞会，\(y\) 参加不参加都可以。

  初始时 \(dp[x][0]=0\)，\(dp[x][1]=val[x]\)，在 \(dfs\) 返回上一层时记录 \(x\) 的答案。

代码

#include
using namespace std;
typedef long long ll;
const ll maxn=6e3+5;
ll n,u,v,rt,val[maxn],dp[maxn][2],ru[maxn];
vector e[maxn];
void dfs(ll x,ll fa){
	dp[x][0]=0;
	dp[x][1]=val[x];
	for(auto y:e[x]){
		if(y!=fa){
			dfs(y,x);
			dp[x][1]+=dp[y][0];
			dp[x][0]+=max(dp[y][0],dp[y][1]);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n;
	for(ll i=1;i<=n;i++){
		cin>>val[i];
	}
	for(ll i=1;i>u>>v;
		e[v].push_back(u);
		ru[u]++;
	}
	for(ll i=1;i<=n;i++){
		if(ru[i]==0){
			rt=i;
			break;
		}
	}
	dfs(rt,0);
	cout<

二、洛谷P2014 [CTSC1997]选课

题目大意

  有 \(n\) 门课，每门课都有不同的学分，且都有一门或没有直接先修课（若课程 \(a\) 是课程 \(b\) 的先修课，即只有学完课程 \(a\)，才能学习课程 \(b\)）。一个学生要在这些课程中选 \(m\) 门学习，求他最多能获得多少学分。

审题

  根据每门课只有一门或没有先修课的特点，可以联想到有根树中每个点最多只有一个父亲节点的性质；据此，我们可以把课程关系构造为一片森林。为了便于搜索，我们设 \(0\) 号节点为整片森林的根。

设计状态

  设 \(dp[x][i][j]\) 表示以 \(x\) 为根的子树中，已经遍历了 \(x\) 号节点的前 \(i\) 棵子树，并选了 \(j\) 门课程时能获得的最大学分。

状态转移

  设 \(x\) 的儿子个数为 \(sum_x\)，以 \(x\) 为根的子树大小为 \(siz_x\)，那么

\[dp[x][i][j]=\max_{y,k\leq{j},k\leq{siz_y}}(dp[x][i][j],dp[x][i-1][j-k]+dp[y][sum_y][k]) \]

  不难发现，\(dp\) 数组的第二维类似背包 \(dp\)，可以用滚动数组省略掉，此时枚举 \(j\) 时要倒序枚举。

代码

#include
using namespace std;
typedef long long ll;
ll n,m,k,s[305],dp[305][305];
vector e[305];
void dfs(ll x){
	for(auto y:e[x]){
		dfs(y);
		for(ll t=m;t>=0;t--){
			for(ll j=0;j<=t;j++){
				dp[x][t]=max(dp[x][t],dp[x][t-j]+dp[y][j]);
			}
		}
	}
	if(x!=0){
		for(ll t=m;t>=1;t--){
			dp[x][t]=dp[x][t-1]+s[x]; 
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m;
	for(ll i=1;i<=n;i++){
		cin>>k>>s[i];
		e[k].push_back(i);
	}
	dfs(0);
	cout<

三、洛谷P3574 [POI 2014]FAR-FarmCraft

题目大意

  有 \(n\) 个节点、\(n-1\) 条边，构成一棵以 \(1\) 为根的树。从根节点开始遍历整棵树，并记录下遍历到每个节点的时间；同时每个节点又有一个自己的倒计时，当遍历到它时就开始计时。我们需要求出所有节点中倒计时结束最慢的那一个的结束时间，并使其最小化，即最小化「节点权重与到达时间之和」的最大值。

设计状态

  设 \(dp[x]\) 表示遍历完以 \(x\) 为根的子树后，该子树内所有节点倒计时结束时间的最大值；\(siz[x]\) 表示在遍历 \(x\) 的子树之前，已经遍历过的所有子树的大小之和再 \(\ast 2\)，即在遍历完整个子树后 \(siz[x]\) 会更新为以 \(x\) 为根的子树的大小 \(\ast 2\)。

状态转移

  对于节点 \(x\) 的子树 \(y\)，可得：

\[dp[x]=max(dp[x],dp[y]+siz[x]+1) \]

  可以发现，\(dp[x]\) 最终的大小与遍历子树的顺序有关，因此需要对遍历子树的顺序进行排序。

  设节点 \(x\) 的两棵子树为 \(y\)、\(z\)。

  假设先遍历子树 \(y\) 再遍历子树 \(z\)，那么

\[dp[x]=max(dp[x],siz[x]+max(dp[y],dp[z]+siz[y]+2)+1) \]

  若交换遍历顺序，先遍历子树 \(z\) 再遍历子树 \(y\)，那么

\[dp[x]=max(dp[x],siz[x]+max(dp[z],dp[y]+siz[z]+2)+1) \]

  再假设交换后的方案比交换前的更优，即

\[max(dp[x],siz[x]+max(dp[y],dp[z]+siz[y]+2)+1)\\ <\\ max(dp[x],siz[x]+max(dp[z],dp[y]+siz[z]+2)+1) \]

  化简可得：

\[max(dp[y],dp[z]+siz[y]+2)\\ <\\ max(dp[z],dp[y]+siz[z]+2) \]

  又因为：

\[dp[y]

  所以：

\[dp[y]+siz[z]

  所以最终根据：

\[dp[y]-siz[y]>dp[z]-siz[z] \]

  据此排序即可。

代码

#include
using namespace std;
typedef long long ll;
const ll maxn=5e5+5;
ll n,val[maxn],dp[maxn],siz[maxn];
vector e[maxn];
bool cmp(ll y,ll z){
	return dp[y]-siz[y]>dp[z]-siz[z];
}
void dfs(ll x,ll fa){
    if(x!=1){
        dp[x]=val[x];
    }
    if(!e[x].empty()){
        for(auto y:e[x]){
    		if(y!=fa){
    			dfs(y,x);
    		}
    	}
    	sort(e[x].begin(),e[x].end(),cmp);
    	for(auto y:e[x]){
            if(y!=fa){
                dp[x]=max(dp[x],dp[y]+siz[x]+1);
    		    siz[x]+=siz[y]+2;
            }
    	}
    }
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n;
	for(ll i=1;i<=n;i++){
		cin>>val[i];
	}
	for(ll i=1;i>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,0);
	cout<

四、洛谷P4516 [JSOI2018]潜入行动

题目大意

  给定一棵 \(n\) 个点、\(n-1\) 条边的无向树，在节点 \(u\) 上安装监听设备后，对于每一条边 \((u,v)\)，节点 \(v\) 都会被监听。需要注意的是，放置在节点 \(u\) 的监听设备并不监听 \(u\) 本身。现在一共有 \(k\) 个监听设备，求有多少种不同的放置方案（每个节点至多只能安装一个监听设备，且监听设备必须全部用完），能够使得所有节点都被监听？

设计状态

  设 \(dp[x][i+j][0/1][0/1]\) 表示以 \(x\) 号节点为根的子树已经放置了 \(i+j\) 个监听设备、\(x\) 号节点放没放、\(x\) 号节点能不能被其子节点监听到的方案数，其中 \(i\) 是以 \(x\) 为根的子树中已经遍历的所有节点上放置的监听设备数，\(j\) 是以当前 \(x\) 的孩子为根的子树上放置的监听设备数。

  设 \(siz[x]\) 表示到目前为止已经遍历的以 \(x\) 为根的子树的大小，\(siz[x]\) 在遍历完以 \(x\) 为根的子树后就是这棵子树的完整大小。

状态转移

  这里的状态转移比较复杂，类似背包，一共有四个状态，分别对应：\(dp[x][i+j][0][0]\)、\(dp[x][i+j][0][1]\)、\(dp[x][i+j][1][0]\) 和 \(dp[x][i+j][1][1]\)。

  首先初始每个点的 \(dp[x][0][0][0]\)、\(dp[x][1][1][0]\) 都为 \(1\)，即以 \(x\) 为根的子树没装监听设备，或装了一个（在 \(x\) 节点装的，所以 \(x\) 不能被监听到）的方案数都是 \(1\)。

  下面设 \(x\) 的子节点为 \(y\)。

  1.对于 \(dp[x][i+j][0][0]\)，由于 \(x\) 既没放监听设备，又没有被其子节点监听，所以节点 \(y\) 一定没放监听设备，且必须已被监听，即

\[dp[x][i+j][0][0]=\sum dp[x][i][0][0]\ast dp[y][j][0][1] \]

  2.对于 \(dp[x][i+j][0][1]\)，\(x\) 被监听了但没放监听设备，要分两种情况：

    ①对于 \(dp[x][i][0][0]\)，\(x\) 还没被已遍历过的子节点监听，那么监听 \(x\) 的任务就交给了 \(y\)，而 \(y\) 有没有被监听无所谓；

    ②对于 \(dp[x][i][0][1]\)，\(x\) 已经被其他子节点监听了，所以 \(y\) 放不放都无所谓，但要保证 \(y\) 是被监听的；

  即

\[dp[x][i+j][0][1]=\sum (dp[x][i][0][1]\ast (dp[y][j][0][1]+dp[y][j][1][1])+dp[x][i][0][0]\ast dp[y][j][1][1]) \]

  3.对于 \(dp[x][i+j][1][0]\)，\(x\) 没被其子节点监听，但放了监听设备，所以 \(y\) 有没有被监听无所谓，但一定放了监听设备，即

\[dp[x][i+j][1][0]=\sum dp[x][i][1][0]\ast (dp[y][j][1][0]+dp[y][j][1][1]) \]

  4.对于 \(dp[x][i+j][1][1]\)，\(x\) 放了监听设备且被其子节点监听了，这时候也要分两种情况：

    ①对于 \(dp[x][i][1][0]\)，\(x\) 还没被已遍历过的子节点监听，那么监听 \(x\) 的任务就交给了 \(y\)，而 \(y\) 有没有被监听无所谓；

    ②对于 \(dp[x][i][1][1]\)，\(x\) 已被监听，那么 \(y\) 有没有放监听设备，有没有被监听都无所谓；

  即

\[dp[x][i+j][1][1]=\sum dp[x][i][1][0]\ast (dp[y][j][1][0]+dp[y][j][1][1])+dp[x][i][1][1]\ast (dp[y][j][0][0]+dp[y][j][0][1]+dp[y][j][1][0]+dp[y][j][1][1]) \]

注意点

  1.由于 \(1\leq n\leq 10^5\)，\(1\leq k\leq \min(n,100)\)，所以 \(dp\) 数组不能开 \(long\ long\)（不然会 \(MLE\)），但计算时又会爆 \(int\)，所以要单开一个 \(long\ long\) 数组 \(tmp\) 转一下。

  2.注意循环边界，遍历 \(i\) 时从 \(0\) 到 \(\min(k,siz[x])\)，\(j\) 从 \(0\) 到 \(\min(k-i,siz[y])\)。

  3.输出时是 \(dp[1][k][0][1]+dp[1][k][1][1]\)，即刚好用完了 \(k\) 个监听设备，根节点放或没放监听设备都可以，但一定被监听的方案数。

代码

#include
using namespace std;
typedef long long ll;
const ll maxn=1e5+5,mod=1e9+7;
ll n,k,tmp[105][2][2],siz[100005];
int dp[100005][105][2][2];//dp[i][j][0/1][0/1]表示以i为根的子树已经放置了j个监听器，i放没放，i能不能被监听到的方案数
vector e[maxn];
void dfs(ll x,ll fa){
	siz[x]=dp[x][0][0][0]=dp[x][1][1][0]=1;
	for(auto y:e[x]){
		if(y!=fa){
			dfs(y,x);
			for(ll i=0;i<=min(k,siz[x]);i++){
				tmp[i][0][0]=dp[x][i][0][0];
				tmp[i][0][1]=dp[x][i][0][1];
				tmp[i][1][0]=dp[x][i][1][0];
				tmp[i][1][1]=dp[x][i][1][1];
				dp[x][i][0][0]=0;
				dp[x][i][0][1]=0;
				dp[x][i][1][0]=0;
				dp[x][i][1][1]=0;
			}
			for(ll i=0;i<=min(k,siz[x]);i++){
				for(ll j=0;j<=min(k-i,siz[y]);j++){
					ll a=dp[x][i+j][0][0],b=dp[x][i+j][0][1],c=dp[x][i+j][1][0],d=dp[x][i+j][1][1];
					ll e=dp[y][j][0][0],f=dp[y][j][0][1],g=dp[y][j][1][0],h=dp[y][j][1][1];
					dp[x][i+j][0][0]=(a+tmp[i][0][0]*f%mod)%mod;
					dp[x][i+j][1][0]=(c+tmp[i][1][0]*(e+f)%mod)%mod;
					dp[x][i+j][0][1]=(b+tmp[i][0][1]*(f+h)%mod+tmp[i][0][0]*h%mod)%mod;
					dp[x][i+j][1][1]=(d+tmp[i][1][0]*(g+h)%mod+tmp[i][1][1]*(e+f+g+h)%mod)%mod;
				}
			}
			siz[x]+=siz[y];
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>k;
	for(ll i=1;i>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,0);
	cout<<(dp[1][k][0][1]+dp[1][k][1][1])%mod;
	return 0;
}
"

原文地址: https://www.cveoy.top/t/topic/qHVT 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录