树上背包问题做题总结

背包(一般是\(01\)背包吧)与树形\(DP\)的结合,第一维通常是节点编号,第二维通常是背包体积.由子节点向父节点转移的时候,就是一个普通的背包问题.

\(T1\):选课/\(The\) \(more\), \(The\) \(Better\)

洛咕

HDU(多组数据)

题意:给定一个\(n\)个节点的森林,带点权,选\(m\)个点的最大点权和,要求选子节点必须先选父节点.

分析:新建一个虚根,森林变成树.套路地,设\(f[i][j]\)表示以\(i\)点为根的子树内选择\(j\)个点的最大点权和.先不考虑父节点必须选的话,\(f[u][j]=max(f[u][j],f[u][j-k]+f[v][k])\),最后再考虑要先选父节点,\(f[u][j]=f[u][j-1]+a[u]\).

#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=305;
int n,m,a[N],f[N][N];
int tot,head[N],nxt[N],to[N];
inline void add(int a,int b){
	nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
}
inline void dfs(int u,int fa){
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];dfs(v,u);
		for(int j=m;j>=0;--j)
			for(int k=j;k>=0;--k)
				f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);
	}
	if(u!=1){//如果不是虚根,则选子节点时必须要选这个根节点
		for(int j=m;j>=1;--j)f[u][j]=f[u][j-1]+a[u];
	}
}
int main(){
	while(1){
		n=read();m=read();if(!n&!m)break;
		tot=0;memset(head,0,sizeof(head));
		memset(f,0,sizeof(f));
		for(int i=2;i<=n+1;++i){//把1号节点当做虚根,其他节点2~n+1
			int x=read()+1;a[i]=read();
			add(x,i);
		}
		dfs(1,0);
		printf("%d\n",f[1][m]);
	}
    return 0;
}

\(T2\):有线电视网

洛咕

POJ

题意:给定一棵带边权,叶子结点带点权的有根树.问从根结点出发使得权值和不为负最多能到达的叶子结点个数.

分析:套路地,设\(f[i][j]\)表示以\(i\)为根的子树内选出\(j\)个叶子节点的最大权值和.则\(f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]-w[i])\).

可以先预处理出每个节点的子树内有多少个叶子节点,那么对于叶子节点初始化\(f[i][1]=a[i].\),答案就是最大的\(j\)满足\(f[1][j]>=0\).

#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=3005;
int n,m,a[N],size[N],f[N][N],yz[N];
int tot,head[N],nxt[N],to[N],w[N];
inline void add(int a,int b,int c){nxt[++tot]=head[a];head[a]=tot;to[tot]=b;w[tot]=c;}
inline void dfs(int u,int fa){
	size[u]=1;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];dfs(v,u);
		size[u]+=size[v];yz[u]+=yz[v];
	}
	if(size[u]==1){
		yz[u]=1;
		f[u][1]=a[u];
	}
}
inline void dp(int u,int fa){
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];dp(v,u);
		for(int j=yz[u];j>=1;--j){
			for(int k=1;k<=min(j,yz[v]);++k){
				f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]-w[i]);
			}
		}
	}
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n-m;++i){
		int sum=read();
		for(int j=1;j<=sum;++j){
			int x=read(),y=read();
			add(i,x,y);
		}
	}
	for(int i=n-m+1;i<=n;++i)a[i]=read();
	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)f[i][j]=-1e9;
	dfs(1,0);dp(1,0);
	for(int j=m;j>=0;--j)if(f[1][j]>=0){printf("%d\n",j);break;}	
	return 0;
}

\(T3\):重建道路

洛咕

POJ

题意:给定一棵\(n\)个节点的树,求留下一棵\(m\)个结点的子树，最少需要切断几条边?

分析:套路地,设\(f[i][j]\)表示以\(i\)为根的子树内留下\(j\)个节点最少需要切断的边数.则\(f[u][j]=min(f[u][j],f[v][k]+f[u][j-k])\),发现因为要考虑\(u->v\)这条边留不留的各种情况,然后就写挂了.

正难则反,设\(f[i][j]\)表示以\(i\)为根的子树内丢弃\(j\)个节点最少需要切断的边数.这个就可以\(f[u][j]=min(f[u][j],f[v][k]+f[u][j-k])\)这样转移了.初始化\(f[u][size[u]]=1\)(即相当于整颗子树都不要,直接切掉最上面那一条边即可).

然后还是设\(g[i][j]\)表示以\(i\)为根的子树内留下\(j\)个节点最少需要切断的边数.那么\(g[i][j]=f[i][size[i]-j]+(fa==root?0:1)\),即留下\(j\)个节点相当于丢掉\(size[i]-j\)个节点,然后如果\(i\)的父节点不是(虚)根节点\((0)\)的话,即这条边是存在的,需要切断.

#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=200;
int n,m,ans,size[N],f[N][N],g[N][N];
int tot,head[N],nxt[N],to[N];
inline void add(int a,int b){
	nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
}
inline void dfs1(int u,int fa){
	size[u]=1;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];dfs1(v,u);
		size[u]+=size[v];
	}
	f[u][size[u]]=1;
}
inline void dfs2(int u,int fa){
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];dfs2(v,u);
		for(int j=size[u];j>=1;--j)
			for(int k=1;k<=min(size[v],j);++k)
				f[u][j]=min(f[u][j],f[u][j-k]+f[v][k]);
	}
}
inline void dfs3(int u,int fa){
    g[u][size[u]]=(fa^0?1:0);
    for(int i=1;i

发现树上背包问题有个通用套路,状态一般都是\(f[i][j]\)表示以\(i\)为根的子树内.....\(j\)个节点的......,然后一般先要\(dfs\)预处理出一些东西,然后对叶子节点初始化,最后再\(dfs\)一次从下往上状态转移即可.

动态规划-背包问题动态规划-树形DP

相关

标签