题解 P1272 【重建道路】

· · 题解

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

状态设计

首先可以有这么一个想法：设 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;
}