树形DP

简介

经典应用：树的重心（以这个点为根，最大子树的结点数最少），树的直径，树的中心（到树中其他点的最远距离最近）

例题

  1. 树的直径

  1. 战略游戏

问题：给定一棵树，从中选择最少的结点，使得所有边至少有一个端点在所选集合中，输出所选择结点的个数。

分析：主要是点的取舍，用dp[i][1]和dp[i][0]分别表示该点取或不取时，以它为根的子树的最小代价。

转移：如果该点不取，则必须取它的所有儿子，此时 dp[i][0]=∑j∈son[i]dp[j][1] dp[i][0]=\sum_{j \in son[i]} dp[j][1] ；否则，选取最优解，此时 $ dp[i][1]=1+\sum_{j \in son[i]} \min(dp[j][1],dp[j][0]) $。转移方向是从叶子结点到根结点，可以使用递归实现。

代码 
# include<iostream>
using namespace std;

const int N=1502;
int n,t,k,r;
int cnt,head[N],to[2*N],nxt[2*N];
int dp[N][2]; //0不放1放 

void add(int x,int y){
	to[++cnt]=y;
	nxt[cnt]=head[x];
	head[x]=cnt;
}

void dfs(int x,int fa){
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(y==fa) continue;
		dfs(y,x);
		dp[x][0]+=dp[y][1];
		dp[x][1]+=min(dp[y][0],dp[y][1]);
	}
	dp[x][1]++;
}

int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>t>>k;
		for(int j=1;j<=k;++j){
			cin>>r;
			add(t,r);
			add(r,t);
		}
	}
	dfs(0,-1);
	cout<<min(dp[0][0],dp[0][1]);
	return 0;
}
  1. 二叉苹果树

需要留意到一点：这是一棵现实意义上的树，因此树根 1 1 需要被保留，且修剪完之后必须是一个连通块。

用 l[x] l[x] 和 r[x] r[x] 分别代表结点x的左右儿子，w[x][y] w[x][y] 代表结点x和y之间的边权，dp[i][j] dp[i][j] 表示 i i 号结点的子树保留 j j 根树枝的最大苹果数量，那么可以得到转移：

dp[i][j]=max⁡p+q=j(s+t)dp[i][j]=\max_{p+q=j} (s+t)

其中：

$$s=\begin{cases} 0 & p=0 \\ dp[l[x]][p-1]+w[x][l[x]] & p\ge 1 \end{cases}$$$$t=\begin{cases} 0 & q=0 \\ dp[r[x]][q-1]+w[x][r[x]] & q\ge 1 \end{cases}$$

时间复杂度 O(n3) O(n^3) ，空间复杂度 O(n2) O(n^2) ，在本题 n≤100 n \le 100 的限制下可以通过。

（本题实敲50min。。。）

代码 
# include<iostream>
using namespace std;

const int N=105;
int n,q,x,y,z;
bool vis[N];
int map[N][N],to[N][5];
int l[N],r[N],fa[N],son[N];
int dp[N][N],tmp;

void build(int x){
	if(to[x][0]==1){
		son[x]=1;
		return;
	}
	if(x==1){
		l[x]=to[x][1];
		r[x]=to[x][2];
	}
	else{
		if(to[x][1]==fa[x]){
			l[x]=to[x][2];
			r[x]=to[x][3];
		}
		else if(to[x][2]==fa[x]){
			l[x]=to[x][3];
			r[x]=to[x][1];
		}
		else{
			l[x]=to[x][1];
			r[x]=to[x][2];
		}
	}
	fa[l[x]]=fa[r[x]]=x;
	build(l[x]);
	build(r[x]);
	son[x]=son[l[x]]+son[r[x]]+1;
	return;
}

void dfs(int x){
	if(son[x]==1) return;
	dfs(l[x]);
	dfs(r[x]);
	for(int i=0;i<=son[l[x]];++i)
		for(int j=0;j<=son[r[x]];++j){
			tmp=0;
			tmp+=(i?dp[l[x]][i-1]+map[x][l[x]]:0);
			tmp+=(j?dp[r[x]][j-1]+map[x][r[x]]:0);
			dp[x][i+j]=max(dp[x][i+j],tmp);
		}
}			

int main(){
	cin>>n>>q;
	for(int i=1;i<n;++i){
		cin>>x>>y>>z;
		map[x][y]=z;
		map[y][x]=z;
		to[x][++to[x][0]]=y;
		to[y][++to[y][0]]=x;
	}
	build(1);
	dfs(1);
	cout<<dp[1][q];
	return 0;
}
  1. 皇宫看守

