洛谷U53878 树上背包，指针分配内存

题意：

给出一颗有$n$个结点的树，求最少删去几条边，可以使得图有一个大小为$p$的连通分量？

Solution：

设$dp[u][i]$为子树保留$i$个点，最少的子树删边数是多少？这显然是个树上背包，转移如下

$$dp[u][i]=min(dp[u][i-k]+dp[v][k])$$

诚然，子树若一个点都不保留，这棵子树的删边数应该是1，即删去根和根的父亲所连接的，我们需要在子树之间转移，所以$dp[u][0]$这一项应该是不存在的一项，但使子树一个都不保留是对根的父节点来说可实现的，于是$dp[u][i]$还需要考虑当前子树不保留的情况，即总转移方程为

$$dp[u][i]=min(min(dp[u][i-k]+dp[v][k]),dp[u][i]+1)$$

初始化条件，当我们尚未为当前子树合并任何子树时，应当只存在1个结点，并且此时操作次数为0，于是$dp[u][1]=0$，其余的置为无穷大

一开始做的时候状态不太明确，将$dp[u][0]$置为了1，实际上状态更准确的说法应该是子树至少与父亲相连，并且保留$i$个点，最少的删边数为何？整颗子树删去我们只需要在父亲转移的时候特殊考虑即可，正是因为这样，$dp[u][0]=inf$的含义为不可实现，其余$inf$的含义应当是等待更新的一个极大值

加强版由于空间太大，但$n\times p\le 10^8$，而$dp[u][i]$的$i\le p$，$n$个点，那么总空间最多$n\times p$，于是预先计算字树大小，分配一个$max(p,sum[u])$给子树$dp$即可

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

using ll=long long;
const int N=100005,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;
}

vector<int>f(100000005,inf);
int n,p,sum[N],*dp[N],*pp=&f[0];

void dfs1(int u,int fa)
{
	sum[u]=1;
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v==fa) continue;
		dfs1(v,u);
		sum[u]+=sum[v];
	}
	dp[u]=pp; pp+=max(p,sum[u]);
}

void dfs(int u,int fa)
{
	sum[u]=1; dp[u][1]=0;
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v==fa) continue;
		dfs(v,u);
		sum[u]+=sum[v];
		for(int j=min(sum[u],p);j>=1;j--)
		{
			int min1=dp[u][j]+1;
			for(int k=1;k<=min(sum[v],j);k++) min1=min(min1,dp[u][j-k]+dp[v][k]);
			dp[u][j]=min1;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>p;
	for(int i=1;i<n;i++)
	{
		int u,v; cin>>u>>v;
		add(u,v); add(v,u); 
	}
	dfs1(1,0); dfs(1,0);
	int ans=inf;
	for(int i=1;i<=n;i++) ans=min(ans,dp[i][p]+(i!=1));
	cout<<ans;
	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