自动搬运

查看原文

来自洛谷，原作者为

	big_news away from OI | substandard competitor

搬运于2025-08-24 21:23:11，当前版本为作者最后更新于2019-10-26 09:50:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

个人觉得题解里面的那个转移并不是很好理解，有些基础的东西并没有把它讲明白，所以说说我自己的理解。

状态设计

首先可以有这么一个想法：设 $f[u][s]$ 表示在节点 $u$ ，获得大小为 $s$ 的子树所需要删除的边的个数。

转移

考虑对于一个 $s$ ，我们需要找到一种“空间”的分配方案。讲的形象一点，设 $s(v_i)$ 表示在子树 $v_i$ 内我们留下的节点个数，其中 $v_i$ 表示当前节点 $u$ 的第 $i$ 个子节点；再设 $c(v_i)$ 表示我们在子树 $v_i$ 中留下 $s(v_i)$ 个节点所删除的边的数量。那么现在我们要做的事情就是：对于全部 $v_i$ ，找到一种 $s(v_i)$ 的分配方式，使得 $∑s(v_i) = s$ ，且 $∑c(v_i)$ 最小，然后我们就可以令 $f[u][s] = ∑c(v_i)$，也就完成了状态的转移。

然后上面那句“对于全部 $v_i$ ，找到一种 $s(v_i)$ 的分配方式，使得 $∑s(v_i) = s$ ，且 $∑c(v_i)$ 最小”，你不觉得这是一个背包么？

然后这个时候你就会发现我们所设的 $f[u][s]$ 这个状态实际上是不完全的。不考虑滚动数组，我们应该设 $f[u][k][s]$ 表示考虑节点 $u$ 的前 $k$ 个子节点，取 $s$ 个节点所需要的最小花费，这就是一个背包。

那么可以写出一个转移：$f[u][k][s] = \min(f[u][k-1][s] + 1, f[u][k-1][s-s_v] + f[v][k_v][s_v])$，其中 $k_v$ 表示 $v$ 的所有子节点数量，$s_v$ 表示在子树 $v$ 上选取的点的数量。

上面那个方程其实很好理解：前面表示不从子树 $v$ 选取节点，那么要删除 $(u,v)$ 这条边，答案 $+1$ ；后面是在考虑子树 $v$ 内选取的节点个数。

然后上面那个方程它一点也不可爱，考虑滚动掉 $k$ 这一维，方程变成 $f[u][s] = \min(f[u][s] + 1, f[u][s-s_v] + f[v][s_v])$。

这基本上就做完了，但是在转移的顺序上还有点小问题。 我们发现 $f[u][k][s]$ 总从 $f[u][k-1][s]$ 或 $f[u][k-1][s-s_v]$ 的状态更新。也就是说，去掉 $k$ 这一维，我们需要保证 $f[u][s-s_v]$ 比 $f[u][s_v]$ 后更新，这样 $f[u][s_v]$ 才是我们想要用来转移的“上层状态”。那么也就是倒序枚举 $s$ 去更新。

于是我们只需要枚举 $s$，然后再枚举 $s_v$，去转移就好了。

考虑答案的统计

上面那个状态 $f[u][s]$ 里面， $u$ 实际上是强制选择的，否则就缺少一个能把若干子树连接起来的“桥梁”。但是贪心的想，我们不一定非得强制选择某一个节点啊。那么答案应该对所有的 $f[u][p]$ 取一个 $\min$ 。然后还有一个问题，就是再某一个非根节点的位置，我们想要取出这棵子树，还得把这个节点和它的父亲节点断掉，那么答案还得 $+1$ ，细节见代码。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int CN = 160;
class fs{
  public: int to,nxt; void init(int t,int n) {to=t;nxt=n;}
}E[CN * 2];
int hd[CN],ecnt = 0;
void add(int x,int y) {E[++ecnt].init(y,hd[x]);hd[x]=ecnt;}

int n,P,ans,sum[CN],f[CN][CN]; // sum[u] 表示子树 u 的大小
void dfs(int u,int p){
    sum[u] = 1; f[u][1] = 0; // 初始时不考虑子树，因此 f[u][1] = 1
    for(int k=hd[u];k;k=E[k].nxt){
        int v = E[k].to;
        if(v == p) continue;
        dfs(v, u); // 求出子树的答案
        sum[u] += sum[v]; // 累加大小
        
        for(int s=sum[u]; s; s--){ // 考虑背包问题的更新方式，那么一定要每次都更新一下
            f[u][s] += 1; // 实际上是 f[u][k][s] = f[u][k-1][s] + 1 ，滚动了 k 这一维
            for(int sv=0;sv<=min(s-1, sum[v]);sv++) // s-1 为了强制选根
                f[u][s] = min(f[u][s], f[u][s - sv] + f[v][sv]);
        }
    }    
}

int main()
{
    //freopen("p1272.in","r",stdin);

    scanf("%d%d",&n,&P);
    for(int i=1;i<n;i++){
        int x,y; scanf("%d%d",&x,&y);
        add(x,y); add(y,x);
    }

    memset(f,0x3f,sizeof(f));
    dfs(1,0);
    ans = f[1][P]; for(int i=2;i<=n;i++) ans = min(ans, f[i][P] + 1); // 加上与父亲之间的那条边
    printf("%d", ans);

    return 0;
}