树形DP浅析

动态规划の树形dp

树形DP

动态规划这东西是没有模板的。。

因此，通过最近的刷题，我总结出了树形DP的一些套路：

通常情况下，树形DP是需要结合DFS和回溯一起使用的，其中的状态通常定义为一个节点的状态，它有可能受到它的儿子节点（或者父亲节点）的影响，因此就会出现多个状态，而状态转移方程通常由儿子（或父亲）的状态推得，具体问题具体分析，下面来搞几道典型例题

习题

1. POJ 2342 没有上司的舞会

题意

一棵节点有权值的树，从中取出一些节点，相邻的两节点不能同时取出，问取出节点的权值和最大值是多少？

题解

定义如下两个状态

则转移方程如下（其中v为i的子节点们）

AC代码

code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
struct Edge{
	int v,next;
}e[50005];
int cnt,head[50005]; 
inline void addedge(int u,int v){
	e[cnt]=Edge{v,head[u]};
	head[u]=cnt++;
}
int n,indeg[6005],val[6005],dp[6005][2];

void dfs(int x){
	dp[x][1]=val[x];//取的话，最小值就是本身节点的权值
	for(int i=head[x];~i;i=e[i].next){
		int v=e[i].v;
		dfs(v); //挖到最孙子的那一个节点
		dp[x][1]+=dp[v][0]; //开始dp
		dp[x][0]+=max(dp[v][0],dp[v][1]);
	}
}
int main(){
	scanf("%d",&n);
	memset(head,-1,sizeof(head));
	for(int i=1;i<=n;i++) scanf("%d",&val[i]);
	int u,v;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&u,&v);
		if(u==0&&v==0) break;
		addedge(v,u);
		indeg[u]++;
	}
	int start;
	for(int i=1;i<=n;i++){
		if(indeg[i]==0){
			start=i; //找根节点
			break;
		}
	}
	dfs(start);
	printf("%d\n",max(dp[start][0],dp[start][1])); //取个最大值
	return 0;
}

POJ 1463 Strategic game

题意

在一棵树的节点上安放士兵，每个士兵能守卫与它相连的所有边，问最少需要几个士兵才能守卫到所有边？

题解

跟上一题重题啊，代码只需要把DFS第一行的dp[i][1]=val[i]改成dp[i][1]=1就行了

POJ 2378 Tree Cutting

题意

要求你删除一棵树的一些节点，使得删掉这个节点之后形成的两棵子树节点数均不超过总结点数的一半，问哪些节点可以删除，升序输出它们

题解

利用求树的重心的DP过程，在每个节点的子节点遍历完之后判断一下是否存在n-Size[x]<=n/2&&ans[x]<=n/2（其中Size[x]是以x节点为父亲的这棵树的节点总数，ans[x]是以x节点为父亲的这棵树的儿子中节点数最大的子树的节点数），如果可行，就标记一下这个节点，最后按顺序遍历输出就行了

AC代码

code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
struct Edge{
	int v,next;
}e[50005];
int cnt,head[50005]; 
inline void addedge(int u,int v){
	e[cnt]=Edge{v,head[u]};
	head[u]=cnt++;
}
int n,dp[60005][2],Size[50005],ans[50005];

inline void init(){
	cnt=0;
	memset(head,-1,sizeof(head));
}
bool giao[10005],f;
void dfs(int x,int fa){
	Size[x]=1;
	ans[x]=0;
	for(int i=head[x];~i;i=e[i].next){
		int v=e[i].v;
		if(v==fa) continue;
		dfs(v,x);
		Size[x]+=Size[v];
		ans[x]=max(ans[x],Size[v]);
	}
	if(ans[x]<=n/2&&n-Size[x]<=n/2){
		giao[x]=1;
	}
}

int main(){
	scanf("%d",&n);
	init();
	int u,v;
	for(int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		addedge(u,v);
		addedge(v,u); 
	}
	dfs(1,-1);
	for(int i=1;i<=n;i++){
		if(giao[i]){
			f=true;
			printf("%d\n",i);
		}
	}
	if(!f) printf("NONE\n");
	return 0;
}

ZOJ 3201 Tree of Tree

题意

给你一棵节点带权的树，要求找出指定节点数的权值和最大的子树的权值和

题解

树形DP+背包

定义状态：

转移方程：

可以先像求树的重心那样DFS到叶子节点，然后开始倒着背包（注意：枚举的时候像背包一样倒着枚举）

AC代码

code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
struct Edge{
	int v,next;
}e[50005];
int cnt,head[505];
inline void addedge(int u,int v){
	e[cnt]=Edge{v,head[u]};
	head[u]=cnt++;
}
int n,k,val[505],dp[205][205];

inline void init(){
	cnt=0;
	memset(dp,0,sizeof(dp));
	memset(val,0,sizeof(val));
	memset(head,-1,sizeof(head));
}

void dfs(int x,int fa){
	dp[x][1]=val[x];
	for(int i=head[x];~i;i=e[i].next){
		int v=e[i].v;
		if(v==fa) continue;
		dfs(v,x);
		for(int j=k;j>=1;j--){
			for(int l=j-1;l>=1;l--){
				dp[x][j]=max(dp[x][j],dp[x][j-l]+dp[v][l]);
			}
		}
	}
}