本题的状态设计和T5战略游戏不同，因为父亲结点的状态也可以影响到自身。

因此需要三种状态：

1.选父亲节点，不选本节点。

2.选子节点，不选本节点。

3.选本节点。

那么，状态应该设计成：

dp[x][0] dp[x][0] 表示不选本结点选父亲节点的最小花费；

dp[x][1] dp[x][1] 表示不选本结点选至少一个子节点的最小花费；

dp[x][2] dp[x][2] 表示选本节点的最小花费。

接下来设计转移：

对于 dp[x][0] dp[x][0] ：

$ dp[x][0]=\sum_{y\in son[x]}\min(dp[y][1],dp[y][2]) $；

对于 dp[x][2] dp[x][2] ：

若选了自己，只需要在儿子中选花费最小的就可以了；

$ dp[x][2]=\sum_{y\in son[x]}(\min(dp[y][1],dp[y][2],dp[y][0]))+cost[x] $；

对于dp[x][1]:

$ dp[x][1]=sum_{y\in son[x]}(min(dp[y][1],dp[y][2]))+d $；

这里 d=min(dp[y][2]−min(dp[y][1],dp[y][2]))d=min(dp[y][2]-min(dp[y][1],dp[y][2])) ；

这么设的原因是，若 x x 节点所有的儿子 y y 的 dp[y][1] dp[y][1] 都比 dp[y][2] dp[y][2] 小，就没有节点能看到 x x 节点了，所以我们必须在 x x 的子节点中强制选一个。

时间复杂度为 O(n) O(n) 。

代码 
# include<iostream>
using namespace std;

const int N=1505;
int n,x,k,m,r;
int cnt,head[N],to[2*N],nxt[2*N];
int cost[N],fa[N],dp[N][5]; //父亲，儿子，自己 

void add(int x,int y){
	to[++cnt]=y;
	nxt[cnt]=head[x];
	head[x]=cnt;
}

void dfs(int x,int fa){
	int d=2e9;
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(y==fa) continue;
		dfs(y,x);
		dp[x][0]+=min(dp[y][1],dp[y][2]);
		dp[x][1]+=min(dp[y][1],dp[y][2]);
		dp[x][2]+=min(dp[y][0],min(dp[y][1],dp[y][2]));
		d=min(d,dp[y][2]-min(dp[y][2],dp[y][1]));
	}
	dp[x][1]+=d;
	dp[x][2]+=cost[x];
}

int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>x;
		cin>>cost[x]>>m;
		for(int j=1;j<=m;++j){
			cin>>r;
			add(x,r);
			add(r,x);
		}
	}
	dfs(1,0);
	cout<<min(dp[1][1],dp[1][2]);
	return 0;
}
  1. [CTSC1997] 选课

典型的树上背包问题，转化成分组背包处理。

代码 
# include<iostream>
using namespace std;

const int N=305;
int n,m,k,s;
int cnt,head[N],to[N],nxt[N],val[N];
int son[N],fa[N],dp[N][N]; //以i为根，重量为j 

void add(int x,int y,int w){
	to[++cnt]=y;
	val[cnt]=w;
	nxt[cnt]=head[x];
	head[x]=cnt;
}

void build(int x){
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		build(y);
		son[x]+=son[y]+1;
	}
}

void dfs(int x){
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i],w=val[i];
		dfs(y);
		for(int k=son[x];k>=0;--k)
			for(int j=0;j<=son[y];++j)
				if(k>j)
					dp[x][k]=max(dp[x][k],dp[x][k-j-1]+dp[y][j]+w);
	}
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		cin>>k>>s;
		add(k,i,s);
		fa[i]=k;
	}
	build(0);
	dfs(0);
	cout<<dp[0][m];
	return 0;
}

作业与练习

  1. 没有上司的舞会

思路类似P2016

代码 
# include<iostream>
using namespace std;

const int N=6e3+5;
int n,r[N],dp[N][2],l,k,root;
int cnt,head[N],to[N],nxt[N];
bool f[N],vis[N];

void add(int x,int y){
	to[++cnt]=y;
	nxt[cnt]=head[x];
	head[x]=cnt;
}

void dfs(int x){
	if(vis[x]) return;
	vis[x]=1;
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		dfs(y);
		dp[x][1]+=dp[y][0];
		dp[x][0]+=max(dp[y][0],dp[y][1]);
	}
	dp[x][1]+=r[x];
}

