自动搬运

查看原文

来自洛谷，原作者为

	retep 离谱！世界太离谱了！（关注必互关）

搬运于2025-08-24 22:40:11，当前版本为作者最后更新于2022-10-05 23:31:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目简述

给定一棵有 $n$ 个节点的树，树上的每个节点都可以选择将子树中除自己外的节点全部删除，删除不同的个数会有相应的代价。求将除根节点以外的节点全部删除需要的最小代价是多少。

数据范围：$1\le n \le 5000$

算法标签：树上背包、动态规划、

题目传送门：P8564 ρars/ey

题目分析

强烈建议没做过的同学去做一下 P2014 [CTSC1997] 选课，这是树上背包的模板题，而本题也是用树上背包解决的。

本蒟蒻读完题第一个联想到的是经典的切钻石问题（或者切木头），切成不同大小能卖不同的价格，问最大价值。这里则变成了树上的切割，所以考虑用树上DP来解决。

$f_{i,j}$ 表示 $i$ 号节点删除子树中 $j$ 个节点的最小代价。那么答案就是 $f_{1,sz-1}$，其中 $sz$ 表示子树大小。

树上DP最重要的是理清楚儿子节点应该给父亲节点什么信息，父亲节点怎么处理这些信息。此处，父亲节点应该从所有儿子那里得到一个数组，表示删除子树中不同数量的节点的最小代价，也就是 $f_{i,j}$。父亲节点要用这些数组完成自己的数组，方便爷爷使用。

现在假设父亲节点要删 $j$ 个节点，分两种情况讨论：

第一种情况，父亲节点自己不去删，因为自己去删了最后一定只剩自己了，大部分时候不能这样。于是要将需要删除的数量合理分配给所有儿子，找到最小代价。我们不能枚举所有的分配方案，因为有几个儿子节点就需要几层循环来枚举，这样太慢了。所以考虑用动态规划的方式：$g_{i,j}$ 表示前 $i$ 个儿子节点，总共删除 $j$ 个节点，最少需要代价是多少。我们像切割钻石那样枚举当前儿子删多少，剩下的给前面的儿子删，那么转移方程为：

$$g_{i,j}=\min_{x=1}^{j}(g_{i-1,j-x}+cost(x))$$

$x$ 表示当前儿子节点删多少个节点，cost则是代价函数。

$g$ 数组算到最后一层得到的就是当前节点的 $f$ 数组，再加上面的方程式显然可以滚动数组，所以不需要新定义一个 $g$ 数组（这里是为了方便讲解），直接在 $f$ 里计算即可。

第二种情况，父亲节点自己主动删。这里需要注意的是，并不是说父亲去删了，其它节点都可以摆烂了，大部分情况是需要在父亲删之前为他分担代价的。同时，不管儿子怎么奋斗，他们都删不了自己，这时就需要父亲出马来完善 $f$ 数组了。因为父亲主动去删的话就一定只剩他自己一个了，所以 $j$ 一定等于 $sz-1$。再加上第一种情况里算好的 $g$ 数组（或者说是有一点点不完整的 $f$），我们只需要枚举一下儿子删多少，剩下的留给父亲删就行了，于是有：

$$f_{i,sz-1}= \min_{x=1}^{sz-1}(f_{i,x}+cost(sz-x-1)) $$

$x$ 表示儿子们一共删多少个节点，所以父亲就需要删 $sz-x-1$。

聪明读者可能会有疑惑，到头来这不是 $n^3$ 的吗？这不铁定超时吗？的确是这样的，但我们只需要加一点点小优化即可：依靠子树大小，加入循环的上下界。这是树上背包的经典优化，看似简单，实则作用巨大。

code

#include<bits/stdc++.h>
#define N 5005
#define ll long long
using namespace std;

int n,cost[N];
vector<int> to[N];
ll f[N][N],sz[N],son[N];


void solve(int u,int fa){ //树上背包
	sz[u]=1;
    // 第一种情况
	for(int i=0,cnt=0;i<to[u].size();i++){
		int v=to[u][i];
		if(v==fa)continue;
		solve(v,u); cnt++; //cnt记录第几个儿子，因为可能遇到连到父亲节点的边
		for(int x=sz[u]+sz[v]-cnt-1;x>=1;x--) //滚动数组
			for(int y=max(x-sz[u],1ll);y<=x&&y<sz[v];y++) //一共删x个，y个给当前儿子删，注意此处两个循环的上下界
				f[u][x]=min(f[u][x],f[u][x-y]+f[v][y]);
		sz[u]+=sz[v]; //计算子树大小
	}
    // 第二种情况
	for(int i=0;i<=sz[u]-son[u]-1;i++) //儿子节点删i个
		f[u][sz[u]-1]=min(f[u][sz[u]-1],f[u][i]+cost[sz[u]-i-1]);
}

int main(){
	cin>>n;
	for(int i=1;i<n;i++)
		cin>>cost[i];
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		to[u].push_back(v);
		to[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		son[i]=to[i].size()-1;
		for(int j=1;j<=n;j++)f[i][j]=1e13;
	}
	son[1]++,solve(1,0);
	cout<<f[1][sz[1]-1];
	return 0;
}