int main(){
	while(~scanf("%d%d",&n,&k)){
		init();
		int u,v;
		for(int i=0;i<n;i++){
			scanf("%d",&val[i]);
		}
		for(int i=1;i<n;i++){
			scanf("%d%d",&u,&v);
			addedge(u,v);
			addedge(v,u);
		}
		
		dfs(0,-1);
		int ans=0;
		for(int i=0;i<n;i++){
			ans=max(ans,dp[i][k]);
		}
		printf("%d\n",ans);
	}
	return 0;
}

POJ 3659 Cell Phone Network

题意

有点像上面那道安防士兵的题，条件改为：每个士兵能守护到自己以及与它相连的每个节点，问最少需要安放多少士兵才能够守护到所有节点？

题解

似乎可以定义一个一模一样的状态：

但是这样的话，会发现dp[i][1]的转移方程写不出来，因为如果一个点不放士兵，那么可以从他的儿子中任选一个放一个士兵就行了，但这样的话，他的父节点就又受到了影响，因此我们需要换一种状态表示

转移方程如下：

我们发现，第三行这个转移方程有点问题：如果全都是由dp[v][2]转移过来的，那么i这个点就没有被守护到，那怎么办呢？

很简单，只需要每次遍历儿子节点的时候比较一下$dp[v][0]和dp[v][2]$的大小，如果前者比后者大了，就记录一下两者最小的差值，遍历完所有儿子后如果是前者一直都比后者大，那么就出现了上述特例，需要强行给i节点的值加上这个最小差值（表示强制让一个最优的儿子去守护自己，保证了最小）

AC代码

code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
inline ll read() { 
	ll kk=0,f=1; 
	char cc=getchar(); 
	while(cc<'0'||cc>'9'){if(cc=='-')f=-1;cc=getchar();} 
	while(cc>='0'&&cc<='9'){kk=(kk<<1)+(kk<<3)+cc-'0';cc=getchar();} 
	return kk*f; 
}

const int inf=1<<30;
struct Edge{
	int v,next;
}e[500005];
int cnt,head[50005];
inline void addedge(int u,int v){
	e[cnt]=Edge{v,head[u]};
	head[u]=cnt++;
}
int n,dp[500005][3];

inline void init(){
	cnt=0;
	memset(head,-1,sizeof(head));
}
bool vis[500005];

void dfs(int x,int fa){
	dp[x][0]=1;
	bool f=false;
	int minh=inf;
	for(int i=head[x];~i;i=e[i].next){
		int v=e[i].v;
		if(v==fa) continue;
		dfs(v,x);
		dp[x][0]+=min(dp[v][0],min(dp[v][1],dp[v][2]));
		dp[x][1]+=min(dp[v][0],dp[v][2]);
		if(dp[v][0]<=dp[v][2]){
			f=true; //没必要强制转换了
			dp[x][2]+=dp[v][0];
		}else{ //记录最小差值
			minh=min(minh,dp[v][0]-dp[v][2]);
			dp[x][2]+=dp[v][2];
		}
	}
	
	if(!f){ //如果出现了特例，就要强制把一个最好的儿子抓过来
		dp[x][2]+=minh;
	}
}
int main(){
	n=read();
	init();
	int u,v;
	for(int i=1;i<n;i++){
		u=read(),v=read();
		addedge(u,v);
		addedge(v,u);
	}
	dfs(1,-1);
	printf("%d\n",min(dp[1][0],dp[1][2]));
	return 0;
}

HDU 2196 Computer

题意

给一棵树，求到每个节点距离最远的节点之间距离

题解

这题让我学会了一个最最简洁优美的求树的直径的代码

利用求树的直径的算法，这题需要三次DFS：第一次从任意节点出发找到直径的一端；第二次从这一端出发，同时更新每个节点到这一端的距离，并找到另一端；第三次从另一端出发，更新每个节点到另一端和到这一端两者中的最远距离

而这三次DFS可以通过同一个函数完成：dfs(int x,int fa,int len)

AC代码

code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Edge{
	ll v,w,next;
}e[500005];
ll cnt,head[50005];
inline void addedge(ll u,ll v,ll w){
	e[cnt]=Edge{v,w,head[u]};
	head[u]=cnt++;
}
ll n,vis[500005],start;
ll dis[500005],ans;
inline void init(){
	cnt=ans=start=0;
	memset(head,-1,sizeof(head));
	memset(dis,0,sizeof(dis));
}

void dfs(ll x,ll fa,ll len){ //核心！！！
	for(ll i=head[x];~i;i=e[i].next){
		ll v=e[i].v,w=e[i].w;
		if(v==fa) continue;
		dfs(v,x,len+w);
		dis[v]=max(dis[v],len+w);
		if(len+w>=ans){ //一定是>=,否则另一端找不到QAQ
			ans=len+w;
			start=v;
		}
	}
}

int main(){
	while(scanf("%lld",&n)!=EOF){
		init();
		ll u,w;
		for(ll i=2;i<=n;i++){
			scanf("%lld%lld",&u,&w);
			addedge(i,u,w);
			addedge(u,i,w);
		}
		dfs(1,-1,0);
		dfs(start,-1,0);
		dfs(start,-1,0);
		for(ll i=1;i<=n;i++){
			printf("%lld\n",dis[i]);
		}
	}
	return 0;
}
算法
动态规划

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！