int main(){
	cin>>n;
	root=n*(n+1)/2;
	for(int i=1;i<=n;++i) cin>>r[i];
	for(int i=1;i<n;++i){
		cin>>l>>k;
		add(k,l);
		root-=l;
	}
	dfs(root);
	cout<<max(dp[root][0],dp[root][1]);
	return 0;
}
  1. [ZJOI2007] 时态同步

一道很好想的树形DP。

代码 
# include<iostream>
using namespace std;
# define ll long long

const int N=5e5+2;
int n,s,a,b;
int cnt,head[N],to[2*N],nxt[2*N];
ll t,val[2*N],ma[N],dp[N],ans;

void add(int a,int b,ll t){
	to[++cnt]=b;
	nxt[cnt]=head[a];
	val[cnt]=t;
	head[a]=cnt;
}

void f(int x,int fa){
	ll tmp=0;
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(y==fa) continue;
		ll w=val[i];
		f(y,x);
		tmp=max(tmp,w+ma[y]);
	}
	ma[x]=tmp;
}

void dfs(int x,int fa){
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(y==fa) continue;
		ll w=val[i];
		dfs(y,x);
		dp[x]+=dp[y]+ma[x]-w-ma[y];
	}
}

int main(){
	cin>>n>>s;
	for(int i=1;i<n;++i){
		cin>>a>>b>>t;
		add(a,b,t);
		add(b,a,t);
	}
	f(s,0);
	dfs(s,0);
	cout<<dp[s];
	return 0;
}
  1. 周年纪念晚会

代码 
# include<iostream>
using namespace std;

const int N=6e3+2;
int n,p[N],k,l;
int cnt,head[N],to[2*N],nxt[2*N];
int dp[N][2]; //0不选1选 

void add(int x,int y){
	to[++cnt]=y;
	nxt[cnt]=head[x];
	head[x]=cnt;
}

void dfs(int x,int fa){
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(y==fa) continue;
		dfs(y,x);
		dp[x][0]+=max(dp[y][0],dp[y][1]);
		dp[x][1]+=dp[y][0];
	}
	dp[x][1]+=p[x];
}

int main(){
	cin>>n;
	for(int i=1;i<=n;++i) cin>>p[i];
	while(1){
		cin>>k>>l;
		if(!k&&!l) break;
		add(k,l);
		add(l,k);
	}
	dfs(1,0);
	cout<<max(dp[1][0],dp[1][1]);
	return 0;
}
  1. 数字转换

代码 
# include<iostream>
using namespace std;

const int N=5e4+2;
int n,p[N];
int cnt,head[N],to[2*N],nxt[2*N];
int dp1[N],dp2[N];

void add(int x,int y){
	to[++cnt]=y;
	nxt[cnt]=head[x];
	head[x]=cnt;
}

void dfs(int x,int fa){
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(y==fa) continue;
		dfs(y,x);
		int a=dp1[y]+1;
		if(a>dp1[x]) dp2[x]=dp1[x],dp1[x]=a;
		else if(a>dp2[x]) dp2[x]=a;
	}
}

int main(){
	cin>>n;
	if(n==1){
		cout<<0;
		return 0;
	}
	for(int i=1;i<=n;++i)
		for(int j=2;i*j<=n;++j)
			p[i*j]+=i;
	for(int i=2;i<=n;++i)
		if(p[i]<i){
			add(i,p[i]);
			add(p[i],i);
		}
	dfs(1,0);
	cout<<dp1[1]+dp2[1];
	return 0;
}
  1. 最大子树和

代码 
# include<iostream>
using namespace std;

const int N=16005;
int n,x,y,a[N],dp[N],ans;
int cnt,head[N],to[2*N],nxt[2*N];

void add(int x,int y){
	to[++cnt]=y;
	nxt[cnt]=head[x];
	head[x]=cnt;
}

void dfs(int x,int fa){
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(y==fa) continue;
		dfs(y,x);
		if(dp[y]>0) dp[x]+=dp[y];
	}
	dp[x]+=a[x];
}

int main(){
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1;i<n;++i){
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	ans=dp[1];
	for(int i=2;i<=n;++i) ans=max(ans,dp[i]);
	cout<<ans;
	return 0;
}
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 粤ICP备2021104657号
  3. Worker 0, 12ms
  4. Powered by Hydro v4.14.1 Community