Codeforces 1281F 树上背包

题意：

有一棵有$n$个结点的树，每个结点有两个权值$a_i,b_i$，将树分为$m$个连通分量，使得其联通分量内$a$权值总和大于$b$权值总和的连通分量数目最多，求出这个数目。

题目是先输入$b$再输入$a$的

Solution：

题意可以转化成$a-b$权值之和大于0的连通分量最大数目，下面的权值都代表$a-b$

第一个想法就是树形$dp$，设$dp[u][i]$为将$u$这棵子树分为$i$个联通分量，其中符合条件的连通分量最多数目

当前点$u$的联通分量显然不可能跨越儿子和他的子树在一起，于是我们考虑按背包将儿子合并到$u$这个连通分量上，那么我们需要维护每棵子树顶部的连通分量的权值之和，需要维护什么性质呢？我们需要连通分量的权值和尽可能大，于是考虑维护顶部连通分量的最大权值和，但我们并不是一味的要他最大，因为就算他儿子子树顶部的连通分量权值之和无限大，他也只能使$u$这个联通分量给答案带来一个贡献，不妨在使得子树答案最大时，尽量向上贡献，应该是更好的。然后考虑如何转移，显然转移只需要规划$u$这个连通分量的决策，如果按照原来的状态，有点难以下手，所以不妨将状态设为，除顶部连通分量外，最大的子树符合答案的连通分量数目，加以维护顶部连通分量的大小，就可以转移。转移时，对每个儿子，有两种决策

（1）把儿子顶部的连通分量并入$u$的

（2）不把儿子的连通分量并入$u$的

因此枚举儿子的划分数目，然后转移时维护顶部最大权值和即可，子树的答案是$dp[u]$+顶部权值是否大于0。

如果枚举被更新点来更新有些边界情况有点难处理，我们可以枚举子树的大小$j$，和合并完的子树大小$k$，滚动数组来更新，那么

不并入$u$时，$dp[u][i]=max(dp[u][j]+dp[v][k])$

并入时，$dp[u][i]=max(dp[u][j]+dp[v][k]+(tot[v][k]>0))$

同时维护某个最大值的可以用结构体写法，更简单一些，更多细节见代码

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

using ll=long long;
const int N=3005,inf=0x3fffffff;
const long long INF=0x3f3f3f3f3f3f,mod=998244353;

struct way
{
	int to,next;
}edge[N<<1];
int cnt,head[N];

void add(int u,int v)
{
	edge[++cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
}

int n,m,val[N],sum[N];

struct node
{
	ll val,tot;
	bool operator<(const node& x) const {return (val<x.val)||(val==x.val&&tot<x.tot);}	
}dp[N][N],tmp[N];

void dfs(int u,int fa)
{
	sum[u]=1; dp[u][1]={0,val[u]};
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v==fa) continue;
		dfs(v,u);
		for(int j=1;j<=sum[u];j++) tmp[j]=dp[u][j];
		for(int j=1;j<=sum[u]+sum[v];j++) dp[u][j]={-inf,-inf};//要被更新的要赋无穷小，不然会边界会误判
		for(int j=1;j<=sum[u];j++)
		{
			for(int k=1;k<=sum[v];k++)
			{
				dp[u][j+k-1]=max(dp[u][j+k-1],(node){tmp[j].val+dp[v][k].val,tmp[j].tot+dp[v][k].tot});
				dp[u][j+k]=max(dp[u][j+k],(node){tmp[j].val+dp[v][k].val+(dp[v][k].tot>0),tmp[j].tot});
			}
		}
		sum[u]+=sum[v];
	}
}

int main()
{
	//给一颗树，分为m个连通分量，让里面sum(val)>0的连通分量最多，求最大数
	int t; cin>>t;
	while(t--)
	{
		cin>>n>>m; cnt=0;
		for(int i=1;i<=n;i++) cin>>val[i];
		for(int i=1;i<=n;i++)
		{
			int x; cin>>x;
			val[i]=x-val[i];
			head[i]=0;
		}
		for(int i=1;i<n;i++)
		{
			int u,v; cin>>u>>v;
			add(u,v); add(v,u);
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++) dp[i][j]={-inf,-inf};
		dfs(1,0);
		printf("%d\n",dp[1][m].val+(dp[1][m].tot>0));
	}
	return 0;
}
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83