pars/ey 题解
retep
·
·
题解
题目简述
给定一棵有 n 个节点的树，树上的每个节点都可以选择将子树中除自己外的节点全部删除，删除不同的个数会有相应的代价。求将除根节点以外的节点全部删除需要的最小代价是多少。
数据范围：1\le n \le 5000
算法标签：树上背包、动态规划、
题目传送门：P8564 ρars/ey
题目分析
强烈建议没做过的同学去做一下 P2014 [CTSC1997] 选课，这是树上背包的模板题，而本题也是用树上背包解决的。
本蒟蒻读完题第一个联想到的是经典的切钻石问题（或者切木头），切成不同大小能卖不同的价格，问最大价值。这里则变成了树上的切割，所以考虑用树上DP来解决。
树上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
```cpp
#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;
}
```